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

自底向上语法分析器实验报告 一．问题描述 编写语法分析程序，实现对算术表达式的语法分析。要求所分析算术表达式由如下的文法产生。 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}) ...