编译原理语法分析题+答案.docx

第5章 习题1. 设有文法GS: Sa | | ( T ) TT b S | S说明：其中，终结符号集 = a, b , ( , )。(1) 将文法GS改写为LL(1)文法。(2) 构造改写后的文法的递归子程序(给出流程图即可) 。解：(1) 改写的LL(1)文法为Sa | | ( T ) TS b S(2) 构造的文法的递归子程序（主程序略去，请参考课件）：S对应的子程序：T对应的子程序：2. 计算下列文法中每个产生式的select集，并判断文法是否是LL(1)文法，如果是，给出LL(1)分析表，并给出输入串 aebdee# 的分析过程。GS：S aAbDe | d A BSD | e B SAc | cD | D Se | 说明：其中，终结符号集 = a, b, c, d, e。解：文法式编号： S aAbDe | d A BSD | e B SAc | cD | D Se | Select(1)=first(aAbDe)=aSelect(2)=first(d)=dSelect(3)=first(BSD)=a,c,dSelect(4)=first(e)=eSelect(5)=first(Sac)=a,dSelect(6)=first(cD)=cSelect(7)=follow(B)=a,dSelect(8)=first(Se)=a,dSelect(9)=follow(D)=a,b,c,d,eselect(5)select(7)=a,d所以所以不是LL（1）文法3. 对下面的文法GS S- Ua | Tb T- Sc | d U- Ub | e (1) 构造文法的句柄识别器。(2) 该文法是LR(0)文法吗？请说明理由。(3) 该文法是SLR(1)文法吗？若是，构造它的SLR(1)分析表，并按下表给出的格式列出符号串 eacb# 的SLR(1)分析过程。分析栈当前单词剩余串操作（1）构造文法的句柄识别器。（2）该文法是LR(0)文法吗？请说明理由。（3） 该文法是SLR(1)文法吗？若是，构造它的SLR(1)分析表，并按下表给出的格式列出符号串 eacb# 的SLR(1)分析过程。分析栈当前单词剩余串操作不是LR(0)文法，在1状态处有移近规约冲突。follow(S)=#与c的交集为空，所以是SLR(1)文法。S- S(0) S- Ua (1)| Tb(2) T- Sc (3)| d (4)U- Ub (5)| e (6)分析表abcde#STU0d9e8S1T6U31c2OK2r(3)r(3)r(3)r(3)r(3)r(3)3a4b54r(1)r(1)r(1)r(1)r(1)r(1)5r(5)r(5)r(5)r(5)r(5)r(5)6b77r(2)r(2)r(2)r(2)r(2)r(2)8r(6)r(6)r(6)r(6)r(6)r(6)9r(4)r(4)r(4)r(4)r(4)r(4)分析栈当前单词剩余串操作#0eacb#push(e8)#0e8acb#r(6)#0U3acb#push(a4)#0U3a4cb#r(1)#0S1cb#push(c2)#0S1c2b#r(3)#0T6b#b7#0T6b7#r(2)#0S1#OK附加题：设有文法GS: S-A A-B | AiB B-C | B+C C- )A* | ( (1) 将文法GS改写为LL(1)文法。 (2) 求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。 (3) 构造相应的LL(1)分析表，并给出输入串 (+)(*# 的分析过程。解答：(1) 原文法有左递归，利用A-Ab|a可以化为A-aAA-bA|e可以得到，原文法可以化为G(S)：S-AA-BAA-iBA|eB-CBB-+CB|eC-)A*|(2) 每个非终结符的FIRST集和FOLLOW集如下： firstFollowS ), ( # A ), ( #, * A i # , * B ), ( i, # ,*B + i,#,* C ), ( +, i ,# ,*其中，follow(B)=first(A)follow(A)= first(A)*follow(S)=i*#(3) 为产生式编号：S-A A-BA A-iBA |e B-CB B-+CB |e C-)A* |( 根据每个非终结符的FIRST集和FOLLOW集，可以得到各产生式的select集如下：select()=first(A) =), (select()= first(B) =), (select()=first(iBA)=iselect()=first(e)follow(A)=#,*select()=first(C)= ), (select()=first(+CB)=+select()= first(e)follow(B)=i,#,*select()=first()A*)=)select()=first()=(根据以上select集，可以得到LL(1)分析表：i+)*(#SAABBC根据以上LL(1)分析表，得出输入串 (+)(*# 的分析过程如下：分析栈当前符号剩余符号查分析表：操作#S(+)(*#: push(A)#A(+)(*#: push(AB)#AB(+)(*#: push(BC)#ABC(+)(*#: push()#AB(+)(*#匹配( next(w)#AB+)(*#: push(BC+)#ABC+)(*#匹配+ next(w)#ABC)(*#:push(*A)#AB*A)(*#匹配) next(w)#AB*A(*#: push(AB)#AB*AB(*#: p