内容发布更新时间 : 2024/5/18 21:07:11星期一 下面是文章的全部内容请认真阅读。

自底向上语法分析器实验报告

一．问题描述

编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。

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 #include