编译原理龙书答案.docx
- 文档编号:7548410
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:35
- 大小:119.25KB
编译原理龙书答案.docx
《编译原理龙书答案.docx》由会员分享,可在线阅读,更多相关《编译原理龙书答案.docx(35页珍藏版)》请在冰点文库上搜索。
编译原理龙书答案
编译原理龙书答案
————————————————————————————————作者:
————————————————————————————————日期:
第四章部分习题解答
Aho:
《编译原理技术与工具》书中习题
(Aho)4.1考虑文法
S→(L)|a
L→L,S|S
a)列出终结符、非终结符和开始符号
解:
终结符:
(、)、a、,
非终结符:
S、L
开始符号:
S
b)给出下列句子的语法树
i)(a,a)
ii)(a,(a,a))
iii)(a,((a,a),(a,a)))
c)构造b)中句子的最左推导
i)S⇒(L)⇒(L,S)⇒(S,S)⇒(a,S)⇒(a,a)
ii)S⇒(L)⇒(L,S)⇒(S,S)⇒(a,S)⇒(a,(L))⇒(a,(L,S))⇒(a,(S,S))⇒(a,(a,S)⇒(a,(a,a))
iii)S⇒(L)⇒(L,S)⇒(S,S)⇒(a,S)⇒(a,(L))⇒(a,(L,S))⇒(a,(S,S))⇒(a,((L),S))⇒(a,((L,S),S))⇒(a,((S,S),S))⇒(a,((a,S),S))⇒(a,((a,a),S))⇒(a,((a,a),(L)))⇒(a,((a,a),(L,S)))⇒(a,((a,a),(S,S)))⇒(a,((a,a),(a,S)))⇒(a,((a,a),(a,a)))
d)构造b)中句子的最右推导
i)S⇒(L)⇒(L,S)⇒(L,a)⇒(S,a)⇒(a,a)
ii)S⇒(L)⇒(L,S)⇒(L,(L))⇒(L,(L,S))⇒(L,(L,a))⇒(L,(S,a))⇒(L,(a,a))⇒(S,(a,a))⇒(a,(a,a))
iii)S⇒(L)⇒(L,S)⇒(L,(L))⇒(L,(L,S))⇒(L,(L,(L)))⇒(L,(L,(L,S)))⇒(L,(L,(L,a)))⇒(L,(L,(S,a)))⇒(L,(L,(a,a)))⇒(L,(S,(a,a)))⇒(L,((L),(a,a)))⇒(L,((L,S),(a,a)))⇒(L,((L,a),(a,a)))⇒(L,((S,a),(a,a)))⇒(L,((a,a),(S,S)))⇒(S,((a,a),(a,a)))⇒(a,((a,a),(a,a)))
e)该文法产生的语言是什么
解:
设该文法产生语言(符号串集合)L,则
L={(A1,A2,…,An)|n是任意正整数,Ai=a,或Ai∈L,i是1~n之间的整数}
(Aho)4.2考虑文法
S→aSbS|bSaS|ε
a)为句子构造两个不同的最左推导,以证明它是二义性的
S⇒aSbS⇒abS⇒abaSbS⇒ababS⇒abab
S⇒aSbS⇒abSaSbS⇒abaSbS⇒ababS⇒abab
b)构造abab对应的最右推导
S⇒aSbS⇒aSbaSbS⇒aSbaSb⇒aSbab⇒abab
S⇒aSbS⇒aSb⇒abSaSb⇒abSab⇒abab
c)构造abab对应语法树
d)该文法产生什么样的语言?
解:
生成的语言:
a、b个数相等的a、b串的集合
(Aho)4.3考虑文法
bexpr→bexprorbterm|bterm
bterm→btermandbfactor|bfactor
bfactor→notbfactor|(bexpr)|true|false
a)试为句子not(trueorfalse)构造分析树
解:
b)试证明该文法产生所有布尔表达式
证明:
一、首先证明文法产生的所有符号串都是布尔表达式
变换命题形式——以bexpr、bterm、bfactor开始的推导得到的所有符号串都是布尔表达式
最短的推导过程得到true、false,显然成立
假定对步数小于n的推导命题都成立
考虑步数等于n的推导,其开始推导步骤必为以下情况之一
bexpr⇒bexprorbterm
bexpr⇒bterm
bterm⇒btermandbfactor
bexpr⇒bfactor
bfactor⇒notbfactor
bfactor⇒(bexpr)
而后继推导的步数显然 因此命题一得证。 二、证明所有布尔表达式均可由文法生成 变换命题——所有析取式均可由bexpr推导出来,所有合取式均可由bterm(bexpr)推导出来,所有对子布尔表达式施加not运算或加括号或简单true、false都可由bfactor(bexpr、bterm)推导出来 最简单的布尔表达式true和false显然成立 假定对长度小于n的布尔表达式,均可由文法推导出来 考虑长度等于n的布尔表达式B,显然,B只能是以下形式之一 B=B1orB2 B=B1andB2 B=notB1 B=(B1) 以上几种情况,B1、B2的长度均小于n 对于情况1: B为析取式,B1可为析取式也可为合取式,B2为合取式,根据假设可由bexpr合bterm推导出来,显然可构造推导过程,由bexpr推导出B 其他情况类似,命题二得证 综合一、二,可知文法产生的语言就是布尔表达式 c) (Aho)4.4考虑文法 R→R‘|’R|RR|R*|(R)|a|b c)构造等价的非二义性文法 R→R‘|’A|A A→AB|B B→B*|C C→(R)|a|b (Aho)4.5下面if-then-else文法试图消除空悬else的二义性,证明它仍是二义性的 stmt→ifexprthenstmt |matched_stmt matched_stmt→ifexprthenmatched_stmtelsestmt |other 解: 用S、M、E表示stmt、matched_stmt和expr,用i、t、e、o表示if、then、else和other 则句子iEtiEtoeiEtoeo对应两个最左推导: S⇒iEtS⇒iEtM⇒iEtiEtMeS⇒iEtiEtoeS⇒iEtiEtoeM ⇒iEtiEtoeiEtMeS⇒iEtiEtoeiEtoeS⇒iEtiEtoeiEtoeM ⇒iEtiEtoeiEtoeo S⇒M⇒iEtMeS⇒iEtiEtMeSeS⇒iEtiEtoeSeS⇒iEtiEtoeiEtSeS ⇒iEtiEtoeiEtMeS⇒iEtiEtoeiEtoeS⇒iEtiEtoeiEtoeM ⇒iEtiEtoeiEtoeo 因此文法是二义性文法 直接构造比较困难,可从SLR分析表的构造角度考虑,LR(0)项目集规范族中,项目 I8={M→iEtM·eS,S→·M},有移进/归约冲突,这就是是二义性所在。 显然,存在句型...iEtMeS...和...iEtSeS...,当M位于栈顶时,产生移进/归约冲突。 按此思路,构造形如...iEtSeS...的句型即可 (Aho)4.6为下列语言设计上下文无关文法。 哪些语言是正规式? a)满足这样条件的二进制串: 每个0之后都紧跟着至少一个1 S→0A|1S|ε A→1S 正规式: (1|01)* b)0和1个数相等的二进制串 S→0S1S|1S0S|ε d)不含011子串的二进制串 S→0A|1S|ε A→0A|1B|ε B→0A|ε 正规式: 1*(0|01)* e)具有形式xy的二进制串,x≠y S→A|B|AB|BA A→DAD|0 B→DBD|1 D→0|1 A、B分别表示中心符号为0、1的长度为奇数的二进制串 将AB串接,长度为偶数,将它从中间分为长度相等的两部分,x、y 虽然A、B长度可能不一样,但容易得到,A的中心0在x中的位置,与B的中心1在y中的位置是相同的,因此x≠y BA的情况类似 f)形如xx的0、1串 解: 此语言无法用上下文无关文法描述 (Aho)4.11对习题4.1中文法 a)消除左递归 S→(L)|a L→SL’ L’→,SL’|ε b)构造预测分析表,对4.1(b)中句子,给出预测分析器的运行过程 FIRST(S)={(,a) FIRST(L)={(,a} FIRST(L’)={‘,’,ε} FOLLOW(S)={‘,’,),$} FOLLOW(L)={)} FOLLOW(L’)={)} 预测分析表: a ( ) $ S S→a S→(L) L L→SL’ L→SL’ L’ L’→ε L’→,SL’ (a,a)的分析过程 栈 输入 输出 $S (a,a)$ $)L( (a,a)$ S→(L) $)L a,a)$ L→SL’ $)L’S a,a)$ S→a $)L’a a,a)$ $)L’ a)$ L’→,SL’ $)L’S, a)$ $)L’S a)$ S→a $)L’a a)$ $)L’ )$ L’→ε $) )$ $ $ 其他两个句子的分析过程类似 (Aho)4.13下面文法产生除ε外所有长度为偶数的a的串 S→aSa|aa a)试为该文法构造一个带回溯的递归下降语法分析器,对S的两个候选式首先考虑aSa。 证明: S所对应的过程可以成功分析2、4、8个a的串,但6个a的串不行。 解: aa的分析过程,其中√表示匹配成功,×表示匹配失败,匹配失败则尝试下个候选式 aaaa分析过程: aaaaaa分析过程: aaaaaaaa分析过程: b)此语法分析器能识别什么样的语言? 解: 由a)的解可以看出,2N个a的串分析过程中,步骤如下 1)产生2N+1个S的语法树,对第2N+1个S进行扩展时输入缓冲已空,失败 2)对第2N个S尝试候选式aa,第二个a匹配失败 3)对第2N-1个S尝试候选式aa,左边N-1个a匹配,右边最后一个a匹配,倒数第二个a失败 4)对第2N-2个S尝试候选式aa,左边N-2个a匹配,右边最后一个a和倒数第二个a匹配,倒数第三个a失败 5)对第2N-4个S尝试候选式aa,左边N-4个a匹配,右边最后一个a~倒数第四个a匹配,倒数第五个a失败 6)对第2N-8个S尝试候选式aa,… 最后正确识别的情况必然是: 对第N个S尝试aa,左边N个a和右边N个a恰与输入匹配 显然,可以正确识别的符号串的N满足 2N–1–1–2–4-…=N→N=2i (Aho)4.25试给出图4-60中的优先关系表对应的优先级函数 解: 有向图如下 优先级函数为 a ( ) $ f 2 0 2 2 0 g 3 3 0 1 0 (Aho)4.26对习题4.1中文法,利用讲义中给出的算法计算终结符之间的优先关系 解: S→(L)|a L→L,S|S 由于S→(L),因此(≐ ) S→(L),而L⇒L,S,L⇒S⇒(L),L⇒S⇒a 因此(⋖,,(⋖(,(⋖a;,⋗),)⋗),a⋗) 由于L→L,S,而L⇒L,S,L⇒S⇒(L),L⇒S⇒a,因此,⋗,,)⋗,,a⋗, 而S⇒(L),S⇒a,因此,⋖(,,⋖a 非终结符与$优先关系的计算方法: 如果存在S⇒a…,或S⇒Qa…,则$⋖a, 若存在S⇒…a,或S⇒…aQ,则a⋗$ 因此,$⋖(,$⋖a,)⋗$,a⋗$ 算符优先关系表为: a ( ) $ a ⋗ ⋗ ⋗ ( ⋖ ⋖ ≐ ⋖ ) ⋗ ⋗ ⋗ ⋖ ⋖ ⋗ ⋗ $ ⋖ ⋖ (Aho)4.27试给下列文法构造算符优先关系 a)练习4.2中文法 解: S→aSbS|bSaS|ε 由S→aSbS可得a≐b 由S→bSaS可得b≐a 由S→aSbS,和S⇒bSaS可得a⋖b、b⋖b、a⋗b,和S⇒aSbS可得a⋖a、b⋖a、b⋗b 由S→bSaS,和S⇒bSaS可得b⋖b、a⋖b、a⋗a,和S⇒aSbS可得b⋖a、a⋖a、a⋗a 文法不是算符优先文法,二义性文法,很自然 b)练习4.3中文法 bexpr→bexprorbterm|bterm bterm→btermandbfactor|bfactor bfactor→notbfactor|(bexpr)|true|false 解: 无论分析语法含义,还是利用4.26算法计算,均可得到 true false not and or ( ) $ true ⋗ ⋗ ⋗ ⋗ false ⋗ ⋗ ⋗ ⋗ not ⋖ ⋖ ⋖ ⋗ ⋗ ⋖ ⋗ ⋗ and ⋖ ⋖ ⋖ ⋗ ⋗ ⋖ ⋗ ⋗ or ⋖ ⋖ ⋖ ⋖ ⋗ ⋖ ⋗ ⋗ ( ⋖ ⋖ ⋖ ⋖ ⋖ ⋖ ≐ ) ⋗ ⋗ ⋗ ⋗ $ ⋖ ⋖ ⋖ ⋖ ⋖ ⋖ (Aho)4.30一个文法称为Greibach范式(GNF)文法,如果它无ε产生式,且每个产生式(S→ε除外)均形如A→aα,其中,a是终结符,α是非终结符串,也可能为空。 a)试编写一个算法,将给定文法转换为Greibach范式 解: 算法步骤如下 1.先将文法消除左递归、消除ε产生式、删除无用符号,然后对每个非终结符A的每个产生式,执行2 2.若产生式右部以终结符开始,则略过,考虑其他产生式,否则产生式必为A→A1α的形式,A1为≠A的NT,a为语法符号串,对它执行以下操作 i.将A1的所有产生式的右部替换A1,产生新的关于A的产生式 ii.对于这些产生式,若右部以T开始,略过,不予处理,考虑那些以NT开始的产生式,反复执行i、ii iii.由于文法的NT个数是有限的(设为k),且已消除左递归,则最多k个步骤后,处理完毕,此时,A的产生式右部应该均以T开始。 否则,若某个产生式右部以NT开始,表明A无论经过怎样的推导过程,均不可能得到一个以终结符开始的串,当然也就不可能得到一个终结符串,这显然是一个错误的文法,矛盾。 这样,A的某个产生式处理完毕,其右部均以T开始。 转向2,继续考虑其他产生式,所有产生式处理完毕,则转向3 3.此时,每个产生式均为A→aα的形成,a为NT,α为语法符号串,若α中包含T,则进行如下处理 i.假定α中包含k个T,则产生式形为A→aα0a1α1…akαk,其中ai为T,αi为NT串或ε ii.引入k个新的NTA1、A2、…Ak,和k个新的产生式 A1→a1α1A2 A2→a2α2A3 … Ak-1→ak-1αk-1Ak Ak→akαk 而将原产生式改为A→aα0A1 4.经过2、3处理,所有产生式必然满足Greibach范式的格式 b)将你的算法应用到表达式文法4-10上 解: 文法4-10消除左递归、消除ε产生式后得到 E→TE'|T E'→+TE'|+T T→FT'|F T'→*FT'|*F F→(E)|id 将每个产生式转换为以T开始的形式,得到 E→(E)T'E'|idT'E'|(E)E'|idE'|(E)T'|idT'|(E)|id E'→+TE'|+T T→(E)T'|idT'|(E)|id T'→*FT'|*F F→(E)|id 将每个产生式右部转换为TNT*的形式,最后结果为: E→(EE''|idT'E'|(EE'''|idE'|(E|idT'|(EE'''''|id E''→)T'E' E'''→)E' E''''→)T' E'''''→) E'→+TE'|+T T→(EE''''|idT'|(EE'''''|id T'→*FT'|*F F→(EE'''''|id (Aho)4.33考虑文法 S→AS|b A→SA|a a)构造此文法的LR(0)项目集规范族 解: I0={S’→·S,S→·AS,S→·b,A→·SA,A→·a} goto(I0,S)={S’→S·,A→S·A,A→·SA,A→·a,S→·AS,S→·b}=I1 goto(I0,A)={S→A·S,S→·AS,S→·b,A→·SA,A→·a}=I2 goto(I0,a)={A→a·}=I3 goto(I0,b)={S→b·}=I4 goto(I1,S)={A→S·A,A→·SA,A→·a,S→·AS,S→·b}=I5 goto(I1,A)={A→SA·,S→A·S,S→·AS,S→·b,A→·SA,A→·a}=I6 goto(I1,a)=I3,goto(I1,b)=I4 goto(I2,S)={S→AS·,A→S·A,A→·SA,A→·a,S→·AS,S→·b}=I7 goto(I2,A)=I2,goto(I2,a)=I3,goto(I2,b)=I4 goto(I5,S)=I5,goto(I5,A)=I6,goto(I5,a)=I3,goto(I5,b)=I4 goto(I6,S)=I7,goto(I6,A)=I2,goto(I6,a)=I3,goto(I6,b)=I4 goto(I7,S)=I5,goto(I7,A)=I6,goto(I7,a)=I3,goto(I7,b)=I4 c)构造SLR分析表 解: FIRST(S)=FIRST(A)={a,b} FOLLOW(S)={$,a,b}FOLLOW(A)={a,b} SLR分析表为: action goto a b $ S A 0 s3 s4 1 2 1 s3 s4 acc 5 6 2 s3 s4 7 2 3 r4 r4 4 r2 r2 r2 5 s3 s4 5 6 6 s3/r3 s4/r3 7 2 7 s3/r1 s4/r1 r1 5 6 SLR分析表冲突,分析过程有多种可能路径,选择其中一种导致正确结果的即可。 d)对输入串abab,给出SLR分析器运行过程 栈 输入 动作 0 abab$ 移进 0a3 bab$ 归约A→a 0A2 bab$ 移进 0A2b4 ab$ 归约S→b 0A2S7 ab$ 归约S→AS 0S1 ab$ 移进 0S1a3 b$ 归约A→a 0S1A6 b$ 归约A→SA 0A2 b$ 移进 0A2b4 $ 归约S→b 0A2S7 $ 归约S→AS 0S1 $ 接受 e)构造规范LR分析表 解: I0={[S’→·S,$],[S→·AS,$/a/b],[S→·b,$/a/b],[A→·SA,a/b],[A→·a,a/b]} goto(I0,S)={[S’→S·,$],[A→S·A,a/b],[A→·SA,a/b],[A→·a,a/b],[S→·AS,a/b],[S→·b,a/b]}=I1 goto(I0,A)={[S→A·S,$/a/b],[S→·AS,$/a/b],[S→·b,$/a/b],[A→·SA,a/b],[A→·a,a/b]}=I2 goto(I0,a)={[A→a·,a/b]}=I3,goto(I0,b)={[S→b·,$/a/b]}=I4 goto(I1,S)={[A→S·A,a/b],[A→·SA,a/b],[A→·a,a/b],[S→·AS,a/b],[S→·b,a/b]}=I5 goto(I1,A)={[A→SA·,a/b],[S→A·S,a/b],[S→·AS,a/b],[S→·b,a/b],[A→·SA,a/b],[A→·a,a/b]}=I6 goto(I1,a)=I3,goto(I1,b)={[S→b·,a/b]}=I7 goto(I2,S)={[S→AS·,$/a/b],[A→S·A,a/b],[A→·SA,a/b],[A→·a,a/b],[S→·AS,a/b],[S→·b,a/b]}=I8 goto(I2,A)=I2,goto(I2,a)=I3,goto(I2,b)=I4 goto(I5,S)=I5,goto(I5,A)=I6,goto(I5,a)=I3,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 答案