编译原理第3章文法和语言(11)

(((a,a),∧,(a)),S) (((a,a),∧,(a)),a) (2)改写文法为： 0)S→a 1)S→∧ 2)S→(T) 3)T→S N 4)N→,S N 5)N→ε 非终结符 FIRST集 FOLLOW集 S

{a,∧,(} {#,,,)} T

{a,∧,(} {)}.... N {,,ε}. {)}....

对左部为N的产生式可知： FIRST（→,S N）={，} FIRST（→ε）={ε} FOLLOW（N）={)}

由于SELECT(N→,S N)∩SELECT(N→ε)={，}∩{)}= 所以文法是LL(1)的。

预测分析表（Predicting Analysis Table） a ∧ ( ) , # S →a →∧ →(T) T →S N →S N →S N N

→ε →,S N

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

(3)对输入串（a,a）#的分析过程为： 栈（STACK） 当前输入符

（CUR_CHAR） 剩余输入符

（INOUT_STRING） 所用产生式

（OPERATION） #S #)T( #)T #)NS #)Na #)N #)NS, #)NS #)Na #)N #) # ( ( a a a , , a a ) ) #

a,a)#... a,a)#... ,a)#... ,a)#... ,a)#... a)#... a)#... )#... )#... #... #...

S→(T) .

T→SN S→a .

N→,SN . S→a .

N→ε

可见输入串（a,a）#是文法的句子。

第3题

已知文法G[S]： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM

判断G是否是LL(1)文法，如果是，构造LL(1)分析表。 答案：

文法展开为： 0）S→M H 1）S→a 2）H→L S o 3）H→ε 4）K→d M L 5）K→ε 6）L→e H f 7）M→K 8）M→b L M 非终结符 FIRST集 FOLLOW集 S

{a,d,b,ε,e} {#,o}........ M

{d,ε,b}.... {e,#,o}...... H

{ε,e}...... {#,f,o}...... L

{e}......... {a,d,b,e,o,#} K

{d,ε}...... {e,#,o}......

对相同左部的产生式可知：

SELECT(S→M H)∩SELECT(S→a)={d,b,e，#,o}∩{a}= SELECT(H→L S o)∩SELECT(H→ε)={e}∩{#,f,o}= SELECT(K→d M L)∩SELECT(K→ε)={d}∩{e,#,o}= SELECT(M→K)∩SELECT(M→b L M)={d，e,#,o}∩{b}= 所以文法是LL(1)的。