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

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

一．问题描述

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

E-E+T|E-T|T

T-T*F|T/F|F

F-id|(E)|num

实验要求：

在对输入表达式进行分析的过程中，输出所采用的产生式。

编写语法分析程序实现自底向上的分析，要求如下：

构造识别所有活前缀的DFA。

构造LR分析表。

编程实现算法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)=