给定文法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中的一个符号。语法树是句子结构的图形表示，它代表了句子的推导结果，有利于理解句子语法结构的层次。简单说，语法树就是按照某一规则进行推导时所形成的树。