编译原理实验报告二

1、实验二 语法分析程序实现一、实验目的与要求通过设计、编制、调试一个典型的语法分析程序（任选一种有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，作为编制语法分析程序的依据），对实验一所得扫描器提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。二、一般实现方法说明为了在对源程序的一遍扫描过程中，同时完成词法和语法分析任务，应注意首先修改实验一中的词法分析程序，将它编写为子程序的形式，以便供语法分析程序调用。另外，应加强错误检查，对输入符号串中的词法、语法错误，给出必要的说明信息，尽可能多地、确切地指出错误的位置、原因和性质。例如，在

2、词法分析阶段，对当前正在处理的字符ch，可进一步定义一些与该字符相关的信息row和col，即定义：char ch; /*The current character*/int row; /*The line number position of the current character*/int col; /*The column number position of the current character*/分别表示该字符所在的行和列，这些内容在出错处理时用来提供和源程序位置相关的信息。三、实验内容基本实验题目：选择对各种常见高级程序设计语言都较为通用的语法结构算术表达式的一个简化子集作

3、为分析对象，根据如下描述其语法结构的BNF定义G2，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。G2： | + | - | * | / | ()若将语法范畴、和分别用E、T、F和i代表，则G2可写成：G2E：E T | E+T | E-T T F | T*F | T/F F i | (E)输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID 输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、

4、符号栈中的信息等，以及必要的出错说明信息。四、参考实现方法下面分别简要给出基于递归下降法、预测分析法、算符优先法、SLR(1)四种语法分析程序的开发方法示例说明，仅供参考。4、示例四：SLR(1)分析器的开发。首先，对于分析对象，即算术表达式的文法G2E，引入一个新的开始符号E，得到G2E的拓广文法G2E：0. EE 1. EE+T 2. EE-T 3. ET 4. TT*F 5. TT/F 6. TF 7. F(E) 8. Fi求出文法中各个非终结符号的FOLLOW集如下：Follow(E)=#，)，+，- Follow(T)=#，)，+，-，*，/ Follow(F)=#，)，+，-，*，

5、/然后，根据文法G2E构造识别其全部活前缀的DFA，以便据此构造SLR(1)分析表，参见表III。表III G2E的SLR(1)分析表状态ACTIONGOTO（）+-*/i#ETF0S4S51231S6S7Acc2R3R3R3S8S9R33R6R6R6R6R6R64S4S510235R8R8R8R8R8R86S4S51137S4S51238S4S5139S4S51410S15S6S711R1R1R1S8S9R112R2R2R2S8S9R213R4R4R4R4R4R414R5R5R5R5R5R515R7R7R7R7R7R7最后，编程实现SLR(1)分析表的驱动程序，即开发LR分析器的总控程序，完

6、成对算术表达式的识别。主要是用三维字符数组构造一个slr（1）的状态转移表，然后主控程序控制查询三维数组，调用一次词法分析再调用一次语法分析。5、 源程序、#include # include # include # include # include # define LB 0/左括号# define RB 1/右括号# define PL 2# define MI 3# define MU 4# define DI 5# define UCON 6 /Suppose the class number of unsigned constant is 7# define OVER 7# def

7、ine LT 8# define LE 9# define EQ 10# define NE 11# define GT 12# define GE 13# define IS 19/14至18被五个关键字占用# define ID 20#define MAX_KEY_NUMBER 20 /*关键字的数量*/#define KEY_WORD_END waiting for your expanding /*关键字结束标记*/char *KeyWordTableMAX_KEY_NUMBER=begin,end, if, then, else, KEY_WORD_END;char TOKEN20=

8、;char ch= ;/用于存储带判断的字符int row=1;/row标识错误在第几行/无符号数部分#define DIGIT 1#define POINT 2#define OTHER 3#define POWER 4#define PLUS 5#define MINUS 6#define ClassOther 200#define EndState -1int index=0;int w,n,p,e,d;int Class; /Used to indicate class of the wordint ICON;float FCON;static int CurrentState; /U

9、sed to present current state, the initial value:0/语法分析部分/产生式 1、E-E+T 2、E-E-T 3、E-T 4、T-T*F 5、T-T/F 6、T-F 7、F-(E) 8、F-i# define Max 256/goto表的列项# define E 0# define T 1# define F 2int StateStackMax;/状态栈int StackPoint;/状态栈指针int TopState;/作为状态栈盏栈顶指针int InputWordType;/输入的单词类型/ ( ) + - * / i #char Action

10、1684=s4, , , , , , s5, , , , s6, s7, , , , A, , r3, r3, r3, s8, s9, , r3, , r6, r6, r6, r6, r6, , r6, s4, , , , , , s5, , , r8, r8, r8, r8, r8, , r8, s4, , , , , , s5, , s4, , , , , , s5, , s4, , , , , , s5, , s4, , , , , , s5, , , s15, s6, s7, , , , , , r1, r1, r1, s8, s9, , r1, , r2, r2, r2, s8, s

11、9, , r2, , r4, r4, r4, r4, r4, , r4, , r5, r5, r5, r5, r5, , r5, , r7, r7, r7, r7, r7, , r7,;/action表/ E T Fint Goto163= 1, 2, 3,-1, -1, -1,-1, -1, -1,-1, -1, -1,10, 2, 3,-1, -1, -1,-1, 11, 3,-1, 12, 3,-1, -1, 13,-1, -1, 14,-1, -1, -1,-1, -1, -1,-1, -1, -1,-1, -1, -1,-1, -1, -1,-1, -1, -1,;/goto表int

12、 EXCUTE (int state, int symbol,FILE *fp,char JudgeStr,int row,int index);int GetChar (char ch);int HandleError (char StrJudge,int row);int Push( int State );int Pop(int count);int SLRControl(FILE* fp);/查保留字表，判断是否为关键字 int lookup (char *token)int n=0;while (strcmp(KeyWordTablen, KEY_WORD_END) /*strcmp

13、比较两串是否相同，若相同返回0*/if (!strcmp(KeyWordTablen, token) /*比较token所指向的关键字和保留字表中哪个关键字相符*/return n+1; /*根据单词分类码表I，设置正确的关键字类别码，并返回此类别码的值*/break;n+;return 6; /*单词不是关键字，而是标识符*/输出分析结果void out (int i, char* pStr)char Mnemonic5;if(0=i)strcpy(Mnemonic,LB);else if(1=i)strcpy(Mnemonic,RB);else if(2=i)strcpy(Mnemonic

14、,PL);else if(3=i)strcpy(Mnemonic,MI);else if(4=i)strcpy(Mnemonic,MU);else if(5=i)strcpy(Mnemonic,DI);else if(6=i)strcpy(Mnemonic,UCON);else if(7=i)strcpy(Mnemonic,OVER);else if(8=i)strcpy(Mnemonic,LT);else if(9=i)strcpy(Mnemonic,LE);else if(10=i)strcpy(Mnemonic,EQ);else if(11=i)strcpy(Mnemonic,NE);e

15、lse if(12=i)strcpy(Mnemonic,GT);else if(13=i)strcpy(Mnemonic,GE);else if(14=i)strcpy(Mnemonic,BEGIN);else if(15=i)strcpy(Mnemonic,END);else if(16=i)strcpy(Mnemonic,IF);else if(17=i)strcpy(Mnemonic,THEN);else if(18=i)strcpy(Mnemonic,ELSE);else if(19=i)strcpy(Mnemonic,IS);else if(20=i)strcpy(Mnemonic,

16、ID);elsestrcpy(Mnemonic,Unkown Type);printf(%s )对应%sn,Mnemonic,pStr);/报错部分void report_error (int row)printf(%s Error! In the %d rown,TOKEN,row);/扫描程序部分void scanner(FILE *fp)/总的判断函数开始就应该判断已读取的字符是否为空字符，不为则不用再读，直接进行判断，否则再读int i, c;fseek(fp,-1,1);/首先回溯一个字符，就是将文件所有的字符都在scanner内部判断，外部while循环不会浪费任何字符ch=fge

17、tc (fp);/scanner中要想判断字符，必须开头先读一个字符while( =ch|n=ch|t=ch)/将文件中的所有空字符浪费在这里if(n=ch)row+;ch=fgetc (fp);if(EOF=ch)return;/必须在这里判断一下if (isalpha (ch) /*it must be a identifer!*/TOKEN0=ch; ch=fgetc (fp); i=1;while (isalnum (ch)TOKENi=ch; i+;ch=fgetc (fp);TOKENi= 0;fseek(fp,-1,1); /* retract*/c=lookup (TOKEN)

18、;if (c!=6) out (c+13,TOKEN); else out (c+14,TOKEN);/此处加13或者14因为一些常量的定义产生冲突，被迫修改以适应else if(isdigit(ch)| .=ch)fseek (fp,-1,1);/首先回溯一个字符，下面为了循环内部使用先读字符后判断的格式。int Type; CurrentState=0;i=0;doch=fgetc(fp);TOKENi=ch;i+;TOKENi=0;/为随时输出字符串做准备Type=GetChar(ch);EXCUTE (CurrentState,Type,fp,TOKEN,row,i);while(Cu

19、rrentState!=EndState);elseswitch(ch)case : ch=fgetc(fp);if(ch=)out(LE,) out (NE,);elseout (LT,: ch=fgetc(fp);if(ch=)out(GE,=);elseout(GT,);break;case +:InputWordType=PL;out(PL,+);break;case -:InputWordType=MI;out(MI,-);break;case *:InputWordType=MU;out(MU,*);break;case /:InputWordType=DI;out(DI,/);b

20、reak;case (:InputWordType=LB;out(LB,();break;case ):InputWordType=RB;out(RB,);break;case #:InputWordType=OVER;out(OVER,#);break;default: report_error(row); break;return;/无符号数判断矩阵执行程序int EXCUTE (int state, int symbol,FILE *fp,char JudgeStr,int row,int index)/row用于指示出错的行数，index用于为待输出的字符串赋结束符0时用 switch

21、 (state) case 0:switch (symbol) case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break; case POINT: w=0;n=0;p=0;e=1;CurrentState=3;Class=UCON;break; default: Class=ClassOther; CurrentState=EndState; printf(无符号数的第一个字符是非法的！n); break; case 1:switch (symbol) case DIGIT: w=w*10+d;break; /CurrentStat

22、e=1 case POINT: CurrentState=2;break; case POWER: CurrentState=4;break; default: if (ch!=EOF)/如果是因为读到文件结束字符而终止识别（是正确识别一个无符号数结束），就不应该回退，否则可能造成死循环 fseek(fp,-1,1);/遇到其他的字符，可能是一条语句中的其他字符，需后退，因为主函数外层循环每次都要读一个字符进行判断，而这个判读不回溯，所以在内部把这个多读的字符回溯 ICON=w;CurrentState=EndState;JudgeStrindex-1=0;InputWordType=UCON

23、; printf(UCON,%i)对应%sn,ICON,JudgeStr); break; break; case 2:switch (symbol) case DIGIT: n+;w=w*10+d;break; case POWER: CurrentState=4;break; default: if (ch!=EOF) fseek(fp,-1,1); FCON=w*pow(10,e*p-n);CurrentState=EndState; JudgeStrindex-1=0; InputWordType=UCON; printf(UCON,%f)对应于%sn,FCON,JudgeStr);

24、break; case 3:switch (symbol) case DIGIT: n+;w=w*10+d;CurrentState=2;break; default: HandleError(JudgeStr,row);CurrentState=EndState; break; case 4:switch (symbol) case DIGIT: p=p*10+d;CurrentState=6;break; case MINUS: e=-1;CurrentState=5;break; case PLUS: CurrentState=5;break; default: HandleError(

25、JudgeStr,row);CurrentState=EndState; break; case 5:switch (symbol) case DIGIT: p=p*10+d;CurrentState=6;break; default: HandleError(JudgeStr,row);CurrentState=EndState;/判断一个无符号数的最后一个字符应该都是多余读取的，所以为了防止引起后面再次判断下一无符号数时产生呑字符的现象，都应该回溯一个字符 break; case 6:switch (symbol) case DIGIT:p=p*10+d;break; default: i

26、f (ch!=EOF) fseek(fp,-1,1); FCON=w*pow(10,e*p-n);CurrentState=EndState; JudgeStrindex-1=0; InputWordType=UCON; printf(UCON,%f)对应 %sn,FCON,JudgeStr); break; break; return CurrentState; /无符号数判断过程中的字符类型判断程序int GetChar (char ch)if(isdigit(ch) d=ch-0;return DIGIT;if (ch=.) return POINT;if (ch=E|ch=e) ret

27、urn POWER;if (ch=+) return PLUS;if (ch=-) return MINUS;return OTHER;/判断出错报错程序int HandleError (char StrJudge,int row)printf (Row: %d*%s Error!n,row,StrJudge); return 0;/语法分析总控程序int SLRControl(FILE* fp)while(ActionTopStateInputWordType0 != A)printf(栈顶状态：%in,TopState); printf(扫描的单词类型：%in,InputWordType)

28、; if (-1=TopState) printf(状态栈栈顶指针错误！n); return 0; if ( = ActionTopStateInputWordType0) printf(语法分析出错！n); return 0; else if(s=ActionTopStateInputWordType0) Push(atoi(&ActionTopStateInputWordType1); printf(执行压栈操作n); if (EOF!=fgetc(fp) scanner(fp); else printf(语句不完整！n); return 0; else if(r=ActionTopSta

29、teInputWordType0) int ProductionNum=atoi(&ActionTopStateInputWordType1); int ProdutionLeft=0; if (1=ProductionNum) ProdutionLeft=E;/为下面差goto表提供列坐标 Pop(3); printf(用产生式 1 归约n); else if(2=ProductionNum) ProdutionLeft=E; Pop(3); printf(用产生式 2 归约n); else if(3=ProductionNum) ProdutionLeft=E; Pop(1); printf(用产生式 3 归约n); else if(4=ProductionNum) ProdutionLeft=T; Pop(3); printf(用产生式 4 归约n); else if(5=ProductionNum) ProdutionLeft=T; Pop(3); printf(用产生式 5 归约n); else