资源描述：
《北邮 编译原理 自底向上语法分析实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、自底向上语法分析器实验报告一．问题描述编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。E->E+T
2、E-T
3、TT->T*F
4、T/F
5、FF->id
6、(E)
7、num实验要求：在对输入表达式进行分析的过程中，输出所采用的产生式。编写语法分析程序实现自底向上的分析，要求如下：（1）构造识别所有活前缀的DFA。（2）构造LR分析表。（3）编程实现算法4.3，构造LR分析程序。二．算法思想1.大体步骤：（1）根据题目所给出的文法构造相应的拓广文法，并求出该文法各非终结符的FIRST、FOLL
8、OW集合；（2）.构造拓广文法的项目集规范族，并构造出识别所有前缀的DFA；（3）构造文法的LR分析表；（4）由此构造LR分析程序。2.数据结构：1.输入缓冲区为一个字符型数组，读入输入的算术表达式并保存在此，以’$’结束；2.构建一个相对应的整型数组，将输入缓冲区中的字符转换为相应的代号并保存；3.构造一个结构体，以保存文法的某个产生式，该结构包括三个元素：整形变量，保存产生式左部非终结符代号。整型数组，保存产生式右部字符串的代号。整型变量，保存产生式右部长度；4.定义该结构的数组，保存文法的所有产生式；5.定义
9、两个二维整形数组，goto和action，其值大于零代表移进操作，小于零代表规约操作，引进的状态或规约用到的产生式又绝对值表示。等于零代表出现错误。等于特殊值999代表acc.状态。3.计算过程：文法对应的拓广文法为：1S->E2E->E+T3E->E-T4E->T5T->T*F6T->T/F7T->F8F->(E)9F->id10F->num求的各个非终结符的FIRST、FOLLOW集合为：FIRST(S)={id,num,(}FOLLOW(S)={$}FIRST(E)={id,num,(}FOLLOW(E)={
10、$,+,-,)}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·+
11、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->·
12、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
13、})={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};
14、从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·};从I
