蒋立源编译原理第三版第四章习题与答案1

1、4-1 消除下列文法的左递归性。(1) ssa|aa- sb|b|(s)|()b-s川asa|at s|t,ssaab|ba|aaab| ebbb|(2) a as|b a (t)|a|4-2 对于如下文法，求各候选式的 firs磔和各非终结符号的 follow集4-3 验证下列文法是否为 ll(1戊:法。(1) sab|cdaa ab|cbde|c ec|g fd|fe de| e saabbcd|a asd| ebsac|ec| c- sf|cg|dabd| 4-4 对于如下的文法gs：ssb|ab|ba aa|a构造一个与g等价的ll(1)文?fe g s; 对于g s,构造相应的ll(

2、1加析表；利用ll(1汾析法判断符号串aabb是否是文法gs的合法句子。4-5 设已给文法ssab|bba s|abac构造一个与g等价的ll(1)文?fe g s; 对于g s,构造相应的ll(1加析表；利用ll(1汾析法判断符号串bacabc是否是文法gs的合法句子。第 4 章 习题答案4-1 解：(1)文法gs中白s, a都是间接左递归的非终结符号。将a产生式的右部代入产生式sa中，得到与原文法等价的文法gs:ssa|sb|b|(s)|()a- sb|b|(s)|()b-s川文法gs中白s是直接左递归的非终结符号，则消除s产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文

3、法gs：sbs|(s)s( )s s as|bs &a- sb|b|(s)|()b-s川(2)文法gs中白s, a都是间接左递归的非终结符号。将a产生式代入产生式sas中，得到与原文法等价的文法gs:ssas|as|ba sa|a文法gs中白s是直接左递归的非终结符号，则消除s产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法gs：sass|bss ass| &a sa|a(3)文法gs中白t是直接左递归的非终结符号。则消除t产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法g s:下(t)同&t stt st 1 4-2 解：文法gs的各候选式的firs咪

4、和各非终结符号的 follow集如答案表4-2所示。答案表4-2 文法gs的各个firs磔和follow集产生式firstfollowsaabasfbab#s- a aabab,#a 一 ebf bbb#b e 4-3 解：(1)因为d产生式的两个候选式fd和f的firs琛交集为f,不为空，所以该文法不 是 ll(1w。(2)因为文法中含有左递归的非终结符号a,故此文法具有左递归性，不是ll(1*h4-4 解：(1)文法中含有直接左递归的非终结符号s和a,则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法g s:sabs |bss贵 | a aa，a -aa | e文法g s的

5、各候选式的firs磔和各非终结符号的follow集如答案表4-4-(1)所示:答案表4-4-(1) 文法g s的各个firs磔和follow集产生式firstfollowsabssbsab#s七ss弋b #a 一 aaaba -aa,a弋a b下面来验证文法 g s是否是ll(1)文法。对于文法 g s,因为有:对于产生式 s abs|bs ；有 first(absq first(bs =总0 b二；对于产生式 s城| 有 first(bsq follow(s =ba#二；对于产生式 a -aa| 有 first(aar)follow(a =an b二；所以文法g s即为所求的与g等价的ll(

6、1戊:法。(2)文法g s的ll(1方析表如答案表4-4-(2)所示：答案表4-4-(2)文法g s的ll(1分析表ab#ssabssfsss杨s弋aa 一 aaaa囿aa弋对符号串aabb进彳f ll(1汾析的过程如答案表 4-4-(3)所示。答案表4-4-(3)对aabb进彳f ll(1汾析的过程步骤分析栈余留输入串所用产生式1#saabb#sabs2#s baaabb#a-aa3#s ba aaabb#4#s ba abb#a m5#s ba aabb#6#s babb#a弋7#s bbb#8#sb#s hbs，9#s bb#10#s#s建11#分析成功因为分析成功，所以符号串aabb是

7、文法gs的合法句子。4-5 解：(1)文法中含有直接左递归的非终结符号s,则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法g s:s-bbs，s bs| a s|abfac文法g s的各候选式的firs磔和各非终结符号的follow集如答案表4-5-(1)所示:答案表4-5-(1) 文法g s的各个firs磔和follow集产生式firstfollowsbbsb#,cs -abss弋a #,ca 一 sa 一 abacbfaca,b #,a,c下面来验证文法 g s是否是ll(1)文法。对于文法 g s,因为有:对于产生式 s abs| 有 first(absq follow

8、(s =aa #,c二;对于产生式 a一s|a,有 first(s) first(a尸b1a二；所以文法g s即为所求的与g等价的ll(1戊:法。(2)文法g s的ll(1方析表如答案表4-5-(2)所示：答案表4-5-(2)文法g s的ll(1分析表abc#ss bbsss池与s建s,aa一 aa一 sbbfacb-ac 对符号串bacabc进彳f ll(1汾析的过程如答案表 4-5-(3)所示。答案表4-5-(3)对bacabc进彳f ll(1加析的过程步骤分析栈余留输入串所用产生式1#sbacabc#sbbs2#s bbbacabc#3#s bacabc#bf ac4#s caacabc#a-a5#s caacabc#6#s ccabc#7#sabc#s -abs8#s baa