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

第5章 习题1. 设有文法G[S]: S→a | ε | ( T ) T→T b S | S说明：其中，终结符号集 = {a, b , ( , )}。(1) 将文法G[S]改写为LL(1)文法。(2) 构造改写后的文法的递归子程序(给出流程图即可) 。解：(1) 改写的LL(1)文法为S→a | ε | ( T ) T→S { b S}(2) 构造的文法的递归子程序（主程序略去，请参考课件）：S对应的子程序：T对应的子程序：2. 计算下列文法中每个产生式的select集，并判断文法是否是LL(1)文法，如果是，给出LL(1)分析表，并给出输入串 aebdee# 的分析过程。G[S]：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)={a}Select(2)=first(d)={d}Select(3)=first(BSD)={a,c,d}Select(4)=first(e)={e}Select(5)=first(Sac)={a,d}Select(6)=first(cD)={c}Select(7)=follow(B)={a,d}Select(8)=first(Se)={a,d}Select(9)=follow(D)={a,b,c,d,e}select(5)∩select(7)={a,d}所以所以不是LL（1）文法3. 对下面的文法G[S] 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附加题：设有文法G[S]: S-A A-B | AiB B-C | B+C C- )A* | ( (1) 将文法G[S]改写为LL(1)文法。 (2) 求经改写后的文法的每个非终结符的FIRST集和FOLLOW集。 (3) 构造相应的LL(1)分析表，并给出输入串 (+)(*# 的分析过程。解答：(1) 原文法有左递归，利用A-A|可以化为A-A`A`-A`|可以得到，原文法可以化为G`(S)：S-AA-BA`A`-iBA`|B-CB`B`-+CB`|C-)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` ③ | ④B-CB` ⑤B`-+CB` ⑥ | ⑦C-)A* ⑧ |( ⑨根据每个非终结符的FIRST集和FOLLOW集，可以得到各产生式的select集如下：select(①)=first(A) ={), (