语法分析程序实验报告

需求分析

题目：语法分析程序的设计与实现。

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

E?E?T|E?T|TT?T*F|T/F|F F?id|(E)|num实验要求：在对输入表达式进行分析的过程中，输出所采用的产生式。 方法1：编写LL(1)语法分析程序，要求如下。

(1) 编程实现算法4.2，为给定文法自动构造预测分析表。 (2) 编程实现算法4.1，构造LL(1)预测分析程序。

方法2：编写语法分析程序实现自底向上的分析，要求如下。 (1) 构造识别所有活前缀的DFA。 (2) 构造LR分析表。

(3) 编程实现算法4.3，构造LR分析程序。

概要设计

1. LL(1)语法分析程序 （1）.原文法

E?E?T|E?T|TT?T*F|T/F|FF?id|(E)|num

（2）.消除左递归和回溯

E->TR R->+TR R->-TR R->e T->FW W->*FW W->/FW W->e F->id F->(E) F->num

（3）. FISRT集和FOLLOW集

FIRST(S) = { id, num, ( } FIRST(E) = { id, num, ( } FIRST(T) = { id, num, ( } FIRST(F) = { id, num, ( }

FOLLOW (S) = { $ }

FOLLOW (E) = { $ , + , - , ) }

FOLLOW (T) = { $ , + , - , * , / , ) } FOLLOW (F) = { $ , + , - , * , / , ) }

（4）.LL(1)预测分析表

2. LR实现，自底向上分析 （1）.原文法

E?E?T|E?T|TT?T*F|T/F|FF?id|(E)|num

（2）.文法对应的拓广文法为：

1 2 3 4 5 6 7 8 9

E -> E+T E -> E-T E -> T T -> T*F T -> T/F T -> F F -> (E) F -> id F -> num

（3）. FISRT集和FOLLOW集

FIRST(S) = { id, num, ( } FIRST(E) = { id, num, ( } FIRST(T) = { id, num, ( } FIRST(F) = { id, num, ( }

FOLLOW (S) = { $ }

FOLLOW (E) = { $ , + , - , ) }

FOLLOW (T) = { $ , + , - , * , / , ) } FOLLOW (F) = { $ , + , - , * , / , ) }

（4）.构造项目集规范族

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,