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

S T N2

FIRST { a，^，( } { a，^，( } { ,，ε -

FOLLOW { #，,，) } { ) } { ) }

对左部为N2的产生式可知： FIRST （, S N2）={，} FIRST （ε）=,ε-

FIRST(, S N2) ∩ FIRST(ε)=?;

且：FIRST(N2) ∩ FOLLOW(N2)= ? 所以文法是LL(1)的。

得到预测分析表 ： a ^ ( ) , # S S→a S→^ S→( T ) T T→SN2 T→SN2 T→SN2 N2 N2→ε N2→,SN2

也可由预测分析表中无多重入口判定文法是LL(1)的。 对输入串（a,a）#的分析过程为： 分析栈 输入串 所用产生式 #S a,a)# #)T( #)T #)N2S #)N2a #)N2 #)N2S, #)N2S #)N2a #)N2 #) # a,a)# ,a)# ,a)# ,a)# a)# a)# )# )# # # # S→(T) T→SN2 S→a N2→,SN2 S→a N2→ε 可见输入串（a,a）#是文法的句子。

6. 设文法G(S)：

S→(L)|aS|a L→L,S|S (1)消除左递归和提取左因子；

(2)计算每个非终结符的FIRST和FOLLOW； (3)构造预测分析表。

(4)已知输入串(aa,a)a，该输入串是否文法的句子？给出分析过程。

7. 对于文法

bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor

bfactor→ not bfactor | (bexpr) | true | false 构造一个预测分析器(表)。

答案：

消除左递归和提取左因子

bexpr → bterm bexpr′

bexpr′ → or bterm bexpr′ | ? bterm → bfactor bterm′

bterm′ → and bfactor bterm′ | ?

bfactor→ not bfactor | (bexpr) | true | false

First(bexpr)=First(bterm)=First(bfactor)={ not, (, true,false } First(bexpr′)=, or , ? } First(bterm′)=, and, ? }

Follow(bexpr)=Follow(bexpr′)=, ) , $ - Follow(bterm)=Follow(bterm′)=,or , ) , $- Follow(bfactor)={and , or, ) , $}

8. 已知G[R]的产生式如下: R → R′ | ′T | T T → TF | F F → F* | C C → (R) | a | b

构造它的LL(1)分析表，并写出对输入串a|ba*的分析过程。

答案：

①消除上面文法中的左递归

R → TR′

R′ → ′|′ TR′ | ε T → FT′ T′ → FT′ | ε F → CF′ F → *F′ | ε C → (R) | a | b

②计算FIRST(α)和FOLLOW(A)

③构造LL(1)分析表。

9. 已知文法如下：

S→S*T | S/T | T T→T+F | T-F | F F →(S) | i | i e i

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

10. 已知文法：

S→Ac|c A→Bb|b B→Sa|a 构造预测分析表，给出对输入串cabc的分析过程。

11. 已知文法G： S → ( L | a L → S , L | )

（1）构造文法 G 的预测分析表。 （2）若输入串为“（ａ，）”，请给出语法分析过程。

解（１）

1）求各非终结符的 FISRT 集和 FOLLOW 集： FIRST(S) = { (, a ) FIRST(L) = { a }? FIRST(S) = { (, ), a }

FOLLOW(S) = , ′,′, # - FOLLOW(L) = FOLLOW(S) =, ′,′, # - 2）预测分析表： ( a , } # S S→ ( L S→ a L L→ S , L L→ S , L L → ) （２）对输入串 “（ａ，）”的分析处理过程如表1所示。 表1 对输入串 “（ａ，）”的分析过程

步骤 分析栈 输入串 ０ １ ２ ３ ４ ５ ６ ７ ８ ＃Ｓ ＃L( ＃L ＃L, a ＃L, ＃L ＃） ＃ 所用产生式 （ａ，）＃ （ａ，）＃ S → ( L ａ，）＃ ａ，）＃ ，）＃ ）＃ ）＃ ＃ L → S , L S→a L → ) ＃L, S ａ，）＃

12. 给定文法

Ｇ＝({ i，d，′(′，′)′ }，{Ｅ，Ａ}，Ｅ，Ｐ) 其中 Ｐ：

E →iA E →EA A → i A →d A → (E)

(1)消除左递归；

(2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集； (3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?。 解

(1)消除左递归后的文法为: E → iAE′

Ｅ′→ ? | AE′ A → i A →d A → ( E )

(2)各非终结符的 FISRT集和FOLLOW集 FIRST( E ) ={i}

FIRST(E′) = ,i, d, (, ?) FIRST( A ) ={i, d, () FOLLOW( E ) ={?, # } FOLLOW(E′) =, -, # -

FOLLOW( A ) ={i, d, (, ), # }

(3)改写后文法的预测分析表： E i d ( ) # E→iAE′ A→d E′ E′→AE′ E′→AE′ E′→AE′ E →? E→ ? A A→i A→ (E) 预测分析表中无多重入口,因此该文法是 LL(1) 文法.

13. 已知文法： A→aABe|a B→Bb|d

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

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

答案：

改写文法为： 0) A→a N3 1) N3→A B e 2) N3→ε 3) B→d N2 4) N2→b N2 5) N2→ε

A B FIRST FOLLOW {a} {d} {#,d} {e} {e} {#,d} N2 {b,ε} N3 {ε,a}

Predicting Analysis Table

A B a A→a N3 e b d # N3→ε B→d N2 N3→ε N2 N2→ε N2→b N2 N3 N3→A B e

由预测分析表中无多重入口判定文法是LL(1)的。

14. 已知文法：

S→Aa|b A→SB