编译原理复习题 - 给学生(2014)

.. .. ..

8．令文法G[N]为 G[N]: N→D|ND

D→0|1|2|3|4|5|6|7|8|9

给出句子568的最左、最右推导。

解：最左推导：N ? ND ? NDD ? DDD ? 5DD ? 56D ? 568

最右推导：N ? ND ? N8 ? ND8? N68 ? D68 ? 568 8．已知文法G[A]: A→aABl|a

B→Bb|d

试给出与G[A]等价的LL(1)文法G[A′]；

解：G[A′]：A→aA′

A′→ABl | ε B→dB′ B′→bB′| ε

9．试构造下述文法的SLR(1)分析表。

G[A]: A→aABl|a

B→Bb|d

解：拓广文法 （0）S→A

（1）A→aABl （2）A→a （3）B→Bb （4）B→d

参考材料

.. .. ..

I0：S→．A A→．aABl a A→．a I1：S→A． I2：A→a．ABl A A→a． A→．aABl A→．a I3： A→aA．Bl d B→．Bb B→．d B I4：B→d． a I5： A→aAB．l B→B．b b I7： B→Bb． l I6： A→aABl． First（A）={a}follow（A）={#，d} First（B）={d}follow（B）={l} SLR（1）分析表如下： 0 1 2 3 4 5 6 7 a S2 S2 b S7 d R2 S4 R1 l R4 S6 R3 # ACC R2 R1 A 1 3 B 5 10. 试构造下述文法的LL(1)分析表。

G[S]: S→（L）|a

L→L，S|S

参考材料

.. .. ..

解：消除左递归：

构造FIRST集，如下：

（1）FIRST(S) = {(, a} （2）FIRST(L) = {(, a} （3）FIRST(L’) = {,, ε}

构造FOLLOW集如下： （1）FOLLOW(S) = {#, ,, )} （2）FOLLOW(L) = {)} （3）FOLLOW(L’) = {)}

LL(1)分析表

S L L’

11．已知文法G[S]: S→aSbS|bSaS|ε

试证明G[S]是二义文法

( S ? (L) L ? SL’ ) L’ ? ε a S ? a L ? SL’ , L’ ? ,SL’ # G(S): S ? (L) | a L ? SL’ L’ ? , SL’| ε

参考材料

.. .. ..

证明： 该文法产生的语言是a的个数和b的个数相等的串的集合。该文法二义，例如句子abab有两种不同的最左推导。

S?aSbS?abS?abaSbS?ababS?abab S?aSbS?abSaSbS?abaSbS?ababS?abab

12．已知文法Ｇ： S → ( L | a L → S , L | )

判断是不是LL（1）文法，如果是请构造文法 Ｇ 的预测分析表，如果不是请说明理由。 【解】

1）求各非终结符的 FISRT 集和 FOLLOW 集：

First（S）= { (, a }

FIRST(L) = { ） }? FIRST(S) = { (, ), a } FOLLOW(S) = {, # }

FOLLOW(L) = FOLLOW(S) ={ , # } FIRST(( L)∩{a}=Φ FIRST(S , L)∩{)}=Φ 所以是LL（1）文法

2）预测分析表： S L

参考材料

( S→ ( L L→ S , L a S→ a L→ S , L , } L → ) #