《编译原理》实验二(共16页).doc

《《编译原理》实验二(共16页).doc》由会员分享，可在线阅读，更多相关《《编译原理》实验二(共16页).doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上实验二 预测分析法设计与实现实验时间：2013.5.7，5.21，6.4实验目的设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。实验要求建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。实验内容（1）文法描述及其LL(1)分析表表达式语言（XL）的语法规则如下：1 程序 表达式；2 |表达式；程序prgm expr;prgm prgm prgm prgm 3 表达式

2、表达式 + 项4 |项expr term expr expr +term expr expr 5 项 项 * 因式6 |因式term factor term term *factor term term 7 因式 num_or_id8 |(表达式)factor (expr) factor num 将该语言的文法转换为如下的LL(1)文法：1 prgm expr;prgm 7 term factor term2 prgm prgm 8 term *factor term 3 prgm 9 term 4 expr term expr 10 factor (expr) 5 expr +term ex

3、pr 11 factor num6 expr first(prgm)=(,num first(prgm)=(,num, first(expr)=(,num first(expr)=+, first(term)=(,num first(term)=*, first(factor)=(,num follow(prgm)=# follow(prgm)=#follow(expr)=;, ) follow(expr)=; , )follow(term)=+,; , ) follow(term)=+,; , )follow(factor)=*,+,; select(prgm expr;prgm)= (,n

4、um select(prgm prgm)= (,num select(prgm )= #select(expr term expr)= (,num select(expr +term expr)=+select(expr )= ; , )select(term factor term)= (,num select(term *factor term)= * select(term )= +,; , )select(factor (expr)= (select(factor num)= num 该LL(1)文法的LL(1)分析表如下： TNNum+*();#prgm11prgm223expr44

5、expr566term77term9899factor1110对文法中每个文法符号指定一个常数值，符号编码表如下：文法符号常数值备注（Num+);*#4625130终结符（#为输入结束标志）Exprexprtermtermfactorprgmprgm258260259262261256257非终结符（2）文法及其LL(1)分析表的数据结构 文法的产生式可用数组Yy_pushtab存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于该表达式语言XL的LL(1)分析表，可用数组Yy_d存放。第一个下标是非终结符数值，第二个下标是终结符

6、数值，数组元素的值为：0（表示接受），1（表示产生式号），-1（表示语法错）。 数组Yy_pushtab的具体内容及表示如下：012345678910Yyp00257,1,258,0prgm ; exprYyp01256,0prgmYyp020Yyp03260,259,0expr term260,259,2,0expr term +262,261,2,0term factor *05,258,4,0) expr (6,0Num0262,261,0term factorYyp04Yyp05Yyp06Yyp07Yyp08Yyp09Yyp10数组Yy_d的具体内容及表示如下：0 1 2 3 4 5

7、6# ； + * （ ） Num-1-1-1-10-102-1-1-11-11-1-1-1-13-13-1-1-1-16-16-154-1-15-1-1-1-1-19-110-1887-18-1prgm 256 prgm 257 expr 258 term 259 expr 260factor 261term 262（3）预测分析器总控程序结构预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈（元素类型为int），其结构如下：初始化；/* 把开始符号的常数值压入分析站，输入指向第一个输入符号 */ while(分析栈非空) if(栈顶常数表示一个终结符) if(该常数

8、与输入符号的常数不等) 报语法错； else 把一个数从栈顶弹出； advance读下一输入符号； else /* 栈顶的常数表示一个非终结符 */ what_to_do=Yy_d栈顶常数当前输入符号的常数； if(what_to_do= = -1) 报语法错； else 把栈顶元素弹出栈； 把Yy_pushtabwhat_to_do中列出的全部常数压入分析栈； 请实现该程序。在程序中添加输出栈内容的功能，以便和手工模拟分析过程作比较。（4）用预测分析器和手工模拟两种方式对文法的句子1+2；进行分析。综合分析过程可用下表表示。栈（符号）栈（数值）输入串What_to_dosystem_goal

9、prgmprgm ; exprprgm ; expr termprgm ; expr term factorprgm ; expr term Numprgm ; expr termprgm ; expr prgm ; expr term +prgm ; expr termprgm ; expr term factorprgm ; expr term Numprgm ; expr term prgm ; expr prgm ; prgm 263256257 1 258257 1 260 259257 1 260 262 261257 1 260 262 6257 1 260 262 257 1

10、260 257 1 260 259 2257 1 260 259 257 1 260 262 261257 1 260 262 6257 1 260 262257 1 260 257 1 260 262257 1+2；#1+2；#1+2；#1+2；#1+2；#1+2；#+2；#+2；#+2；#2；#2；#2；#；#；#；#120371195711962（5）请考虑如何设计并实现LL(1)分析表的自动生成程序。下面是一个实例：可作为参考/LL(1)语法分析#include #include#include #define MAX 50using namespace std;struct T_NT

11、int code;char strMAX;T_NT T7=0,#,1,;,2,+,3,*,4,(,5,),6,Num; /终结符T_NT NT8=256,prom,257,prom,258,expr,259,term, /非终结符260,expr,261,factor,262,term,263,system_goal;typedef struct sqstint dataMAX;int top;SqStack;int Yy_pushtab134= /*逆序存放产生式右部内容*/257,1,258,0,256,0,0,260,259,0,0,260,259,2,0,0,262,261,0,262

12、,261,2,0,0,5,258,4,0,6,0,256,0;int Yy_d87= /LL1分析表初始化-1,0,-1,-1,0,-1,0,2,1,-1,-1,1,-1,1,-1,4,-1,-1,3,4,3,-1,-1,-1,-1,7,-1,7,-1,6,5,-1,-1,6,-1,-1,-1,-1,-1,10,-1,11,-1,9,9,8,-1,9,-1,-1,12,-1,-1,12,-1,12,;int main()SqStack st;int i=0,j=0,l=0;int q,k,m,n,a,what_to_do;char c,tMAX;int sMAX;coutc;tl=c;l+;i

13、f(c=0&c=9)si=6;elseswitch(c)case(:si=4;break;case+:si=2;break;case):si=5;break;case;:si=1;break;case*:si=3;break;case#:si=0;break;i+;coutLL1文法非递归预测分析表如下:endl;cout栈符号 | 栈数值 | 输入串 | what_to_doendl;st.top=-1;st.top+;st.datast.top=263;while(st.top!=-1) /栈非空int p=0;while(p=st.top)for(l=0;l8;l+)if(NTl.cod

14、e=st.datap) coutNTl.str ;for(i=0;i7;i+)if(Ti.code=st.datap)coutTi.str ;p+;coutleft | ; p=0;while(p=st.top)cout st.datap ;p+;cout | ;for(a=j;a5;a+)cout=0&st.datast.top7) /栈顶为终结符if(st.datast.top!=sj)/栈顶常数与输入符号常数不等cout语法错误;elsest.top-; /把一个数从栈顶弹出j+; /读下一输入符号else /栈顶常数为一个非终结符m=st.datast.top-256; n=sj;wh

15、at_to_do=Yy_dmn;cout | ; cout what_to_do;if(what_to_do=-1)cout语法错误;else st.top-; /把元素从栈顶弹出k=0;while(Yy_pushtabwhat_to_dok!=0)st.top+;st.datast.top=Yy_pushtabwhat_to_dok;k+;coutendl;return 0;/简单词法分析器#include #include #include #include #include #include #define NULL 0FILE *fp;char cbuffer;char *key21=

16、AND,BEGIN,CONST,DIV,DO,ELSE,END, FUNCTION,IF,INTEGER,NOT,OR,PROCEDURE, PROGRAM,READ,REAL,THEN,TYPE,VAR,WHILE, WRITE;char *border8=,;,:,.,(,),;char *arithmetic4=+,-,*,/;char *relation10=,=,:=,#;char *consts20;char *label20;int constnum=0,labelnum=0;int search(char searchchar,int wordtype) int i=0; sw

17、itch (wordtype) case 1:for (i=0;i=20;i+) if (strcmp(keyi,searchchar)=0) return(i+1); ; case 2:for (i=0;i=7;i+) if (strcmp(borderi,searchchar)=0) return(i+24); ; return(0); case 3:for (i=0;i=3;i+) if (strcmp(arithmetici,searchchar)=0) return(i+35); ; ; return(0); ; case 4:for (i=0;i=9;i+) if (strcmp(

18、relationi,searchchar)=0) return(i+39); ; ; return(0); ; case 5:for (i=0;i=constnum;i+) if (strcmp(constsi,searchchar)=0) return(23); ; constsi-1=(char *)malloc(sizeof(searchchar); strcpy(constsi-1,searchchar); constnum+; return(23); ; case 6:for (i=0;i=labelnum;i+) if (strcmp(labeli,searchchar)=0) r

19、eturn(22); ; labeli-1=(char *)malloc(sizeof(searchchar); strcpy(labeli-1,searchchar); labelnum+; return(22); ; char alphaprocess(char buffer) int atype; int i=-1; char alphatp20; while (isalpha(buffer)|(isdigit(buffer) alphatp+i=buffer; buffer=fgetc(fp); ; alphatpi+1=0; if (atype=search(alphatp,1) p

20、rintf( %-10s, %-5dn,alphatp,atype-1); else atype=search(alphatp,6); printf( %-10s, %-5dn,alphatp,atype-1); ; return(buffer); char digitprocess(char buffer) int i=-1; char digittp20; int dtype; while (isdigit(buffer) digittp+i=buffer; buffer=fgetc(fp); digittpi+1=0; dtype=search(digittp,5); printf( %

21、-10s, %-5dn,digittp,dtype-1); return(buffer); char otherprocess(char buffer) int i=-1; char othertp20; int otype,otypetp; othertp0=buffer; othertp1=0; if (otype=search(othertp,3) printf( %-10s, %-5dn,othertp,otype-1); buffer=fgetc(fp); goto out; ; if (otype=search(othertp,4) buffer=fgetc(fp); othert

22、p1=buffer; othertp2=0; if (otypetp=search(othertp,4) printf( %-10s, %-5dn,othertp,otypetp-1); goto out; else othertp1=0; printf( %-10s, %-5dn,othertp,otypetp-1); goto out; ; if(buffer=:) buffer=fgetc(fp); if (buffer=) printf( := , 44 n); buffer=fgetc(fp); goto out; else if (otype=search(othertp,2) p

23、rintf( %-10s, %-5dn,othertp,otype-1); buffer=fgetc(fp); goto out; ; if (buffer!=n)&(buffer!= ) printf(%c error,not a wordn,buffer); buffer=fgetc(fp);out: return(buffer); void main() int i; clrscr(); printf( The Result :n); for (i=0;i=20;i+) labeli=NULL; constsi=NULL; ; if (fp=fopen(pas.PAS,r)=NULL)

24、printf(error); elsecbuffer = fgetc(fp);while (cbuffer!=EOF) if (isalpha(cbuffer) cbuffer=alphaprocess(cbuffer); else if (isdigit(cbuffer) cbuffer=digitprocess(cbuffer); else cbuffer=otherprocess(cbuffer); ; printf( OVER !n); ; #include #include#include /下面定义保留，为简化程序，使用字符指针数组保存所有保留字。/如果想增加保留字，可继续添加，并

25、修改保留字数目#define keywordSum 8char *keywordkeywordSum= if,else,for,while,do,int,read,write;/下面定义纯单分界符，如需要可添加char singleword50=+-*();,:;/下面定义双分界符的首字符char doubleword10=!;extern char Scanin300, Scanout300; /用于接收输入输出文件名,在TEST_main.c中定义extern FILE *fin,*fout; /用于指向输入输出文件的指针,在TEST_main.c中定义int TESTscan()/词法分

26、析函数 char ch,token40; /ch为每次读入的字符，token用于保存识别出的单词 int es=0,j,n; /es错误代码，0表示没有错误。j,n为临时变量，控制组合单词时的下标等 printf(请输入源程序文件名（包括路径）：); scanf(%s,Scanin); printf(请输入词法分析输出文件名（包括路径）：); scanf(%s,Scanout); if (fin=fopen(Scanin,r)=NULL) /判断输入文件名是否正确 printf(n打开词法分析输入文件出错!n); return(1);/输入文件出错返回错误代码1 if (fout=fopen(

27、Scanout,w)=NULL) /判断输出文件名是否正确 printf(n创建词法分析输出文件出错!n); return(2); /输出文件出错返回错误代码2 ch=getc(fin); while(ch!=EOF) while (ch= |ch=n|ch=t) ch=getc(fin); if (isalpha(ch) /如果是字母，则进行标识符处理 token0=ch; j=1; ch=getc(fin); while(isalnum(ch) /如果是字母数字则组合标识符；如果不是则标识符组合结束 tokenj+=ch; /组合的标识符保存在token中ch=getc(fin); /读下

28、一个字符 tokenj=0; /标识符组合结束 /查保留字 n=0; while (n=keywordSum) /不是保留字，输出标识符fprintf(fout,%st%sn,ID,token); /输出标识符符号else/是保留字，输出保留字fprintf(fout,%st%sn,token,token); /输出保留字符号 else if (isdigit(ch)/数字处理 token0=ch; j=1; ch=getc(fin); /读下一个字符 while (isdigit(ch) /如果是数字则组合整数；如果不是则整数组合结束 tokenj+=ch; /组合整数保存在token中ch

29、=getc(fin); /读下一个字符 tokenj=0; /整数组合结束 fprintf(fout,%st%sn,NUM,token); /输出整数符号 else if (strchr(singleword,ch)0) /单分符处理 token0=ch; token1=0; ch=getc(fin);/读下一个符号以便识别下一个单词 fprintf(fout,%st%sn,token,token); /输出单分界符符号 else if (strchr(doubleword,ch)0) /双分界符处理 token0=ch; ch=getc(fin); /读下一个字符判断是否为双分界符 if (

30、ch=) /如果是=，组合双分界符 token1=ch;token2=0; /组合双分界符结束 ch=getc(fin); /读下一个符号以便识别下一个单词 else/不是=则为单分界符token1=0; fprintf(fout,%st%sn,token,token); /输出单或双分界符符号 else if (ch=/) /注释处理 ch=getc(fin); /读下一个字符 if (ch=*) /如果是*，则开始处理注释 char ch1;ch1=getc(fin); /读下一个字符do ch=ch1;ch1=getc(fin); /删除注释while (ch!=* | ch1!=/)&

31、ch1!=EOF); /直到遇到注释结束符*/或文件尾ch=getc(fin);/读下一个符号以便识别下一个单词 else /不是*则处理单分界符/ token0=/; token1=0; fprintf(fout,%st%sn,token,token); /输出单分界符/ else/错误处理 token0=ch;token1=0; ch=getc(fin); /读下一个符号以便识别下一个单词 es=3; /设置错误代码 fprintf(fout,%st%sn,ERROR,token); /输出错误符号 fclose(fin);/关闭输入输出文件 fclose(fout); return(es); /返回主程序/主程序#include #include extern int TESTscan();char Scanin300,Scanout300; /用于接收输入输出文件名FILE *fin,*fout; /用于指向输入输出文件的指针void main()int es=0;es=TESTscan();/调词法分析 if (es0) printf(词法分析有错,编译停止!);else printf(词法分析成功!n);专心-专注-专业