西理工编译原理试题集1-7(9)

L → L,S | S

ⅰ.消除左递归，若有左因子则提取之；

ⅱ.对（1）中得到的文法求First集合和Follow集合 ⅲ.对（1）中得到的文法构造一个预测分析表； ⅳ.给出对句子(a,(a,a))上的分析动作

1.答案：将所给文法消除左递归得G′： S → (L) | a L → SL′

L′ → ,SL′ |?

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

根据文法G′有

FIRST(S) = { ( , a } FOLLOW(S) = {#, ) , ′,′- FIRST(L) = { ( , a } FOLLOW(S) = { ) } FIRST(L′) = ,′,′ , ?} FOLLOW(L′) = , ) } 按以上结果，构造预测分析表M如下： 非终结符号 S L L′ 输入符号 ( ) , a S → a # S →( L ) L → SL′ L →SL′ L′ →? L′ → ,SL′ 文法G′是LL(1)的，因为它的分析表不含多重定义入口。 预测分析器对输入符号串(a, (a, a))做出的分析动作如下： 栈 $S $)L( $)L $)L′S $)L′a $)L′ $)L′S, $)L′S $)L′)L( $)L′)L $)L′)L′S $)L′)L′a $)L′)L′ $)L′)L′S, $)L′)L′S $)L′)L′a $)L′)L′ $)L′) 输入 (a, (a, a)) (a, (a, a))$ a, (a, a))$ a, (a, a))$ a, (a, a))$ , (a, a))$ , (a, a))$ (a, a))$ (a, a))$ a, a))$ a, a))$ a, a))$ , a))$ , a))$ a))$ a))$ ))$ ))$ 输出 $ S → (L) L → SL′ S → a L′ → , SL′ S → (L) L → SL′ S → a L′ → ,SL′ S → a L′ →? $)L′ $) $ )$ )$ $ L′ →?

2. 考查文法G(s):

S→( T ) | a + S | a T→T, S | S

ⅰ. 消除文法的左递归，提取公共左因子 ⅱ. 改造后的文法是LL(1)的吗？为什么？

ⅲ. 如果是LL(1)文法，对每个非终结符，写出不带回朔的递归子程序。

2.答案：

ⅰ.消除文法的左递归G ( s )：

S→ ( T ) | a + S | a T→ S T′ T`→ , S T′| ?

再提取公共左因子，最后得到改造后的文法G[S]:

①S→( T ) | a S′ ②S′→ + S | ? ③T→ S T′ ④T′→, S T′ | ? ⅱ.

First(S)={(，a }； Follow(S)={#，‘,’}； First(S’)={＋，ε}； Follow(S’)= {#，‘,’}； First(T)={(，a }； Follow(T)={ ) }； First(T’)=,‘,’ ，ε}; Follow(T’) ={ ) }；

产生式①的两个候选的First集合： Fist(（T）)=｛（｝，First(aS’)={a} 不相交，满足条件。

产生式②，First(S’)∩ Follow(S’)=?； 产生式④，First(T’)∩ Follow(T’)=?；

所以，改造后的文法是LL(1)的， ⅲ.

我们构造不带回溯的递归子程序如下： ①S→( T ) | a S′

PROCEDURE S; DEGIN

IF SYM=′( ′THEN BEGIN

ADVANCE T;

IF SYM=′ ) ′THEN ADVANCE ELSE ERROR END

ELSE IF SYM=′a′ THEN BEGIN

ADVANCE; END

ELSE ERROR END;

②S′→ + S | ? PROCEDURE S′; BEGIN

IF SYM=′ + ′THEN BEGIN ADVANCE;S END END;

③T→ S T′ PROCEDURE T; BEGIIN S; T ′ END;

④T′→, S T′ | ? PROCEDURE T′; BEGIN

IF SYM=′ , ′ THEN BEGIN

ADVANCE; S; T′ END END;

3. 已知文法G[S]：

S → uBDz B → Br | w D → EF E → y | ? F → x | ?

(a) 求每个非终结符的FIRST和Follow集。 (b) 构造这个文法的LL(1)分析表 (c) 说明这个文法不是LL(1)的;

(d) 尽可能少地修改此文法,使其成为能产生相同语言的LL(1)文法. 3. 答案：

(a) FIRST(S) = { u } FOLLOW(S) = {#} FIRST(B) = {w } FOLLOW(B) = { r, z } FIRST(D) = { x, y, ?} FOLLOW(D) = { z }

FIRST(E) = { y, ?} FOLLOW(E) = { x, z } FIRST(F) = { x, ? } FOLLOW(F) = { z }

(b) 该文法的LL(1)分析表为：

非终结符 u S B D E F

(c) 因为M[B, w]有两个产生式 B→Bv, B→w 且FIRST(Bv)=FIRST(w) = { w } 所以不是LL(1)的。

(d) 消除左递归即可。 S→uBDz B→wB′ B′→rB′ | ? D → EF

E = y | ? F = x | ?

4. 已知文法如下： E→T | E+T T→F | T*F F→i | (E)

构造预测分析表，并给出对输入串i*i+i的分析过程。

4.答案：

首先消除左递归，得到新文法如下： E→TE′ E′→+TE′|ε T→FT′ T′→*FT′|ε F→(E)|i

对每个非终结符构造First和Follow集合：

FIRST(E) = FIRST(T) = FIRST(F) = { ( , i }；FIRST(E′) = , + , ε-；FIRST(T′) = , * , ε- FOLLOW(E) = FOLLOW(E′) = , ) , # -；FOLLOW(T) = FOLLOW(T′) = , + ，) ，# } FOLLOW(F) = { * , + , ) , # }

再通过对文法的每个非终结符的任意候选都构造出First集合：

FIRST(TE′)= ,(,i-； FIRST(+TE′)=,+- ；FIRST(FT′)=,(,i-；FIRST(*FT′)=,*-； FIRST(（E）)={(} 得到预测分析表如下：

z r w x y # S→uBDz B→Br B→w E→y F→x D→EF D→EF E→? F→? D→EF D→EF E→?

E E→TE′ E→TE′

E′ E′→+TE′ E′→ ? E′→ ?

T T→FT′ T→FT′

T′ T′→ ? T′→*FT′ T′→ ? T′→ ? F F→i F→(E) i + * ( ) # 对输入串的分析过程如下：

5. 文法G1：

S→a|^|(T) T→T,S|S

(1) 证明文法G是LL(1)文法。 (2) 构造LL(1)分析表。

(3) 写出句子（a,a）#的分析过程。

5. 答案：

（1）先消除左递归，得到文法G2： 0) S→a 1) S→^ 2) S→( T ) 3) T→S N2 4) N2→, S N2 5) N2→ε

求非终结符的First和Follow集合：