（1）消除G的左递归得到文法 G‘

E→TE ' E'→+TE'│ε T→FT ' T'→*FT'│ε F→(E)│i

（2）求出每个产生式的select集,G’是LL(1)文法

SELECT(E→TE' ) = { (,i } SELECT(E'→ε ) = { ),# } SELECT(T'→*FT' ) = { * } SELECT(F→(E) ) = { ( } SELECT(E'→+TE' ) = { + } SELECT(T→FT' ) = { (,i } SELECT(T'→ε ) = { +,),# } SELECT(F→ i ) = { i }

（3）依照选择集合把产生式填入分析表

注：表中空白处为出错

题目2：作业、习题5.1：消除左递归+判定+分析 G[S]:S->a|^|(T) T->T,S|S d、分析输入串（a,a）#

文法G[S]:S->a|^|(T)，T->T,S|S

(1) 给出对(a,(a,a))的最左推导 (2) 改写文法，去除左递归

(3) 判断新文法是否LL1文法，如是，给出其预测分析表

(4) 给出输入串（a,a）#的分析过程，判断其是否文法G的句子 。 答：（1）对(a,(a,a))的最左推导为：

S=>(T)

=>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a))

（2）改写文法为：

5

0) S→a 1) S→? 2) S→(T) 3) T→SN 4) N→,SN 5) N→ε 非终结符 FIRST集 FOLLOW集 S {a,?,(} {#,,,)} T {a,?,(} {)} N {,,ε} {)} 对左部为N的产生式可知： FIRST (→,S N) = {, } FIRST (→ε) ={ε} FOLLOW (N) ={)}

由于SELECT(N→,S N)∩SELECT(N→ε)={, }∩{)}=? 所以文法是LL(1)的。 （3）预测分析表：

a ? ( ) , # S →a →? →(T) T →SN →SN →SN N →ε →,SN 可由预测分析表中，无多重入口判定文法是LL（1）的。 （4）对输入串（a,a）#的分析过程为： 栈 当前输入符 剩余输入符 所用产生式 #S ( a,a)# S→(T) #)T( ( a,a)# #)T a ,a)# T→SN #)NS a ,a)# S→a #)Na a ,a)# #)N , a)# N→,SN #)NS, , a)# #)NS a )# S→a #)Na a )# #)N ) # N→ε #) ) # # # 可见输入串（a,a）#是文法的句子。 题目3：复习、书本5.6例1：判定+分析 G[S]：S→aH，H→aMd|d，M→Ab|ε，A→aM|e d、分析输入串aaabd#

（1）判断G[S]是否为LL（1）文法；若是，构造其预测分析表；

6

Select(H→aMd)={a} , Select(H→d)= {d} ； Select(M→Ab)= {a,e}, Select(M→ε)= {d,b}； Select(A→aM)= {a} , Select(A→e)= {e}

相同左部产生式的select集的交集均为空，所以G[S]是LL（1）文法。 预测分析表：

（2）分析aaabd#是否G[S]的句子。 使用栈和预测分析表对输入串的分析：

7

第6章 自底向上的语法分析 重点内容：算符优先文法

a、 非终结符的firstvt集和lastvt集的计算b、 算符优先关系表

c、 使用栈和算符优先关系表对输入串的归约 题目1：课件例题： 文法：E→E+T|T T→T×F|F

F→(E)|I

c、算符优先归约输入串i+i#

（1）求各非终结符的FIRSTVT集与LASTVT集

（2）计算算符优先关系表并说明此文法是否算符优先文法 （3）给出输入串i+i#的算符优先分析过程

8