北邮-编译原理-自底向上语法分析实验报告

1、自底向上语法分析器实验报告一问题描述编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。E - E+T | E-T | TT - T*F | T/F | FF - id | (E) | num实验要求：在对输入表达式进行分析的过程中，输出所采用的产生式。编写语法分析程序实现自底向上的分析，要求如下：（1） 构造识别所有活前缀的DFA。（2） 构造LR分析表。（3） 编程实现算法4.3，构造LR分析程序。二算法思想1.大体步骤：（1）根据题目所给出的文法构造相应的拓广文法，并求出该文法各非终结符的FIRST、FOLLOW集合；（2）.构造拓广文法的项目集规范族，并

2、构造出识别所有前缀的DFA；（3）构造文法的LR分析表；（4）由此构造LR分析程序。2.数据结构：1.输入缓冲区为一个字符型数组，读入输入的算术表达式并保存在此，以$结束；2.构建一个相对应的整型数组，将输入缓冲区中的字符转换为相应的代号并保存；3.构造一个结构体，以保存文法的某个产生式，该结构包括三个元素：整形变量，保存产生式左部非终结符代号。整型数组，保存产生式右部字符串的代号。整型变量，保存产生式右部长度；4.定义该结构的数组，保存文法的所有产生式；5.定义两个二维整形数组，goto和action，其值大于零代表移进操作，小于零代表规约操作，引进的状态或规约用到的产生式又绝对值表示。等于

3、零代表出现错误。等于特殊值999代表acc.状态。3.计算过程：文法对应的拓广文法为：1S - E2 E - E+T3 E - E-T4 E - T5 T - T*F6 T - T/F7 T - F8 F - (E)9 F - id10 F - num求的各个非终结符的FIRST、FOLLOW集合为：FIRST(S) = id, num, ( FOLLOW (S) = $ FIRST(E) = id, num, ( FOLLOW (E) = $ , + , - , ) FIRST(T) = id, num, ( FOLLOW (T) = $ , + , - , * , / , ) FIRST(

4、F) = id, num, ( FOLLOW (F) = $ , + , - , * , / , ) 构造项目集规范族：I0 = closure(S-E) = S-E, E-E+T, E-E-T, E-T, T-T*F, T-T/F, T-F, F-id, F-(E), F-num;从I0出发：I1 = go(I0, E) = closure(S-E, E-E+T, E-E-T) = S-E, E-E+T, E-E-T;I2 = go(I0, T) = closure(E-T, T-T*F, T-T/F) = E-T, T-T*F, T-T/F;I3 = go(I0, F) = closure

5、(T-F) = T-F;I4 = go(I0, id) = closure(F-id) = F-id;I5 = go(I0, () = closure(F-(E) = F-(E), E-E+T, E-E-T, E-T, T-T*F, T-T/F, T-F, F-id, F-(E), F-num;I6 = go(I0, num) = closure(F-num) = F-num;从I1出发：I7 = go(I1, +) = closure(E-E+T) = E-E+T, T-T*F, T-T/F, T-F, F-id, F-(E), F-num;I8 = go(I1, -) = closure(

6、E-E-T) = E-E-T, T-T*F, T-T/F, T-F, F-id, F-(E), F-num;从I2出发：I9 = go(I2, *) = closure(T-T*F) = T-T*F, F-id, F-(E), F-num;I10 = go(I2, /) = closure(T-T/F) = T-T/F, F-id, F-(E), F-num;从I5出发：I11 = go(I5, E) = closure(F-(E), E-E+T, E-E-T) = F-(E), E-E+T, E-E-T;从I7出发：I12 = go(I7, T) = closure(E-E+T, T-T*F

7、, T-T/F) = E-E+T, T-T*F, T-T/F;从I8出发：I13 = go(I8, T) = closure(E-E-T, T-T*F, T-T/F) = E-E-T, T-T*F, T-T/F;从I9出发：I14 = go(I9, F) = closure(T-T*F) = T-T*F;从I10出发：I15 = go(I10, F) = closure(T-T/F) = T-T/F;从I11出发：I16 = go(I11, ) = closure(F-(E) = F-(E);下面构造文法的LR分析表：goto0,E = 1; goto0,T = 2; goto0,F = 3;

8、action0,id = S4; action0,( = S5; action0,num = S6;action1,$ = ACC.; action1,+ = S7; action1,- = S8;action2,) = action2,+ = action2,- = action2,$ = R4;action2,* = S9; action2,/ = S10;action3,) = action3,+ = action3,- = action3,* = action3,/ = action3,$ = R7;action4,) = action4,+ = action4,- = action4

9、,* = action4,/ = action4,$ = R8;goto5,E = 11; goto5,T = 2; goto5,F = 3;action5,id = S4; action5,( = S5; action5,num = S6;action6,) = action6,+ = action6,- = action6,* = action6,/ = action6,$ = R10;goto7,T = 12; goto7,F = 3;action7,id = S4; action7,( = S5; action7,num = S6;goto8,T = 13; goto8,F = 3;a

10、ction8,id = S4; action8,( = S5; action8,num = S6;goto9,F = 14;action9,id = S4; action9,( = S5; action9,num = S6;goto10,F = 15;action10,id = S4; action10,( = S5; action10,num = S6;action11,) = S16; action11,+ = S7; action11,- = S8;action12,) = action12,+ = action12,- = action12,$ = R2; action12,* = S

11、9; action12,/ = S10;action13,) = action13,+ = action13,- = action13,$ = R3; action13,* = S9; action13,/ = S10;action14,) = action14,+ = action14,- = action14,* = action14,/ = action14,$ = R5;action15,) = action15,+ = action15,- = action15,* = action15,/ = action15,$ = R6;action16,) = action16,+ = ac

12、tion16,- = action16,* = action16,/ = action16,$ = R9;4.SLR(1)分析表为：E1: 缺少运算对象。认为加入一个Id入栈并转移至相应状态E2: 括号不匹配删掉右括号，则删去右括号并转移至相应状态E3: 缺少运算符，添加运算符并转移至相应状态actiongoto()+-*/idnum$ETF0s5E2E1E1E1E1 s4s6E11231E3E2s7s8E3E3Acc.2E3r4r4r4s9s10E3E3r43r7r7r7r7r7r74r8r8r8r8r8r85s5E2E1E1E1E1s4s611236E3r10r10r10r10r10r10

13、7s5E2E1E1E1 E1s4s61238s5E2E1E1E1E1s4s61339s5E2E1E1E1E1s4s61410s5E2E1E1E1E1s4s61511E3s16s7s8E3E312E3r2r2r2s2s2E3E3r213E3r3r3r3s9s10E3E3r314r5r5r5r5r5r515r6r6r6r6r6r616r9r9r9r9r9r9三、实验程序设计说明1.主要函数说明void TRANS();/*将读入的buffer数组内容按字符转换为相应代号存入code数组*/void GetFromCode();/*取得当前输入符号串的元素*/void PUSH(int A,int

14、S);/*入栈操作*/void POP();/*出栈操作*/void SHITF();/*移入操作*/void REDUCE();/*规约操作*/void ACC();/*接受操作*/ void ERROR();/*错误处理*/void E1();/*错误处理*/void E2();void E3();2.源程序代码#include#include#includeint symbol,status;/*移入或规约时压入分析栈的符号、移入或规约操作后转而进入的状态*/int analysis_stack 50;/*定义分析栈*/int ip = -1;/*ip为栈顶元素下标*/char buff

15、er30;/*将输入符号串w保存于数组中*/int code30;/*将读入的字符串转换为代号形式*/int position = 0;/*position为code数组的下标*/int X;/*X为当前获取的输入符号的代号*/int flag = 1;/*循环标志*/typedef struct/*定义文法产生式的结构*/ int Vn;/*文法产生式的左部非终结符的代码*/ int Str4;/*文法产生式右部的代码串*/ int size;/*文法产生式右部的长度*/G;G production11 = /*该文法的所有产生式*/ 0, 101,0,102,1,/*S - E*/ 102

16、,0,102,3,103,3,/*E - E+T*/ 102,0,102,4,103,3,/*E - E-T*/ 102,0,103,1,/*E - T*/ 103,0,103,5,104,3,/*T - T*F*/ 103,0,103,6,104,3,/*T - T/F*/ 103,0,104,1,/*T - F*/ 104,0,7,1,/*F - id*/ 104,0,1,101,2,3,/*F - (E)*/ 104,0,8,1,/*F - num*/;int GOTO175 = /*LR分析表goto*/ 0,0,1,2,3,/*0*/ 0,0,0,0,0,/*1*/ 0,0,0,0,

17、0,/*2*/ 0,0,0,0,0,/*3*/ 0,0,0,0,0,/*4*/ 0,0,11,2,3,/*5*/ 0,0,0,0,0,/*6*/ 0,0,0,12,3,/*7*/ 0,0,0,13,3,/*8*/ 0,0,0,0,14,/*9*/ 0,0,0,0,15,/*10*/ 0,0,0,0,0,/*11*/ 0,0,0,0,0,/*12*/ 0,0,0,0,0,/*13*/ 0,0,0,0,0,/*14*/ 0,0,0,0,0,/*15*/ 0,0,0,0,0/*16*/;int ACTION179 = /*LR分析表action*/ 51,5,52,51,51,51,51,4,6,/

18、0 999,53,52,7,8,0,0,53,53,/1 -4,53,-4,-4,-4,9,10,53,53,/2 -7,0,-7,-7,-7,-7,-7,0,0,/3 -8,0,-8,-8,-8,-8,-8,0,0,/4 0,5,52,51,51,51,51,4,6,/5 -10,0,-10,-10,-10,-10,-10,0,0,/6 51,5,52,51,51,51,51,4,6,/7 51,5,52,51,51,51,51,4,6,/8 51,5,52,51,51,51,51,4,6,/9 51,5,52,51,51,51,51,4,6,/10 0,53,16,7,8,0,0,53,5

19、3,/11 -2,53,-2,-2,-2,9,10,53,53,/12 -3,53,-3,-3,-3,9,10,53,53,/13 -5,0,-5,-5,-5,-5,-5,0,0,/14 -6,0,-6,-6,-6,-6,-6,0,0,/15 -9,0,-9,-9,-9,-9,-9,0,0/16;void TRANS();/*将读入的buffer数组内容按字符转换为相应代号存入code数组中*/void GetFromCode();/*取得当前输入符号串的元素*/void PUSH(int A,int S);/*入栈操作*/void POP();/*出栈操作*/void SHITF();/*移入操作*/void REDUCE();/*规约操作*/void ACC();/*接受操作*/ void E1();/*错误处理*/void E2();void E3();main() int c=1; printf(请输入表达式,并以$结尾。例如：a+b$n); scanf(%s,buffer);/*读入算术表达式，保存至buffer中*/ print