当前位置：文档之家 › 编译原理教程第四版答案

编译原理教程第四版答案

  • 格式：docx
  • 大小：13.03 KB
  • 文档页数：10

编译原理教程第四版答案【篇一：编译原理教程课后习题答案——第三章】.1 完成下列选择题：(1) 文法g：s→xsx|y所识别的语言是a. xyxb. (xyx)*c. xnyxn(n≥0)d. x*yx*a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同(3) 采用自上而下分析，必须。

a. 消除左递 a. 必有ac归b. 消除右递归c. 消除回溯d. 提取公共左因子(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则。

b. 必有cac. 必有bad. a～c都不一定成立(5) 在规范归约中，用a. 直接短语b. 句柄c. 最左素短语d. 素短语a. 归约b. 移进c. 接受d. 待约a. lalr文法b. lr(0)文法c. lr(1)文法d. slr(1)文法(8) 同心集合并有可能产生新的冲突。

a. 归约b. “移进”/“移进”c.“移进”/“归约”d. “归约”/“归约”【解答】 (1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法g[n]为g[n]: n→d|ndd→0|1|2|3|4|5|6|7|8|9(1) g[n]的语言l(g[n])是什么?(2) 给出句子0127、34和568的最左推导和最右推导。

【解答】(1) g[n]的语言l(g[n])是非负整数。

(2) 最左推导： nndnddnddddddd0ddd01dd012d0127nnddd3d34nndnddddd5dd56d568最右推导： nndn7nd7n27nd27n127d1270127nndn4d434nndn8nd8n68d685683.3 已知文法g[s]为s→asb|sb|b，试证明文法g[s]为二义文法。

【解答】由文法g[s]：s→asb|sb|b，对句子aabbbb可对应如图3-1所示的两棵语法树。

ssasbsbasbasbsbasbbb图3-1 句子aabbbb对应的两棵不同语法树因此，文法g[s]为二义文法(对句子abbb也可画出两棵不同语法树)。

sassassas??sas(a)(b)图3-2 句子aa对应的两棵不同的语法树由图3-2可知，文法g[s]为二义文法。

3.5 按指定类型，给出语言的文法。

(1) l={aibj|j＞i≥0}的上下文无关文法；(3) 由相同个数a和b组成句子的无二义文法。

【解答】 (1) 由l={aibj|j＞i≥0}知，所求该语言对应的上下文无关文法首先应有s→asb型产生式，以保证b的个数不少于a的个数；其次，还需有s→sb或s→b型的产生式，用以保证b的个数多于a的个数。

因此，所求上下文无关文法g[s]为g[s]：s→asb|sb|b由图3-3可直接得到正规文法g[s]：s→aa|bba→as|bc|b图3-3 习题3.5的(3) 我们用一个非终结符a代表一个a(即有a→a)，用一个非终结符b代表一个b(即有b→b)；为了保证a和b的个数相同，则在出现一个a时应相应地出现一个b，出现一个b时则相应出现一个a。

假定已推导出ba，如果下一步要推导出连续两个b时，则应有babbaa。

也即为了保证b和a的个数一致，应有a→baa；同理有b→abb。

此外，为了保证递归地推出所要求的ab串，应有s→abs和s→bas。

由此得到无二义文法g[s]为a→baa|ab→abb|b3.6 有文法g[s]: s→aacb|bda→aab|cb→bsca|b(1) 试求句型aaabcbbdcc和aacbbdcc的句柄；(2) 写出句子acabcbbdcc的最左推导过程。

【解答】 (1) 分别画出对应句型aaabcbbdcc和aacbbdcc的语法树如图3-4的(a)、s(b)所示。

saacbaacb aabbscabscabdc图3-4 习题3.6的语法树bdc b (a )(b ) (a) aaabcbbdcc; (b) aacbbdcc 对树(a)，直接短语有3个：aab、b和c，而aab为最左直接短语(即为句柄)。

对树(b)，直接短语有两个：bd和c，而bd为最左直接短语。

能否不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aaabcbbdcc，我们可以由左至右扫描找到第一个子串aab，它恰好是满足a→aab右部的子串；与树(a)对照，aab的确是该句型的句柄。

是否这一方法始终正确呢？我们继续检查句型aacbbdcc，由左至右找到第一个子串c，这是满足a→c右部的子串，但由树(b)可知，c不是该句型的句柄。

由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。

(2) 句子acabcbbdcc的最左推导如下：saacbaaabcbacabcbacabcbacabcbscaacabcbbdcaacabcbbdcaacabcbbdcc3.7 对于文法g[s]: s→(l)|as|al→l,s|s(1) 画出句型(s,(a))的语法树；(2) 写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。

【解答】 (1) 句型(s, (a))的语法树如图3-5所示。

s(l)l,ss(l)图3-5 句型(s,(a))的语法树 sa(2) 由图3-5可知：短语：s、a、(a)、s,(a)、(s,(a))；直接短语：a、s；句柄：s；素短语：素短语可由图3-5中相邻终结符之间的优先关系求得，即： #? (?，? (?a?)?)?#因此，素短语为a。

3.8 下述文法描述了c语言整数变量的声明语句：g[d]: d→tlt→int|long|shortl→id|l,id(1) 改造上述文法，使其接受相同的输入序列，但文法是右递归的；(2) 分别用上述文法g[d]和改造后的文法g[d′]为输入序列int a,b,c构造分析树。

【解答】 (1) 消除左递归后，文法g[d′]如下：d→tl dt→int|long|short dtll→idlintal′intl,c,bl′l,b,cl′图3-6 两种文法为int a,b,c构造的分析树a?(a ) (b )(a) 文法g(d)； (b) 文法g′(d)3.9 考虑文法g[s]: s→(t) | a+s | at→t,s | s消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。

【解答】消除文法g[s]的左递归：s→(t) | a+s | at→st′提取公共左因子：s→(t) | as′t→st′改造后的文法已经是ll(1)文法，不带回溯的递归子程序如下：void match (token t){if ( lookahead==t)lookahead=nexttoken;else error ( );}void s ( ){if ( lo okahead==′a′)match (′a′);else if ( lookahead==′(′){match (′(′);t ( );void s′( ){if ( lookahead==′+′){match (′+′);s ( );}}void t ( ){s ( );t′( );}void t′ ( ){if ( lookahead==′, ′){match (′, ′);s ( );t′ ( );}}3.10 已知文法g[a]: a→aabl|ab→bb|d(1) 试给出与g[a]等价的ll(1)文法g[a′]；(2) 构造g[a′]的ll(1)分析表；(3) 给出输入串aadl#的分析过程。

来消除左递归。

由此，将产生式b→bb|d改造为b→db′其次，应通过提取公共左因子的方法来消除g[a]中的回溯，即将产生式a→aabl|a改造为a→aa′【篇二：编译原理教程课后习题答案——第一章】完成下列选择题：(1) 构造编译程序应掌握a. 源程序b. 目标语言c. 编译方法d. 以上三项都是(2) 编译程序绝大多数时间花在上。

a. 出错处理b. 词法分析c. 目标代码生成d. 表格管理(3) 编译程序是对。

a. 汇编程序的翻译b. 高级语言程序的解释执行c. 机器语言的执行d. 高级语言的翻译【解答】(1) d (2) d(3) d1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。

在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。

这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。

在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。

因此，编译对源程序的处理是先翻译，后执行。

从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。

这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。

1.3 请画出编译程序的总框图。

如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？【解答】编译程序总框图如图1-1所示。

作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。

总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。

程序子程序或分程序语句表达式数据引用算符函数调用【篇三：编译原理课后答案】下列正规式描述的语言(a) 0(0|1)*0在字母表{0, 1}上,以0开头和结尾的长度至少是2的01串在字母表{0, 1}上,所有的01串,包括空串在字母表{0, 1}上,含有3个1的01串(e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*在字母表{0, 1}上,含有偶数个0和偶数个1的01串2.4为下列语言写正规定义 c语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。

合集下载

编译原理-第4章 语法分析--习题答案

编译原理-第4章 语法分析--习题答案

第4章语法分析习题答案1．判断（1）由于递归下降分析法比较简单，因此它要求文法不必是LL(1)文法。

(× )LL(1)文法。

(× )（3）任何LL(1)文法都是无二义性的。

(√)（4）存在一种算法，能判定任何上下文无关文法是否是LL(1) 文法。

(√)(× )（6）每一个SLR(1)文法都是LR(1)文法。

(√)（7）任何一个LR(1)文法，反之亦然。

(× )（8）由于LALR是在LR(1)基础上的改进方法，所以LALR(× )（9）所有LR分析器的总控程序都是一样的，只是分析表各有不同。

(√)（10）算符优先分析法很难完全避免将错误的句子得到正确的归约。

(√)2．文法G[E]：E→E+T|TT→T*F|FF→(E)|i试给出句型(E+F)*i的短语、简单短语、句柄和最左素短语。

答案：画出语法树，得到：短语: (E+F)*i ，(E+F) ，E+F ，F ，i简单短语: F ，i句柄: F最左素短语: E+F3．文法G[S]：S→SdT | TT→T<G | GG→(S) | a试给出句型(SdG)<a的短语、简单短语、句柄和最左素短语。

答案：画出语法树，得到：短语：(SdG)<a 、（SdG） 、SdG 、G 、a简单(直接)短语：G 、a句柄：G最左素短语：SdG4．对文法G[S]提取公共左因子进行改写，判断改写后的文法是否为LL(1)文法。

S→if E then S else SS→if E then SS→otherE→b答案：提取公共左因子；文法改写为：S→if E then S S'|otherS'→else S|E→bLL(1)文法判定：① 文法无左递归② First(S)={if,other}, First(S')={else, }First(E)={b}Follow(S)= Follow(S')={else,#}Follow(E)={then}First(if E then S S')∩First(other)=First(else S)∩First( )=③First(S')∩Follow(S')={else}不为空集故此文法不是LL(1)文法。

编译原理第4章习题答案

编译原理第4章习题答案


S-> S’ S’->(S)SS’| First( (S)SS’) = { （ } Follow(S)=Follow(S’)= { (, ),$ }
预测分析表
非终结符 S （ S->S’ ） S->S’ $ S->S’
S’
S’->(S)SS’
S’->
S’->
S’->
冲突
仔细分析后，发现该文法 S->S(S)S| 是二义性文法。 二义性文法不可能是LL(1)文法。 例如：( ) ( )
S->aS’ S’->aS’AS’|Ɛ A->+|*
First(S) = First(aS’)={a} First(S’)= First(aS’AS’) ∪ First(Ɛ)= {a} ∪{Ɛ}= {a, Ɛ} First(A) = { +,*}
Follow(S) ={$} 因为 S->aS’，所以把Follow(S)加入到Follow(S’)中。 因为 S’->aS’AS’的第一个S’ ，所以把First(AS’)={+,*}加入到Follow(S’)中。 因为 S’->aS’AS’的第二个S’ ，所以Follow(S)加入到Follow(S’)中。 所以，Follow(S’)= {$, +,*} 对 S’->aS’AS’的A ，当A后面的S’推导出非空时，把First(S’)-{Ɛ}={a}加入到Follow(A)中。 对 S’->aS’AS’的A ，当A后面的S’推导出空时，把Follow(S’)={$,+,*}加入到Follow(A)中。 所以，Follow(A)= {a, +,*,$} 对于S’->aS’AS’|Ɛ，因为First(aS’AS’) ∩Follow(S’)={a} ∩{$,+,*}=空集,所以没有冲突。 对于A->+|*，因为First(+) ∩First(*)={+} ∩{*}=空集,所以没有冲突。 所以该文法是LL(1)文法。
编译原理第四章参考答案

编译原理第四章参考答案

编译原理第四章参考答案1.1考虑下⾯⽂法G1S->a|^|(T)T->T,S|S消去G1的左递归。

然后对每个⾮终结符，写出不带回溯的递归⼦程序。

答:：(1)消除左递归:S->a|^|(T)T-> ST’T’->,S T’|ε(2)first(S)={ a , ^ , ( } first(T)= { a , ^ , ( } first(T’)={ , ε}First(a)={a},First(^)={^},First( (T) )={ ( }S的所有候选的⾸符集不相交First(,ST’)={,} ,First(ε)={ε},T’的所有候选的⾸符集不相交Follow(T’)=Follow(T)={ )}first(T’)∩Follow(T’)={}所以改造后的⽂法为LL(1)⽂法。

不带回溯的递归⼦程序如下：S( ){if (lookahead=’a’) advance;Else if(lookahead=’^’) advance;Else if(lookahead=’(’){advance;T();if(lookahead=’)’) advance;else error();}Else error();}T( ){S( );T’( ):}T’->,S T’|εT’( ){if (lookahead=’,’){advance;T’();}Else if(lookahead=Follow(T’)) advance;Else error;}有⽂法G(S):S→S+aF|aF|+aFF→*aF|*a(1)改写⽂法为等价⽂法G[S’]，消除⽂法的左递归和回溯(2)构造G[S’]相应的FIRST和FOLLOW集合；(3)构造G[S’]的预测分析表，以此说明它是否为LL(1)⽂法。

(4)如果是LL(1)⽂法，请给出句⼦a*a+a*a*a的预测分析过程该⽂法为LL(1)⽂法，因为它的预测分析表中⽆冲突项。

编译原理课后答案

编译原理课后答案

第二章 高级语言及其语法描述4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。

（2） 优先顺序为↑，+，*，同级优先采用右结合。

解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16 （2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=46．令文法G6为 N →D|NDD →0|1|2|3|4|5|6|7|8|9 （1） G6 的语言L （G6）是什么？（2） 给出句子0127、34和568的最左推导和最右推导。

解：（1）L （G6）=｛a|a ∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝（2）N ＝＞ND ＝＞ NDD ＝＞ NDDD ＝＞ DDDD ＝＞ 0DDD ＝＞ 01DD ＝＞ 012D ＝＞ 0127 N ＝＞ ND ＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127 N ＝＞ ND ＝＞ DD ＝＞ 3D ＝＞ 34 N ＝＞ ND ＝＞ N4＝＞ D4 ＝＞34N ＝＞ ND ＝＞ NDD ＝＞ DDD ＝＞ 5DD ＝＞ 56D ＝＞ 568 N ＝＞ ND ＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 5687．写一个文法，使其语言是奇数集，且每个奇数不以0开头。

解：A →SN, S →+|-|∑, N →D|MDD →1|3|5|7|9, M →MB|1|2|3|4|5|6|7|8|9 B →0|1|2|3|4|5|6|7|8|9 8. 文法：E T E T E T TF T F T F F E i→+-→→|||*|/()| 最左推导:E E T T TF T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()最右推导:E E T E TF E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()语法树：/********************************EE FTE +T F F T +iiiEEFTE-T F F T -iiiE EFT+T F FTiii*i+i+ii-i-ii+i*i*****************/9．证明下面的文法是二义的：S → iSeS|iS|I解：因为iiiiei 有两种最左推导，所以此文法是二义的。