自底向上语法分析器实验报告
一．问题描述
编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。
E -> E+T | E-T | T T -> T*F | T/F | F F -> id | (E) | num 实验要求：
在对输入表达式进行分析的过程中，输出所采用的产生式。 编写语法分析程序实现自底向上的分析，要求如下： （1） 构造识别所有活前缀的DFA。 （2） 构造LR分析表。
（3） 编程实现算法4.3，构造LR分析程序。
二．算法思想
1.大体步骤：
（1）根据题目所给出的文法构造相应的拓广文法，并求出该文法各非终结符的FIRST、FOLLOW集合；
（2）.构造拓广文法的项目集规范族，并构造出识别所有前缀的DFA； （3）构造文法的LR分析表； （4）由此构造LR分析程序。
2.数据结构：
1.输入缓冲区为一个字符型数组，读入输入的算术表达式并保存在此，以’$’结束； 2.构建一个相对应的整型数组，将输入缓冲区中的字符转换为相应的代号并保存； 3.构造一个结构体，以保存文法的某个产生式，该结构包括三个元素：整形变量，保存产生式左部非终结符代号。整型数组，保存产生式右部字符串的代号。整型变量，保存产生式右部长度；
4.定义该结构的数组，保存文法的所有产生式；
5.定义两个二维整形数组，goto和action，其值大于零代表移进操作，小于零代表规约操作，引进的状态或规约用到的产生式又绝对值表示。等于零代表出现错误。等于特殊值999代表acc.状态。
3.计算过程：
文法对应的拓广文法为： 1 S->E 2 E -> E+T 3 E -> E-T
4 E -> T 5 T -> T*F 6 T -> T/F 7 T -> F 8 F -> (E) 9 F -> id 10 F -> num
求的各个非终结符的FIRST、FOLLOW集合为： FIRST(S) = { id, num, ( } FOLLOW (S) = { $ } FIRST(E) = { id, num, ( } FOLLOW (E) = { $ , + , - , ) } FIRST(T) = { id, num, ( } FOLLOW (T) = { $ , + , - , * , / , ) } FIRST(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({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({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, 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分析表：
goto[0,E] = 1;goto[0,T] = 2;goto[0,F] = 3;
action[0,id] = S4;action[0,(] = S5;action[0,num] = S6;
action[1,$] = ACC.;action[1,+] = S7;action[1,-] = S8; ;
action[2,)] = action[2,+] = action[2,-] = action[2,$] = R4; action[2,*] = S9;action[2,/] = S10;
action[3,)] = action[3,+] = action[3,-] = action[3,*] = action[3,/] = action[3,$] = R7;
action[4,)] = action[4,+] = action[4,-] = action[4,*] = action[4,/] = action[4,$] = R8;
goto[5,E] = 11;goto[5,T] = 2;goto[5,F] = 3;
action[5,id] = S4;action[5,(] = S5;action[5,num] = S6;
action[6,)] = action[6,+] = action[6,-] = action[6,*] = action[6,/] = action[6,$] = R10;
goto[7,T] = 12;goto[7,F] = 3;
action[7,id] = S4;action[7,(] = S5;action[7,num] = S6;
goto[8,T] = 13;goto[8,F] = 3;
action[8,id] = S4;action[8,(] = S5;action[8,num] = S6;
goto[9,F] = 14;
action[9,id] = S4;action[9,(] = S5;action[9,num] = S6;
goto[10,F] = 15;
action[10,id] = S4;action[10,(] = S5;action[10,num] = S6;
action[11,)] = S16;action[11,+] = S7;action[11,-] = S8;
action[12,)] = action[12,+] = action[12,-] = action[12,$] = R2;action[12,*] = S9;action[12,/] = S10;
action[13,)] = action[13,+] = action[13,-] = action[13,$] = R3;action[13,*] = S9;action[13,/] = S10;
action[14,)] = action[14,+] = action[14,-] = action[14,*] = action[14,/] = action[14,$] = R5;
action[15,)] = action[15,+] = action[15,-] = action[15,*] = action[15,/] = action[15,$] = R6;
action[16,)] = action[16,+] = action[16,-] = action[16,*] = action[16,/] = action[16,$] = R9;
4.SLR(1)分析表为：
E1:缺少运算对象。认为加入一个Id入栈并转移至相应状态 E2: 括号不匹配删掉右括号，则删去右括号并转移至相应状态 E3: 缺少运算符，添加运算符并转移至相应状态 action goto
( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
s5 E3 E3 s5 E3 s5 s5 s5 s5 E3 E3 E3
) E2 E2 r4 r7 r8 E2 r10 E2 E2 E2 E2 s16 r2 r3 r5 r6 r9
+ E1 s7 r4 r7 r8 E1 r10 E1 E1 E1 E1 s7 r2 r3 r5 r6 r9
- E1 s8 r4 r7 r8 E1 r10 E1 E1 E1 E1 s8 r2 r3 r5 r6 r9
* E1 s9 r7 r8 E1 r10 E1 E1 E1 E1 s2 s9 r5 r6 r9
/ E1 s10 r7 r8 E1 r10 E1 E1 E1 E1 s2 s10 r5 r6 r9
id s4 E3 E3 s4 s4 s4 s4 s4 E3 E3 E3
num $ s6 E3 E3 s6 s6 s6 s6 s6 E3 E3 E3
E1 Acc. r4 r7 r8 r10 r2 r3 r5 r6 r9
E 1 11
T 2 2 12 13
F 3 3 3 3 14 15
三、实验程序设计说明
1.主要函数说明
void TRANS();/*将读入的buffer数组内容按字符转换为相应代号存入code数组*/ void GetFromCode();/*取得当前输入符号串的元素*/ void PUSH(int A,int S);/*入栈操作*/ void POP();/*出栈操作*/ void SHITF();/*移入操作*/ void REDUCE();/*规约操作*/ void ACC();/*接受操作*/ void ERROR();/*错误处理*/
void E1();/*错误处理*/ void E2(); void E3();
2.源程序代码
#include