給定文法GSSgtbTc

⑴ 2． 給定文法G=（{E}，{+，*，i,(,)},P,E）,其中P為 E->E+E E->E*E E->(E) E->i

i*i+i
最左推導 E->E*E->i*E->i*E+E->i*i+E->i*i+i
最右推導 E->E+E->E+i->E*E+i->E*i+i->i*i+i

是否有二義性看能否畫出兩種語法樹（i*i+i有二義性）

⑵ 給定文法G=（{S,L}，{a，（，）}，{S→(L)|a L→L,S|S}，S）。給出句型「(S,(a))」的推導和語法樹.

（1）S→(L)|aS』 S』→S|εL→SL』 L』→SL』|ε

（2）FIRST和FOLLOW FIRST)S)＝{(，a} FOLLOW(S)＝{#，，，)} FIRST(S』)＝{，a,ε} FOLLOW(S』)＝{#，，，)} FIRST(L)＝{(，a} FOLLOW(L)＝{ )} FIRST(L』)＝{，，ε} FOLLOW(L』〕＝{ )}

例如：

消除回溯：提取左公因子a，（註：用e代表一補西農符號，就是反三的那個符號，在電腦上不知道怎麼打那個符號）

S→aS'|(L)

S'→S|e

消除左遞歸：

L→SL'

L'→,SL'|e (注意S前面有一個符號「,」)

(2)給定文法GSSgtbTc擴展閱讀：

給定文法G=(Vn,Vt,P,S)，對於G的任何句型都能構造與之關聯的語法樹(推導樹)。樹中的每一個節點都有一個標記，此標記是V= Vn∪Vt中的一個符號。語法樹是句子結構的圖形表示，它代表了句子的推導結果，有利於理解句子語法結構的層次。簡單說，語法樹就是按照某一規則進行推導時所形成的樹。