(整理完)编译原理网上作业题参考答案20121101

试构造相应的LR（0）项目集规范族及相应的分析表。（﹡﹡﹡） 解答：

11. 已知文法G[S]，其产生式如下：

S→(L)|a L→ L，S|S

从G[S]中消除左递归，并为之构造一个非递归预测分析器LL(1)分析表。请说明在句子(a，(a，a))上的分析器的动作。 （﹡﹡﹡） 答：

将所给文法消除左递归得G'： S →(L)|a L → SL' L'→ ，SL' | ε

实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表： 根据文法G'有

FIRST(s) = { ( , a ) FIRST(L) = { ( , a ) FIRST(L’) = { ', ' }

按以上结果，构造预测分析表M如下：

文法G’是LL(1)的，因为它的LL(1)分析表不含多重定义入口。 预测分析器对输入符号串(a, (a, a))做出的分析动作如下：

FOLLOW(S) = { ) , ', ' , $ } FOLLOW(L) = { ) } FOLLOW(L’) = { ) }

12. 证明下面文法是SLR(1)文法，并构造其SLR分析表。

E→E+T|T T→TF|F F→F*|a|b 答：

该文法的拓广文法G'为

(0) E' → E (1) E → E+T (2) E → T (3) T → TF (4) T → F (5) F → F* (6) F → a

(7) F → b

其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下: I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I1 = {E'→E·, E→E·+T}

I2 = {E→T·, T→T·F, F→·F*, F→·a, F→·b} I3 = {T→F·, F→F·*} I4 = {F→a·}

（﹡﹡﹡） I5 = {F→b·}

I6 = {E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I7 = {T→TF·, F→F·*} I8 = {F→F*·}

I9 = {E→E+T·, T→T·F, F→·F*, F→·a, F→·b}

求FOLLOW集：

FOLLOW(E)={＋, ＄} FOLLOW(T)={＋, ＄, a, b} FOLLOW(F)={＋, ＄, a, b, *} 构造的SLR分析表如下：

显然，此分析表无多重定义入口，所以此文法是SLR文法

第五章 语法制导翻译技术和中间代码生成

多项选择题：