编译原理(第二版)清华大学---答案详解.pdf 167页

'《编译原理》课后习题答案第一章第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。（2）源程序：源语言编写的程序称为源程序。（3）目标程序：目标语言书写的程序称为目标程序。（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第一章目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。第3题何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？答案：翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功能的实现，完成后返回到解释程序的总控部分再读人下一条语句继续进行解释、执行，如此反复；另一种方式是，一边翻译一边执行，即每读出源程序的一条语句，解释程序就将其翻译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如此反复。无论盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第一章是哪种方式，其加工结果都是源程序的执行结果。目前很多解释程序采取上述两种方式的综合实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行中间代码程序，最后得到运行结果。广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是边翻译（解释）边执行，不产生目标代码，输出源程序的运行结果。而编译程序只负责把源程序翻译成目标程序，输出与源程序等价的目标程序，而目标程序的执行任务由操作系统来完成，即只翻译不执行。第4题对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。（1）else没有匹配的if（2）数组下标越界（3）使用的函数没有定义（4）在数中出现非数字字符答案：（1）语法分析（2）语义分析（3）语法分析（4）词法分析第5题编译程序大致有哪几种开发技术？答案：（1）自编译：用某一高级语言书写其本身的编译程序。（2）交叉编译：A机器上的编译程序能产生B机器上的目标代码。（3）自展：首先确定一个非常简单的核心语言L0，用机器语言或汇编语言书写出它的编译程序T0，再把语言L0扩充到L1，此时L0⊂L1,并用L0编写L1的编译程序T1，再把语言L1扩充为L2，有L1⊂L2,并用L1编写L2的编译程序T2，……，如此逐步扩展下去，好似滚雪球一样，直到我们所要求的编译程序。（4）移植：将A机器上的某高级语言的编译程序搬到B机器上运行。盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第一章第６题计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?答案：计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。像Basic之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反复。总而言之，是边翻译边执行。像C，Pascal之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上看，编译型的高级语言比解释型的高级语言更快。盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第二章第2章PL/0编译程序的实现第1题PL/0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。答案：PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。（数组CODE存放的只读目标程序，它在运行时不改变。）运行时的数据区S是由解释程序定义的一维整型数组，解释执行时对数据空间S的管理遵循后进先出规则，当每个过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题。第2题若PL/0编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题，试写出下列程序执行到赋值语句b∶=10时运行栈的布局示意图。varx,y;procedurep;vara;procedureq;varb;begin(q)b∶=10;end(q);procedures;varc,d;procedurer;vare,f;begin(r)callq;end(r);begin(s)callr;end(s);begin(p)calls;盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第二章end(p);begin(main)callp;end(main).答案：程序执行到赋值语句b∶=10时运行栈的布局示意图为：第3题写出题2中当程序编译到r的过程体时的名字表table的内容。namekindlevel/valadrsize答案：题2中当程序编译到r的过程体时的名字表table的内容为：namekindlevel/valadrsizexvariable0dxyvariable0dx+1pprocedure0过程p的入口（待填）5盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第二章avariable1dxqprocedure1过程q的入口4sprocedure1过程s的入口（待填）5cvariable2dxdvariable2dxrprocedure2过程r的入口5evariable3dxfvariable3dx+1注意：q和s是并列的过程，所以q定义的变量b被覆盖。第4题指出栈顶指针T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL与返回地址RA的用途。答案：栈顶指针T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL与返回地址RA的用途说明如下：T：栈顶寄存器T指出了当前栈中最新分配的单元(T也是数组S的下标)。B：基址寄存器，指向每个过程被调用时，在数据区S中给它分配的数据段起始地址，也称基地址。SL：静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，用以引用非局部（包围它的过程）变量时，寻找该变量的地址。DL：动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。在每个过程被调用时在栈顶分配3个联系单元，用以存放SL，DL，RA。第5题PL/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。（１）INT0A（２）OPR00（３）CALLA答案：PL/0编译程序所产生的目标代码中有3条非常重要的特殊指令，这3条指令在code中的位置和功能以及所完成的操作说明如下：盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第二章INT0A在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数+3。OPR00在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。CALLA调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行。第6题给出对PL/0语言作如下功能扩充时的语法图和EBNF的语法描述。(1)扩充条件语句的功能使其为：if〈条件〉then〈语句〉[else〈语句〉](2)扩充repeat语句为：repeat〈语句〉{；〈语句〉}until〈条件〉答案：对PL/0语言作如下功能扩充时的语法图和EBNF的语法描述如下：(1)扩充条件语句的语法图为：EBNF的语法描述为：〈条件语句〉::=if〈条件〉then〈语句〉[else〈语句〉](2)扩充repeat语句的语法图为：EBNF的语法描述为：〈重复语句〉::=repeat〈语句〉{；〈语句〉}until〈条件〉盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第三章第3章文法和语言第1题文法G＝({A,B,S},{a,b,c},P,S)其中P为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。答案：L(G[S])={abc}第2题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案:G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD....=>NDDDD...D=>D......D或者：允许0开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第三章答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbbnnL(G[Z])={ab|n>=1}第5题写一文法，使其语言是偶正整数的集合。要求：(1)允许0打头；(2)不允许0打头。答案：(1)允许0开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。（５）i+(i+i)（６）i+i*i盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第三章答案：<表达式>(5)<表达式>=><表达式>＋<项>=><表达式>＋<因子><表达式>+<项>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）<项><因子>=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）<因子>（<表达式>)=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）i=><项>＋（i＋i）<表达式>+<项>=><因子>＋（i＋i）=>i＋（i＋i）<项><因子><因子>ii<表达式>(6)<表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子><表达式>+<项>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i<项>=><项>＋i*i<项>*<因子>=><因子>＋i*i<因子>=>i＋i*i<因子>iii盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第三章第7题证明下述文法G[〈表达式〉]是二义的。〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/答案：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉a〈表达式〉*a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第三章第8题文法G[S]为：S→Ac|aBA→abB→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc(2)S=>aB=>abc即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。SSaBAcbcab第9题考虑下面上下文无关文法：SS→SS*|SS+|a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。(2)G[S]的语言是什么？SS*答案：SS+a(1)此文法生成串aa+a*的最右推导如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*aa(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。盛威网（www.snwei.com）专业的计算机学习网站5 《编译原理》课后习题答案第三章第10题文法S→S(S)S|ε(1)生成的语言是什么？(2)该文法是二义的吗？说明理由。答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。第11题令文法G[E]为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案：此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导序列:E=>E+T=>E+T*F，所以E+T*F句型此句型相对于E的短语有:E+T*F；相对于T的短语有T*F直接短语为：T*F句柄为：T*F第13题一个上下文无关文法生成句子abbaa的推导树如下：(1)给出串abbaa最左推导、最右推导。(2)该文法的产生式集合P可能有哪些元素？S(3)找出该句子的所有短语、直接短语、句柄。ABSSBBAaaεbba盛威网（www.snwei.com）专业的计算机学习网站6 《编译原理》课后习题答案第三章答案：(1)串abbaa最左推导:S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推导：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)产生式有：S→ABS|Aa|εA→aB→SBB|b可能元素有：εaaababbaaaaabbaa……(3)该句子的短语有：a是相对A的短语ε是相对S的短语b是相对B的短语εbb是相对B的短语aa是相对S的短语aεbbaa是相对S的短语直接短语有：aεb句柄是：a第14题给出生成下述语言的上下文无关文法：nnmm（1）{abab|n，m>=0}nmmn（2）{1010|n，m>=0}（3）{WaWr|W属于{0|a}*，Wr表示W的逆}答案：（１）S→AAA→aAb|ε（２）S→1S0|AA→0A1|ε（３）S→0S0|1S1|ε盛威网（www.snwei.com）专业的计算机学习网站7 《编译原理》课后习题答案第三章第16题给出生成下述语言的三型文法：(1){an|n>=0}nm(2){ab|n,m>=1}nmk(3){abc|n,m,k>=0}答案：(1)S→aS|ε(2)S→aAA→aA|BB→bB|b(3)A→aA|BB→bB|CC→cC|ε第17题习题７和习题11中的文法等价吗？答案：等价。第18题解释下列术语和概念：（１）字母表（２）串、字和句子（３）语言、语法和语义答案：（１）字母表：是一个非空有穷集合。（２）串：符号的有穷序列。字：字母表中的元素。+句子：如果Zx,x∈V*T则称x是文法G的一个句子。盛威网（www.snwei.com）专业的计算机学习网站8 《编译原理》课后习题答案第三章（３）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。盛威网（www.snwei.com）专业的计算机学习网站9 《编译原理》课后习题答案第三章附加题问题1：给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|0答案：*R=(01|10)(01|10)问题2：已知文法G[A]，写出它定义的语言描述G[A]:A→0B|1CB→1|1A|0BBC→0|0A|1CC答案:G[A]定义的语言由0、1符号串组成，串中0和1的个数相同.问题3：给出语言描述，构造文法.构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案一：G[E]E→E+T|T*T→TF|FF→(E)|a答案二：*G[E]E→E+E|EE|(E)|a问题4：已知文法G[S]:S→dAB盛威网（www.snwei.com）专业的计算机学习网站10 《编译原理》课后习题答案第三章A→aA|aB→ε|bB相应的正规式是什么？G[S]能否改写成为等价的正规文法？答案：正规式是daa*b*；相应的正规文法为(由自动机化简来)：G[S]:S→dAA→a|aBB→aB|a|b|bCC→bC|b也可为(观察得来):G[S]:S→dAA→a|aA|aBB→bB|ε问题5：已知文法G：E→E+T|E-T|TT→T*F|T/F|FF→(E)|i试给出下述表达式的推导及语法树(1)i;(2)i*i+i(3)i+i*i(4)i+(i+i)答案：(1)E=>T=>F=>i(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)=>i+(i+T)=>i+(i+F)=>i+(i+i)EEETE+TE+TE+TTFFTTFT*F(E)iiFFFFii(1)E+Tiiii(2)TF(3)Fi(4)i盛威网（www.snwei.com）专业的计算机学习网站11 《编译原理》课后习题答案第三章问题6：已知文法G[E]:E→ET+|TT→TF*|FF→F^|a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.答案：该句型对应的语法树如下：该句型相对于E的短语有FF^^*相对于T的短语有FF^^*,F相对于F的短语有F^;F^^简单短语有F;F^句柄为F.问题7：适当变换文法，找到下列文法所定义语言的一个无二义的文法：S→SaS⏐SbS⏐ScS⏐d答案：该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做进一步变换，即可消除二义性。设a、b和c的优先级别依次增高，根据优先级联规则将文法变换为：S→SaS⏐AA→AbA⏐CC→CcC⏐d规定结合性为左结合，进一步将文法变换为：S→SaA⏐AA→AbC⏐CC→CcF⏐FF→d该文法为非二义的。盛威网（www.snwei.com）专业的计算机学习网站12 《编译原理》课后习题答案第三章问题8：构造产生如下语言的上下文无关文法：n2nm（1）{abc|n，m≥0}nm2m（2）{abc|n，m≥0}mn（3）{ab⏐m≥n}mnpq（4）{abcd⏐m+n=p+q}（5）{uawb⏐u,w∈{a,b}*∧|u|=|w|}答案：n2nmn2n（1）根据上下文无关文法的特点，要产生形如abc的串，可以分别产生形如ab和m形如c的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是特别指明，通常可以忽略这一点。对于该语言，存在一个由以下产生式定义的上下文无关文法G[S]：S→ABA→ε⏐aAbbB→ε⏐cBnm2mnm2m（2）同样，要产生形如abc的串，可以分别产生形如a和形如bc的串。对于该语言，存在一个由以下产生式定义的上下文无关文法G[S]：S→ABA→ε⏐aAB→ε⏐bBcc（3）考虑在先产生同样数目的a,b，然后再生成多余的a。以下G[S]是一种解法：S→aSb⏐aS⏐ε（4）以下G[S]是一种解法：S→aSd⏐A⏐DA→bAd⏐BD→aDc⏐BB→bBc⏐ε注：a不多于d时，b不少于c；反之，a不少于d时，b不多于c。前一种情形通过对应A，后一种情形对应D。（5）以下G[S]是一种解法：S→AbA→BAB⏐a盛威网（www.snwei.com）专业的计算机学习网站13 《编译原理》课后习题答案第三章B→a⏐b问题9：下面的文法G(S)描述由命题变量p、q，联结词∧（合取）、∨（析取）、¬（否定）构成的命题公式集合：S→S∨T⏐TT→T∧F⏐FF→¬F⏐p⏐q试指出句型¬F∨¬q∧p的直接短语（全部）以及句柄。答案：直接短语：p，q，¬F句柄：¬F问题10：设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+.答案：000x=(aaa)=ε|x|=0xx=aaaaaa|xx|=655x=aaaaaaaaaaaaaaa|x|=15+12nA=A∪A∪∪….A…∪={a,aa,aaa,aaaa,aaaaa…}012nA*=A∪A∪A∪….∪A∪…={ε,a,aa,aaa,aaaa,aaaaa…}问题11：令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3答案：xy=abcb|xy|=4xyz=abcbaab|xyz|=7333(xy)=(abcb)=abcbabcbabcb|(xy)|=12问题12：已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文法描述的只含有四个符号的句子。盛威网（www.snwei.com）专业的计算机学习网站14 《编译原理》课后习题答案第三章答案：Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z00=>U000=>1000Z=>V1=>Z00=>V100=>0100问题13：已知文法G[S]：S∷=ABA∷=aA︱εB∷=bBc︱bc,写出该文法描述的语言。答案：nA∷=aA︱ε描述的语言:{a|n>=0}nnB∷=bBc︱bc描述的语言:{,bc|n>=1}nmmL(G[S])={abc|n>=0,m>=1}问题14：已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。答案：开始符号：EVT={+,-,*,/,（,）,i}VN={E,F,T}问题15：设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？答案：根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。盛威网（www.snwei.com）专业的计算机学习网站15 《编译原理》课后习题答案第三章SSS*SS+SS+SaaS*Saaaa问题16：写一文法，使其语言是奇正整数集合。答案：A::=1|3|5|7|9|NAN::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9|N::=0|1|2|3|4|5|6|7|8|9盛威网（www.snwei.com）专业的计算机学习网站16 《编译原理》课后习题答案第四章第4章词法分析第1题构造下列正规式相应的DFA.（１）1(0|1)*101（２）１(1010*|1(010)*1）*0（３）a((a|b)*|ab*a)*b（４）b((ab)*|bb)*ab答案：(1)先构造NFA：用子集法将NFA确定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。.01X.AAABBCBCADDCBDFA的状态图：:盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第四章(2)先构造NFA：0ε101ε0εBCDELY1εXAεε10101FGHIJKεε用子集法将NFA确定化ε01XXT0=XAAABFLT1=ABFLYCGYYCGCGJT2=YT3=CGJDHKDHDHKABFKLT4=DHEIEIABEFILT5=ABFKLYCGT6=ABEFILEJYCGEJYABEFGJLYT7=ABEFGJLYEHYCGKEHYABEFHLYCGKABCFGJKLT8=ABEFHLYEYCGIEYABEFLYCGICGJIT9=ABCFGJKLDHYCGKDHYDHYT10=ABEFLYEYCGT11=CGJIDHJKDHJDHJT12=DHYEIT13=DHJEIKEIKABEFIKLT14=ABEFIKLEJYCG盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第四章将T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分别用0、1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因为2、7、8、10、12中含有Y，所以它们都为终态。010112323454652367378981011912910103111351261314147310012101315110111461011079120000101108111314盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第四章(3)先构造NFA：先构造NFA：a,bεεbεBCYbεXaAεaaDEFε用子集法将NFA确定化εabXXT0=XAAABCDT1=ABCDBEBYBEABCDEBYABCDYT2=ABCDEBEFBEYBEFABCDEFBEYABCDEYT3=ABCDYBEBYT4=ABCDEFBEFBEYT5=ABCDEYBEFBEY将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为3、5中含有Y，所以它们都为终态。ab01123245323445545abb013aaaa24bbab5盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第四章(4)先构造NFA：εεabεεBCDbεEaIbXAεYbbεFGHε用子集法将NFA确定化：εabXXT0=XAAABDEFT1=ABDEFCIGCICIGGT2=CIDYDYABDEFYT3=GHHABEFHT4=ABDEFYCIGT5=ABEFHCIG将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为4中含有Y，所以它为终态。ab011232435423523DFA的状态图：盛威网（www.snwei.com）专业的计算机学习网站5 《编译原理》课后习题答案第四章bb013bab2b5baa4盛威网（www.snwei.com）专业的计算机学习网站6 《编译原理》课后习题答案第四章第２题已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，构造相应的DFA。答案：先构造其矩阵01xzxyx,yzx,zy用子集法将NFA确定化：01xzxzxzyxzxzxyyxyxyxyzxxyzxyzxy将x、z、xz、y、xy、xyz重新命名，分别用A、B、C、D、E、F表示。因为B、C、F中含有z，所以它为终态。01ABABCDCCEDEEFAFFEDFA的状态图：1101ABD001EC001F0盛威网（www.snwei.com）专业的计算机学习网站7 《编译原理》课后习题答案第四章第3题将下图确定化：答案：用子集法将NFA确定化：.01SVQQUVQVZQUQUVQUZVZZZVZ.QUZVZQUZZZZ重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。.01SABACBBDECFFDF.ECEFFFDFA的状态图：盛威网（www.snwei.com）专业的计算机学习网站8 《编译原理》课后习题答案第四章第4题将下图的（a）和（b）分别确定化和最小化：答案：初始分划得Π0：终态组{0}，非终态组{1,2,3,4,5}对非终态组进行审查：{1,2,3,4,5}a{0,1,3,5}而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}∵{4}a{0}，所以得到新分划Π1：{0}，{4}，{1,2,3,5}对{1,2,3,5}进行审查：∵{1,5}b{4}{2,3}b{1,2,3,5}，故得到新分划Π2：{0}，{4}，{1,5}，{2,3}{1,5}a{1,5}{2,3}a{1,3}，故状态2和状态3不等价，得到新分划Π3：{0}，{2}，{3}，{4}，{1,5}这是最后分划了盛威网（www.snwei.com）专业的计算机学习网站9 《编译原理》课后习题答案第四章最小DFA：第5题构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。答案：按题意相应的正规表达式是(0*10)*0*，或0*(0|10)*0*构造相应的DFA，首先构造NFA为用子集法确定化：II0I1{X,0,1,3,Y}{0,1,3,Y}{2}{0,1,3,Y}{0,1,3,Y}{2}{2}{1,3,Y}{1,3,Y}{1,3,Y}{2}重新命名状态集：S0112322334443DFA的状态图：盛威网（www.snwei.com）专业的计算机学习网站10 《编译原理》课后习题答案第四章可将该DFA最小化：终态组为{1,2,4}，非终态组为{3}，{1,2,4}0{1,2,4}，{1,2,4}1{3}，所以1,2,4为等价状态，可合并。第６题设无符号数的正规式为θ：θ=dd*|dd*.dd*|.dd*|dd*10(s|ε)dd*|10(s|ε)dd*|.dd*10(s|ε)dd*|dd*.dd*10(s|ε)dd*化简θ，画出θ的DFA，其中d={0,1,2,…,9}，s={＋，－}答案：先构造NFA：dddsd10dDE.BCYεdXA10sdFGHdεε用子集法将NFA确定化：盛威网（www.snwei.com）专业的计算机学习网站11 《编译原理》课后习题答案第四章ε·s10dXXAT0=XABFABBFFGAAT1=BCCCT2=FGGHGGHHT3=ABFAT4=CDCDDET5=GHT6=HHT7=DEEYEEYYT8=EYT9=YY将XA、B、FG、A、C、G、H、DE、E、Y重新命名，分别用0、1、2、3、4、5、6、7、8、9表示。终态有0、3、4、6、9。·s10d012314256312347456667898999DFA的状态图：盛威网（www.snwei.com）专业的计算机学习网站12 《编译原理》课后习题答案第四章dd10·417·s10s0258d10dddd369ddd第7题给文法G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aAE→aB|bFF→bD|aE|b构造相应的最小的DFA。答案：先构造其NFA：ababSABZabbabbabbbQDEFaba用子集法将NFA确定化：盛威网（www.snwei.com）专业的计算机学习网站13 《编译原理》课后习题答案第四章abSAQAABZQQDZBZQDDZABDABBQD将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。ab012113224325416516625DFA的状态图：aa01aba5b4bbb2a3aab6b令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b进行分割：P1＝（｛0,5,6｝,｛1,2｝,｛3,4｝）再用b进行分割：P2＝（｛0｝,｛5,6｝,｛1,2｝,｛3,4｝）再用a、b进行分割，仍不变。再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。最小化为：盛威网（www.snwei.com）专业的计算机学习网站14 《编译原理》课后习题答案第四章aa,bBAababDCb第８题给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|0答案：解方程组S的解：S=0A|1BA=1S|1B=0S|0将A、B产生式的右部代入S中S=01S|01|10S|10=（01|10）S|（01|10）所以：S=(01|10)*(01|10)第9题将下图的DFA最小化，并用正规式描述它所识别的语言。cbab361dcb5dbaab247b盛威网（www.snwei.com）专业的计算机学习网站15 《编译原理》课后习题答案第四章答案：令P0＝（｛1,2,3,4,5｝,｛6,7｝）用b进行分割：P1＝（｛1,2｝,｛3,4｝,｛5｝,｛6,7｝）再用a、b、c、d进行分割，仍不变。再令｛1,2｝为A，｛3，4｝为B，｛5｝为C，｛6，7｝为D。最小化为：cbaBAadbCDb*****+r=ba(c|da)bb=ba(c|da)b盛威网（www.snwei.com）专业的计算机学习网站16 《编译原理》课后习题答案第四章附加题问题1：为下边所描述的串写正规式，字母表是{a,b}.a)以ab结尾的所有串b)包含偶数个b但不含a的所有串c)包含偶数个b且含任意数目a的所有串d)只包含一个a的所有串e)包含ab子串的所有串f)不包含ab子串的所有串答案：注意正规式不唯一a)(a|b)*abb)(bb)*c)(a*ba*ba*)*d)b*ab*e)(a|b)*ab(a|b)*f)b*a*问题2：请描述下面正规式定义的串.字母表{0，1}.+a)0*(10)*0*b)(0|1)*(00|11)(0|1)*c)1(0|1)*0答案：a)每个1至少有一个0跟在后边的串b)所有含两个相继的0或两个相继的1的串c)必须以1开头和0结尾的串问题3：构造有穷自动机.a)构造一个DFA，接受字母表{0,1}上的以01结尾的所有串b)构造一个DFA，接受字母表{0,1}上的不包含01子串的所有串.c)构造一个NFA，接受字母表{x,y}上的正规式x(x|y)*x描述的集合d)构造一个NFA，接受字母表{a,b}上的正规式(ab|a)*b+描述的集合并将其转换为等价的DFA.以及最小状态DFA盛威网（www.snwei.com）专业的计算机学习网站17 《编译原理》课后习题答案第四章答案：b)c)盛威网（www.snwei.com）专业的计算机学习网站18 《编译原理》课后习题答案第四章最小化的DFA问题4：设有如图所示状态转换图，求其对应的正规表达式。可通过消结法得出正规式R=(01)*((00|1)(0|1)*|0)也可通过转换为正则文法，解方程得到正规式。问题5：已知正规式：(1)((a|b)*|aa)*b;(2)(a|b)*b.试用有限自动机的等价性证明正规式(1)和(2)是等价的，并给出相应的正规文法。分析：基本思路是对两个正规式，分别经过确定化、最小化、化简为两个最小DFA，如这两个最小DFA一样，也就证明了这两个正规式是等价的。答案：盛威网（www.snwei.com）专业的计算机学习网站19 《编译原理》课后习题答案第四章状态转换表1abX1241234124Y12341234124Y124Y1234124Y状态转换表2aB123223323由于2与3完全一样，将两者合并，即见下表ab12323而对正规式(2)可画NFA图，如图所示。abX121212Y121212Y12Y1212Y盛威网（www.snwei.com）专业的计算机学习网站20 《编译原理》课后习题答案第四章可化简得下表ab123223得DFA图两图完全一样，故两个自动机完全一样，所以两个正规文法等价。对相应正规文法,令A对应1，B对应2故为：A→aA|bB|bB→aA|bB|b即为S→aS|bS|B,此即为所求正规文法。问题6：考虑正规表达式r=a*b(a|b)，构造可以生成语言L(r)的一个正规文法。答案：S→a*b(a|b)变换为S→aA,S→b(a|b),A→aA,A→b(a|b)变换为S→aA,S→bB,B→(a|b),A→aA,A→bC,C→(a|b)变换为S→aA,S→bB,B→a,B→b,A→aA,A→bC,C→a,C→b所以，一个可能的正规文法为G[S]：S→aA,S→bB,B→a,B→b,A→aA,A→bC,C→a,C→b或表示为：S→aA|bB,B→a|b,A→aA|bC,C→a|b（适当等价变换也可以，但要作说明，即要有步骤）盛威网（www.snwei.com）专业的计算机学习网站21 《编译原理》课后习题答案第四章问题7：考虑下图所示的NFAN，构造可以生成语言L(N)的一个正规文法。答案：G[P]:P→0P⏐1P⏐1QQ→0R⏐1RR→ε问题8：考虑如下文法G[S]：S→0S⏐1S⏐1AA→0B⏐1BB→εa)试构造语言为L(G)的一个正规表达式。b)试构造语言为L(G)的一个有限自动机。答案：a)由A→0B，B→ε得A→0;由A→1B，B→ε得A→1;由A→0，A→1得A→0⏐1;由S→1A，A→0⏐1得S→1(0⏐1);由S→1A，A→0⏐1得S→1(0⏐1);由S→0S，S→1(0⏐1)得S→0*1(0⏐1);由S→1S，S→1(0⏐1)得S→1*1(0⏐1);由S→0*1(0⏐1)，S→1*1(0⏐1)得S→0*1(0⏐1)⏐1*1(0⏐1);所以，一个可能的正规表达式为：盛威网（www.snwei.com）专业的计算机学习网站22 《编译原理》课后习题答案第四章0*1(0⏐1)⏐1*1(0⏐1)b)盛威网（www.snwei.com）专业的计算机学习网站23 《编译原理》课后习题答案第五章第5章自顶向下语法分析方法第1题对文法G[S]S→a|∧|(T)T→T,S|S(1)给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。(2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。(3)经改写后的文法是否是LL(1)的?给出它的预测分析表。(4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。答案：(1)对(a,(a,a)的最左推导为：S(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))对(((a,a),∧,(a)),a)的最左推导为：S(T)(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((S,S,S),S)(((T),S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),∧,S),S)(((a,a),∧,(T)),S)(((a,a),∧,(S)),S)盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第五章(((a,a),∧,(a)),S)(((a,a),∧,(a)),a)(2)改写文法为：0)S→a1)S→∧2)S→(T)3)T→SN4)N→,SN5)N→ε非终结符FIRST集FOLLOW集S{a,∧,(}{#,,,)}T{a,∧,(}{)}....N{,,ε}.{)}....对左部为N的产生式可知：FIRST（→,SN）={，}FIRST（→ε）={ε}FOLLOW（N）={)}由于SELECT(N→,SN)∩SELECT(N→ε)={，}∩{)}=所以文法是LL(1)的。预测分析表（PredictingAnalysisTable）a∧(),#S→a→∧→(T)T→SN→SN→SNN→ε→,SN也可由预测分析表中无多重入口判定文法是LL(1)的。盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第五章(3)对输入串（a,a）#的分析过程为：当前输入符剩余输入符所用产生式栈（STACK）（CUR_CHAR）（INOUT_STRING）（OPERATION）#S(a,a)#...S→(T)#)T((a,a)#....#)Ta,a)#...T→SN#)NSa,a)#...S→a#)Naa,a)#....#)N,a)#...N→,SN#)NS,,a)#....#)NSa)#...S→a#)Naa)#....#)N)#...N→ε#))#...##可见输入串（a,a）#是文法的句子。盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第五章第3题已知文法G[S]：S→MH|aH→LSo|εK→dML|εL→eHfM→K|bLM判断G是否是LL(1)文法，如果是，构造LL(1)分析表。答案：文法展开为：0）S→MH1）S→a2）H→LSo3）H→ε4）K→dML5）K→ε6）L→eHf7）M→K8）M→bLM非终结符FIRST集FOLLOW集S{a,d,b,ε,e}{#,o}........M{d,ε,b}....{e,#,o}......H{ε,e}......{#,f,o}......L{e}.........{a,d,b,e,o,#}K{d,ε}......{e,#,o}......对相同左部的产生式可知：SELECT(S→MH)∩SELECT(S→a)={d,b,e，#,o}∩{a}=SELECT(H→LSo)∩SELECT(H→ε)={e}∩{#,f,o}=SELECT(K→dML)∩SELECT(K→ε)={d}∩{e,#,o}=SELECT(M→K)∩SELECT(M→bLM)={d，e,#,o}∩{b}=所以文法是LL(1)的。盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第五章预测分析表：aodefb#S→a→MH→MH→MH→MH→MHM→K→K→K→bLM→KH→ε→LSo→ε→εL→eHfK→ε→dML→ε→ε由预测分析表中无多重入口也可判定文法是LL(1)的。盛威网（www.snwei.com）专业的计算机学习网站5 《编译原理》课后习题答案第五章第7题对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。(１)A→baB|εB→Abb|a(2)A→aABe|aB→Bb|d(3)S→Aa|bA→SBB→ab答案：(１)先改写文法为：0)A→baB1)A→ε2)B→baBbb3)B→bb4)B→a再改写文法为：0)A→baB1)A→ε2)B→bN3)B→a4)N→aBbb5)N→bFIRSTFOLLOWA{b}{#}B{b,a}{#,b}N{b,a}{#,b}预测分析表：ab#A→baB→εB→a→bNN→aBbb→b由预测分析表中无多重入口判定文法是LL(1)的。（2）文法：A→aABe|aB→Bb|d提取左公共因子和消除左递归后文法变为：0)A→aN1)N→ABe盛威网（www.snwei.com）专业的计算机学习网站6 《编译原理》课后习题答案第五章2)N→ε3)B→dN14)N1→bN15)N1→ε非终结符FIRST集FOLLOW集A{a}...{#,d}B{d}...{e}..N{a,ε}{#,d}N1{b,ε}{e}..对相同左部的产生式可知：SELECT(N→ABe)∩SELECT(N→ε)={a}∩{#,d}=SELECT(N1→bN1)∩SELECT(N1→ε)={b}∩{e}=所以文法是LL(1)的。预测分析表（PredictingAnalysisTable）aebd#A→aNB→dN1N1→ε→bN1N→ABe→ε→ε也可由预测分析表中无多重入口判定文法是LL(1)的。（3）文法：S→Aa|bA→SBB→ab第1种改写：用A的产生式右部代替S的产生式右部的A得：S→SBa|bB→ab消除左递归后文法变为：0)S→bN1)N→BaN2)N→ε3)B→ab盛威网（www.snwei.com）专业的计算机学习网站7 《编译原理》课后习题答案第五章非终结符FIRST集FOLLOW集S{b}...{#}B{a}...{a}N{ε,a}{#}对相同左部的产生式可知：SELECT(N→BaN)∩SELECT(N→ε)={a}∩{#}=所以文法是LL(1)的。预测分析表（PredictingAnalysisTable）ab#S→bNB→abN→BaN→ε也可由预测分析表中无多重入口判定文法是LL(1)的。第2种改写：用S的产生式右部代替A的产生式右部的S得：S→Aa|bA→AaB|bBB→ab消除左递归后文法变为：0)S→Aa1)S→b2)A→bBN3)N→aBN4)N→ε5)B→ab非终结符FIRST集FOLLOW集S{b}...{#}A{b}...{a}B{a}...{a}N{a,ε}{a}对相同左部的产生式可知：SELECT(S→Aa)∩SELECT(S→b)={b}∩{b}={b}≠SELECT(N→aBN)∩SELECT(N→ε)={a}∩{a}={a}≠所以文法不是LL(1)的。盛威网（www.snwei.com）专业的计算机学习网站8 《编译原理》课后习题答案第五章预测分析表：ab#S→Aa..→b....A→bBNB→ab..N→aBN→ε...也可由预测分析表中含有多重入口判定文法不是LL(1)的。盛威网（www.snwei.com）专业的计算机学习网站9 《编译原理》课后习题答案第五章附加题问题1：已知文法G[A]如下，试用类C或类PASCAL语言写出其递归下降子程序.(主程序不需写)G[A]:A→[BB→X]{A}X→(a|b){a|b}答案：不妨约定:在进入一个非终结符号相应的子程序前，已读到一个单词.word：存放当前读到的单词，Getsym()为一子程序，每调用一次，完成读取一单词的工作。error()为出错处理程序.FIRST(A)为终结符A的FIRST集.类C程序如下：voidA()voidB()voidX(){{X();{ifword=="["ifword=="]"if(word=="a"||word=="b"){{{Getsym();Getsym();Getsym();B();while(wordinwhile(word=="a"||word=="b")}FIRST(A))Getsym();elseerror();A();}}}elseerror();elseerror();}}问题2：设有文法G[A]的产生式集为:A→BaC|CbBB→Ac|cC→Bb|b试消除G[A]的左递归。答案：提示：不妨以A、B、C排序.先将A代入B中，然后消除B中左递归；再将A、B代入C中。再消除C中左递归。最后结果为:G[A]:A→BaC|CbBB→CbBcB"|cB"B"→aCcB"|εC→cB"bC"|bC"C"→bBcB"bC"|ε盛威网（www.snwei.com）专业的计算机学习网站10 《编译原理》课后习题答案第五章问题3：试验证如下文法G[E]是LL(1)文法:E→[F]E′E’→E⏐εF→aF’F’→aF’⏐ε其中E,F,E’,F’为非终结符答案：各非终结符的FIRST集和FOLLOW集如下：FIRST（E）={[}FOLLOW（E）={＃}FIRST（E′）={[，ε}FOLLOW（E′）={＃}FIRST（F）={a}FOLLOW（F）={]}FIRST（F′）={a，ε}FOLLOW（F′）={]}对于E’→E⏐ε，FIRST(E)∩FIRST(ε)=φFIRST(E)∩FOLLOW（E’）=φ对于F’→aF’⏐ε，FIRST(aF’)∩FIRST(ε)=φFIRST（aF’）∩FOLLOW（F’）=φ所以,文法G[E]是LL（1）文法。问题4：文法G[E]是LL(1)文法:E→[F]E′E’→E⏐εF→aF’F’→aF’⏐ε其中E,F,E’,F’为非终结符。对文法G[E]构造递归下降分析程序。答案：/*用类C语言写出G[E]的递归子程序，其中yylex()为取下一单词过程，变量lookahead存放当前单词。*/intlookahead;盛威网（www.snwei.com）专业的计算机学习网站11 《编译原理》课后习题答案第五章voidParseE(){MatchToken(′[′);ParseF();MatchToken(′]′);ParseE’();}voidParseE’(){switch(lookahead){case′[′:ParseE();break;case′#′:break;default:printf("syntaxerrorn")exit(0);}}voidParseF(){MatchToken(′a′);ParseF’();}voidParseF’(){switch(lookahead){case′a′:MatchToken(′a′);ParseF’();break;case′]′:break;default:printf("syntaxerrorn")exit(0);}}盛威网（www.snwei.com）专业的计算机学习网站12 《编译原理》课后习题答案第五章voidMatchToken(intexpected){if(lookahead!=expected)//判别当前单词是否与期望的终结符匹配{printf("syntaxerrorn");exit(0);}else//若匹配,消费掉当前单词并读入下一个调用词法分析程序lookahead=yylex();}问题5：文法G[E]是LL(1)文法:E→[F]E′E’→E⏐εF→aF’F’→aF’⏐ε其中E,F,E’,F’为非终结符。构造文法G[E]的LL(1)分析表。答案：盛威网（www.snwei.com）专业的计算机学习网站13 《编译原理》课后习题答案第五章问题6：试消除下面文法G[A]中的左递归和左公因子，并判断改写后的文法是否为LL(1)文法?G[A]：A→aABe⏐aB→Bb⏐d答案：提取左公共因子和消除左递归后，G［A］变换为等价的G′［A］如下：A→aA′A′→ABe|εB→dB′B′→bB′|εµ计算非终结符的FIRST集和FOLLOW集结果如下：FIRST（A）={a}FOLLOW（A）={#,d}FIRST（B）={d}FOLLOW（B）={e}FIRST（A′）={a,ε}FOLLOW（A′）={#,d}FIRST（B′）={b,ε}FOLLOW（B′）={e}µ对相同左部的产生式可知：FIRST(ABe)∩FOLLOW(A′)={a}∩{#,d}=∅FIRST(bB′)∩FOLLOW(B′)={b}∩{e}=∅所以G′［S］是LL(1)文法。盛威网（www.snwei.com）专业的计算机学习网站14 《编译原理》课后习题答案第六章第6章自底向上优先分析第1题已知文法G[S]为：S→a|∧|(T)T→T,S|S(1)计算G[S]的FIRSTVT和LASTVT。(2)构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。(3)计算G[S]的优先函数。(4)给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。答案：文法展开为：S→aS→∧S→(T)T→T,ST→S(1)FIRSTVT-LASTVT表：(2)算符优先关系表：盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第六章表中无多重人口所以是算符优先（OPG）文法。友情提示：记得增加拓广文法S`→#S#，所以#FIRSTVT(S)，LASTVT(S)#。(3)对应的算符优先函数为：a(),^#f212221g331131（4）对输入串（a,a）#的算符优先分析过程为栈（STACK）当前输入字符（CHAR）剩余输入串（INPUT_STRING）动作（ACTION）#(a,a)#...Movein#(a,a)#...Movein#(a,a)#...Reduce:S→a#(N,a)#...Movein#(N,a)#...Movein#(N,a)#...Reduce:S→a#(N,N)#...Reduce:T→T,S#(N)#...Movein#(N)#Reduce:S→(T)#N#Success!盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第六章对输入串（a,(a,a)）#的算符优先分析过程为：剩余输入串栈（STACK）当前字符（CHAR）动作（ACTION）（INPUT_STRING）#(a,(a,a))#...Movein#(a,(a,a))#...Movein#(a,(a,a))#...Reduce:S→a#(N,(a,a))#...Movein#(N,(a,a))#...Movein#(N,(a,a))#...Movein#(N,(a,a))#...Reduce:S→a#(N,(N,a))#...Movein#(N,(Na))#...Movein#(N,(N,a))#...Reduce:S→a#(N,(N,N))#...Reduce:T→T,S#(N,(N))#...Movein#(N,(N))#...Reduce:S→(T)#(N,N)#...Reduce:T→T,S#(N)#...Movein#(N)#Reduce:S→(T)#N#Success!第2题已知文法G[S]为：S→a|∧|(T)T→T,S|S(1)给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。(2)将(1)和题1中的(4)进行比较给出算符优先归约和规范归约的区别。答案：（１）(a,a)的最右推导过程为：S(T)(T,S)(T,a)(S,a)(a,a)（a,(a,a)）的最右推导过程为：S(T)(T,S)(T,(T))盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第六章(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))(S,(a,a))(a,(a,a))(a,(a,a))的规范归约过程：步骤栈输入动作1#(a,(a,a))#移进2#(a,(a,a))#移进3#(a,(a,a))#归约，SÆa4#(S,(a,a))#归约，LÆS5#(T,(a,a))#移进6#(T,(a,a))#移进7#(T,(a,a))#移进8#(T,(a,a))#归约，SÆa9#(T,(S,a))#归约，TÆS10#(T,(T,a))#移进11#(T,(T,a))#移进12#(T,(T,a))#归约，SÆa13#(T,(T,S))#归约，TÆT,S14#(T,(T))#移进15#(T,(T))#归约，SÆ(T)16#(T,S)#移进17#(T,S)#归约，TÆT,S18#(T)#归约，SÆ(T)19#S#接受(a,a)的规范归约过程：步骤栈输入动作1#(a,a)#移进2#(a,a)#移进3#(a,a)#归约，SÆa4#(S,a)#归约，TÆS5#(T,a)#移进6#(T,a)#移进7#(T,a)#归约，SÆa8#(T,S)#归约，TÆT,S9#(T)#移进10#(T)#归约，SÆ(T)11#S#接受盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第六章(2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名字是什么，因此去掉了单非终结符的归约。规范归约的可归约串是句柄，并且必须准确写出可归约串归约为哪个非终结符。第３题：有文法G[S]：SÆVVÆT|ViTTÆF|T+FFÆ)V*|((1)给出(+(i(的规范推导。(2)指出句型F+Fi(的短语，句柄，素短语。(3)G[S]是否为OPG？若是，给出(1)中句子的分析过程。S答案：VViT(1)S=>V=>ViT=>ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=>(+(i(TF(2)句型F+Fi(的语法树：T+F(短语：F，F+F，(，F+Fi(句柄：F素短语：(F(3)FIRSTVT和LASTVTFIRSTVTLASTVTSi,+,),(i,+,*,(Vi,+,),(i,+,*,(T+,),(+,(,*F),(,*,(算符优先关系i+*()#i≯≮≯≮≮≯+≯≯≯≮≮≯*≯≯≯≯(≯≯≯≯)≮≮≮≮#≮≮≮≮≡因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。(+(i(的分析过程盛威网（www.snwei.com）专业的计算机学习网站5 《编译原理》课后习题答案第六章步骤栈优先关系当前符号剩余输入串移进或归约1##≮(((+(i(#移进2#((≯++(i(#归约3#F#≮++(i(#移进4#F++≮((i(#移进5#F+((≯ii(#归约6#F+F+≯ii(#归约7#F#≮ii(#移进8#Fii≮((#移进9#Fi((≯##归约10#FiFi≯##归约11#F#≡##接受盛威网（www.snwei.com）专业的计算机学习网站6 《编译原理》课后习题答案第六章第４题文法G［S］为：S→S;G｜GG→G(T)｜HH→a｜(S)T→T+S｜S（１）构造G［S］的算符优先关系表，并判断G［S］是否为算符优先文法。（２）给出句型a(T+S);H;(S)的短语、句柄、素短语和最左素短语。（３）给出a;(a+a)和(a+a)的分析过程，说明它们是否为G［S］的句子。（４）给出（３）中输入串的最右推导，分别说明两输入串是否为G[S]的句子。（５）由（３）和（４）说明了算符优先分析的哪些缺点。（６）算符优先分析过程和规范归约过程都是最右推导的逆过程吗？答案：（1）构造文法G［S］的算符优先关系矩阵：;()a+#;·＞＜··＞＜··＞·＞(＜·＜·=·＜·＜·)·＞·＞·＞·＞·＞a·＞·＞·＞·＞·＞+＜·＜··＞＜··＞#＜·＜·＜·=·在上表中可看出终结符之间的优先关系是唯一的，或称G［S］的算符优先关系矩阵不含多重入口，因此，G［S］是一个算符优先文法。盛威网（www.snwei.com）专业的计算机学习网站7 《编译原理》课后习题答案第六章（２）（3）对输入串(a+a)＃的分析过程如下：步骤栈当前符号剩余输入串移进或归约（1）#(a+a)#移进（2）#(a+a)#移进（3）#(a+a)#归约（4）#(N+a)#移进（5）#(N+a)#移进（6）#(N+a)#归约（7）#(N+N)#归约（8）#(N)#移进（9）#(N)#归约（10）#N#分析成功说明是它的句子。（４）试用规范推导：S⇒G⇒H⇒（S）由此往下S不可能推导出a+a，所以(a+a)不是G［S］的句子。（5）结果说明：由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，盛威网（www.snwei.com）专业的计算机学习网站8 《编译原理》课后习题答案第六章当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。（６）算符优先分析过程不是最右推导的逆过程。规范归约过程是最右推导的逆过程。盛威网（www.snwei.com）专业的计算机学习网站9 《编译原理》课后习题答案第六章附加题问题1：对于文法SÆ(L)|aLÆL,S|S(1)给出句子(a,((a,a),(a,a)))的一个最右推导，并指出右句型的句柄；(2)按照(1)的最右推导，说明移进－归约分析器的工作步骤。答案：(1)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),(a,a)))=>(S,((a,a),(a,a)))=>(a,((a,a),(a,a)))(注：句柄下面有下划线)盛威网（www.snwei.com）专业的计算机学习网站10 《编译原理》课后习题答案第六章(2)步骤栈输入动作1#(a,((a,a),(a,a)))#移进2#(a,((a,a),(a,a)))#移进3#(a,((a,a),(a,a)))#归约，SÆa4#(S,((a,a),(a,a)))#归约，LÆS5#(L,((a,a),(a,a)))#移进6#(L,((a,a),(a,a)))#移进7#(L,((a,a),(a,a)))#移进8#(L,((a,a),(a,a)))#移进9#(L,((a,a),(a,a)))#归约，SÆa10#(L,((S,a),(a,a)))#归约，LÆS11#(L,((L,a),(a,a)))#移进12#(L,((L,a),(a,a)))#移进13#(L,((L,a),(a,a)))#归约，SÆa14#(L,((L,S),(a,a)))#归约，LÆL,S15#(L,((L),(a,a)))#移进16#(L,((L),(a,a)))#归约，SÆ(L)17#(L,(S,(a,a)))#归约，LÆS18#(L,(L,(a,a)))#移进19#(L,(L,(a,a)))#移进20#(L,(L,(a,a)))#移进21#(L,(L,(a,a)))#归约，SÆa22#(L,(L,(S,a)))#归约，LÆS23#(L,(L,(L,a)))#移进24#(L,(L,(L,a)))#移进25#(L,(L,(L,a)))#归约，SÆa26#(L,(L,(L,S)))#归约，LÆL,S27#(L,(L,(L)))#移进28#(L,(L,(L)))#归约，SÆ(L)29#(L,(L,S))#归约，LÆL,S30#(L,(L))#移进31#(L,(L))#归约，SÆ(L)32#(L,S)#归约，LÆL,S33#(L)#移进34#(L)#归约，SÆ(L)35#S#接受盛威网（www.snwei.com）专业的计算机学习网站11 《编译原理》课后习题答案第六章问题2：试为下列各文法建立算符优先关系表。E→EandT|TT→TorF|FF→notF|NN→(E)|true|false答案：算符优先关系表如下：truefalsenotandor()#true≯≯≯≯false≯≯≯≯not≮≮≮≯≯≮≯≯and≮≮≮≯≯≮≯≯or≮≮≮≮≯≮≯≯(≮≮≮≮≮≮≡)≯≯≯≯#≮≮≮≮≮≮盛威网（www.snwei.com）专业的计算机学习网站12 《编译原理》课后习题答案第七章第7章LR分析第1题已知文法A→aAd|aAb|ε判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。答案：文法：A→aAd|aAb|ε拓广文法为G′，增加产生式S′→A若产生式排序为：0S"→A1A→aAd2A→aAb3A→ε由产生式知：First(S")={ε,a}First(A)={ε,a}Follow(S")={#}Follow(A)={d,b,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：在I0中：A→.aAd和A→.aAb为移进项目，A→.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I0、I2中：Follow(A)∩{a}={d，b，#}∩{a}=盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第七章所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：题目1的SLR(1)分析表状态（State）ActionGotoadb#A0S2r3r3r311acc2S2r3r3r333S4S54r1r1r15r2r2r2题目1对输入串ab#的分析过程剩余输入串状态栈（statestack）文法符号栈动作（action）（inputleft）0#ab#....Shift02#ab#....Reduceby:A→ε023#aAb#....Shift0235#aAb#....Reduceby:A→aAb01#A#....分析成功，说明输入串ab是文法的句子。盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第七章第2题若有定义二进制数的文法如下：S→L·L|LL→LB|BB→0|1(1)试为该文法构造LR分析表，并说明属哪类LR分析表。(2)给出输入串101.110的分析过程。答案：文法：S→L.L|LL→LB|BB→0|1拓广文法为G′，增加产生式S′→S若产生式排序为：0S"→S1S→L.L2S→L3L→LB4L→B5B→06B→1由产生式知：First(S")={0,1}First(S)={0,1}First(L)={0,1}First(B)={0,1}Follow(S")={#}Follow(S)={#}Follow(L)={.,0,1,#}Follow(B)={.,0,1,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第七章在I2中：B→.0和B→.1为移进项目，S→L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I2、I8中：Follow(s)∩{0，1}={#}∩{0，1}=所以在I2、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。构造的SLR(1)分析表如下：题目2的SLR(1)分析表状态（State）ActionGoto·01#SLB0S4S51231acc.2S6S4S5r273r4r4r4r4.4r5r5r5r5.5r6r6r6r6.6S4S5837r3r3r3r3.8S4S5r17盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第七章题目2对输入串101.110#的分析过程剩余输入串状态栈（statestack）文法符号栈动作（action）（inputleft）0#101.110#....Shift05#101.110#....Reduceby:B→103#B01.110#....Reduceby:S→LB02#L01.110#....Shift024#L01.110#....Reduceby:B→0027#LB1.110#....Reduceby:S→LB02#L1.110#....Shift025#L1.110#....Reduceby:B→1027#LB.110#....Reduceby:S→LB02#L.110#....Shift026#L.110#....Shift0265#L.110#....Reduceby:B→10263#L.B10#....Reduceby:S→B0268#L.L10#....Shift02685#L.L10#....Reduceby:B→102687#L.LB0#....Reduceby:S→LB0268#L.L0#....Shift02684#L.L0#....Reduceby:B→002687#L.LB#....Reduceby:S→L.L01#S#....分析成功，说明输入串101.110是题目2文法的句子。盛威网（www.snwei.com）专业的计算机学习网站5 《编译原理》课后习题答案第七章第3题考虑文法SÆAS|bAÆSA|a(1)构造文法的LR(0)项目集规范族及相应的DFA。(2)如果把每一个LR(0)项目看成一个状态，并从每一个形如BÆα·Xβ的状态出发画一条标记为X的箭弧刀状态BÆαX·β，而且从每一个形如BÆα·Aβ的状态出发画标记为ε的箭弧到所有形如AÆ·γ的状态。这样就得到了一个NFA。说明这个NFA与(a)中的DFA是等价的。(3)构造文法的SLR分析表。(4)对于输入串bab，给出SLR分析器所作出的动作。(5)构造文法的LR(1)分析表和LALR分析表。答案：(1)令拓广文法G’为(0)S’ÆS(1)SÆAS(2)SÆb(3)AÆSA(4)AÆa其LR(0)项目集规范族及识别该文法活前缀的DFA如下图所示：FOLLOW(S)={#,a,b}FOLLOW(A)={a,b}LR(0)项目：盛威网（www.snwei.com）专业的计算机学习网站6 《编译原理》课后习题答案第七章(2)显然，对所得的NFA求ε闭包，即得上面的LR(0)项目集，即DFA中的状态。故此NFA与(a)中DFA是等价的。(3)文法的SLR分析表如下：actiongoto状态ab#SA0S4S3121S4S3acc652S4S3723r2r2r24r4r45S4/r3S3/r3726S4S3657S4/r1S3/r1r165因为I5中：FOLLOW（A）∩{a，b}≠ФI7中：FOLLOW（S）∩{a，b}≠Ф所以，该文法不是SLR（1）文法。盛威网（www.snwei.com）专业的计算机学习网站7 《编译原理》课后习题答案第七章或者：从分析表中可看出存在歧义，所以不是该文法SLR（1）文法。注意：不是SLR(1)文法就不能构造SLR(1)分析表，也不能作分析过程。(4)对于输入串bab，SLR分析器所作出的动作如下：步骤状态栈符号栈当前字符剩余字符串动作(1)0#bab#移进(2)03#bab#归约SÆb(3)01#Sab#移进(4)014#Sab#归约AÆa(5)015#SAb#归约AÆSA(6)02#Ab#移进(7)023#Ab#归约SÆb(8)027#AS#归约SÆAS(9)01#S#接受（在第5个动作产生歧义）(5)LR(1)项目集族为：I0:S’Æ·S,#SÆ·AS,#SÆ·b,#SÆ·SA,a/bAÆ·a,a/bI1:S’ÆS·,#AÆS·A,a/bAÆ·a,a/bAÆ·SA,a/bSÆ·AS,a/bSÆ·b,a/bI2:SÆA·S,#SÆ·b,#SÆ·AS,#AÆ·SA,a/b盛威网（www.snwei.com）专业的计算机学习网站8 《编译原理》课后习题答案第七章AÆ·a,a/bI3:SÆb·,#I4:AÆa·,a/bI5:AÆSA·,a/bSÆA·S,a/bSÆ·AS,a/bSÆ·b,a/bAÆ·SA,a/bAÆ·a,a/bI6:AÆS·A,a/bAÆ·SA,a/bAÆ·a,a/bSÆ·AS,a/bSÆ·b,a/bI7:SÆb·,a/bI8:SÆAS·,#AÆS·A,a/bAÆ·SA,a/bAÆ·a,a/bSÆ·AS,a/bSÆ·b,a/bI9:SÆA·S,#SÆ·AS,#SÆ·b,#SÆ·SA,a/bAÆ·a,a/bI10:SÆAS·,a/bAÆS·A,a/bAÆ·SA,a/bAÆ·a,a/bSÆ·b,a/bSÆ·AS,a/bI11:盛威网（www.snwei.com）专业的计算机学习网站9 《编译原理》课后习题答案第七章SÆA·S,a/bSÆ·b,a/bSÆ·AS,a/bAÆ·SA,a/bAÆ·a,a/bI12:SÆSA·,a/bSÆA·S,a/bSÆ·b,a/bSÆ·AS,a/bAÆ·SA,a/bAÆ·a,a/b∵I5状态集中存在“归约――移进”冲突，故无法构造LR(1)分析表，因而也就无法构造LALR分析表。注意：其实是可以构造的，这个题目出得不太严格。因为书上的定义是：根据这种文法构造的LR（1）分析表不含多重定义时，称这样的分析表为LR（1）分析表，能用LR（1）分析表的分析器称为LR（1）分析器（规范的LR分析器），能构造的LR（1）分析表的文法称为LR（1）文法。教材习题：（1）列出这个文法的所有LR(0)项目（2）按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR(0)规范族（3）这个文法是SLR的吗？若是，构造出它的SLR分析表（4）这个文法是LALR或LR(1)的吗？答：（1）令拓广文法G’为0S’ÆS1SÆAS2SÆb盛威网（www.snwei.com）专业的计算机学习网站10 《编译原理》课后习题答案第七章3AÆSA4AÆa其LR(0)项目：(2)识别这个文法活前缀的NFA如上图所示：确定化为DFA如下图所示：盛威网（www.snwei.com）专业的计算机学习网站11 《编译原理》课后习题答案第七章（3）因为I5中：FOLLOW（A）∩{a，b}≠ФI7中：FOLLOW（S）∩{a，b}≠Ф所以，该文法不是SLR（1）文法。（4）LR(1)项目集族为：I0:S’Æ·S,#SÆ·AS,#SÆ·b,#SÆ·SA,a/bAÆ·a,a/bI1:S’ÆS·,#AÆS·A,a/bAÆ·a,a/bAÆ·SA,a/bSÆ·AS,a/bSÆ·b,a/b盛威网（www.snwei.com）专业的计算机学习网站12 《编译原理》课后习题答案第七章I2:SÆA·S,#SÆ·b,#SÆ·AS,#AÆ·SA,a/bAÆ·a,a/bI3:SÆb·,#I4:AÆa·,a/bI5:AÆSA·,a/bSÆA·S,a/bSÆ·AS,a/bSÆ·b,a/bAÆ·SA,a/bAÆ·a,a/bI6:AÆS·A,a/bAÆ·SA,a/bAÆ·a,a/bSÆ·AS,a/bSÆ·b,a/bI7:SÆb·,a/bI8:SÆAS·,#AÆS·A,a/bAÆ·SA,a/bAÆ·a,a/bSÆ·AS,a/bSÆ·b,a/bI9:SÆA·S,#SÆ·AS,#SÆ·b,#SÆ·SA,a/bAÆ·a,a/bI10:SÆAS·,a/bAÆS·A,a/bAÆ·SA,a/b盛威网（www.snwei.com）专业的计算机学习网站13 《编译原理》课后习题答案第七章AÆ·a,a/bSÆ·b,a/bSÆ·AS,a/bI11:SÆA·S,a/bSÆ·b,a/bSÆ·AS,a/bAÆ·SA,a/bAÆ·a,a/bI12:SÆSA·,a/bSÆA·S,a/bSÆ·b,a/bSÆ·AS,a/bAÆ·SA,a/bAÆ·a,a/b因为I5状态集中存在“归约――移进”冲突，所以不是LR(1)文法，也不是LALR文法。盛威网（www.snwei.com）专业的计算机学习网站14 《编译原理》课后习题答案第七章第6题文法G=({U,T,S},{a,b,c,d,e},P,S)其中P为：S→UTa|TbT→S|Sc|dU→US|e(1)判断G是LR(0)，SLR(1)，LALR(1)还是LR(1)，说明理由。(2)构造相应的分析表。答案：文法：S→UTa|TbT→S|Sc|dU→US|e拓广文法为G"，增加产生式S"→S若产生式排序为：0S"→S1S→UTa2S→Tb3T→S4T→Sc5T→d6U→US7U→e由产生式知：First(S")={d,e}First(S)={d,e}First(U)={e}First(T)={d,e}Follow(S")={#}Follow(S)={a,b,c,d,e,#}Follow(U)={d,e}Follow(T)={a,b}盛威网（www.snwei.com）专业的计算机学习网站15 《编译原理》课后习题答案第七章G′的LR(0)项目集族及识别活前缀的DFA如下图所示：在I1中：S"→S.为接受项目，T→S.为归约项目，T→S.c为移进项目，存在接受-归约和移进-归约冲突，因此所给文法不是LR(0)文法。在I1中：Follow(S")∩Follow(T)={#}∩{a，b}=Follow(T)∩{c}={a，b}∩{c}=在I8中：Follow(U)∩Follow(T)∩{c}={d,e}∩{a，b}∩{c}=所以在I1中的接受-归约和移进-归约冲突与I8中的移进-归约和归约-归约冲突可以由Follow集解决，所以G是SLR(1)文法。盛威网（www.snwei.com）专业的计算机学习网站16 《编译原理》课后习题答案第七章构造的SLR(1)分析表如下：状态ActionGoto（State）abcde#SUT0S5S41231r3r3S6Acc2S5S48273S94r7r75r5r56r4r47S10S98r3r3S6r6r69r2r2r2r2r2r210r1r1r1r1r1r1第8题证明文法：S→A$A→BaBb|DbDaB→εD→ε是LR(1)但不是SLR(1)。(其中"$"相当于"#")答案：文法：A→BaBb|DbDaB→εD→ε拓广文法为G′，增加产生式S′→A若产生式排序为：0S"→A1A→BaBb2A→DbDa3B→ε4D→ε由产生式知：First(S")={a,b}盛威网（www.snwei.com）专业的计算机学习网站17 《编译原理》课后习题答案第七章First(A)={a,b}First(B)={ε}First(D)={ε}Follow(S")={#}Follow(A)={#}Follow(B)={a,b}Follow(D)={a,b}G′的LR(1)项目集族及识别活前缀的DFA如下图所示：在I0中：B→.,a和T→.，b为归约项目，但它们的搜索符不同，若当前输入符为a时用产生式B→ε归约，为b时用产生式D→ε归约，所以该文法是LR(1)文法。若不看搜索符，在I0中项目B→.和T→.为归约-归约冲突，而Follow(B)∩Follow(D)={a,b}∩{a,b}≠，冲突不能用Follow集解决，所以该文法不是SLR(1)文法。构造的LR(1)分析表如下：题目4的LR(1)分析表StateActionGotoa.b.#ABD0r3r4......1231Acc.2S4.............3S5.4r365r4............76S87S9............8r19r2盛威网（www.snwei.com）专业的计算机学习网站18 《编译原理》课后习题答案第七章第16题给定文法：S→doSorS|doS|S;S|act(1)构造识别该文法活前缀的DFA。(2)该文法是LR(0)吗?是SLR(1)吗?说明理由。(3)若对一些终结符的优先级以及算符的结合规则规定如下：a)or优先性大于do;b);服从左结合；c);优先性大于do；d);优先性大于or；请构造该文法的LR分析表,并说明LR(0)项目集中是否存在冲突和冲突如何解决的。答案：首先化简文法,用d代替do;用o代替or;用a代替act;文法可写成：S→dSoS|dS|S;S|a拓广文法为G"，增加产生式S′→S若产生式排序为：0S"→S1S→dSoS2S→dS3S→S;S4S→a由产生式知：First(S")={d,a}First(S)={d,a}Follow(S")={#}Follow(S)={o,;,#}(1)识别该文法活前缀的DFA如下图。盛威网（www.snwei.com）专业的计算机学习网站19 《编译原理》课后习题答案第七章(2)该文法不是LR(0)也不是SLR(1)因为：在I5、I6、和I8中存在移进-归约冲突，因此所给文法不是LR(0)文法。又由于Follow(S)={o,;,#}在I6、和I8中：Follow(S)∩{;}={o,;,#}∩{;}={;}≠在I5中：Follow(S)∩{;,o}={o,;,#}∩{;,o}={;,o}≠所以该文法也不是SLR(1)文法。此外很容易证明所给文法是二义性的，S`→S→dSoS→ddSoSS`→S→dS→ddSoS因此该文法不可能满足LR文法。(3)若对一些终结符的优先级以及算符的结合规则规定如下：a)or优先性大于do;b);服从左结合；c);优先性大于do；d);优先性大于or；盛威网（www.snwei.com）专业的计算机学习网站20 《编译原理》课后习题答案第七章则：在I5中：“or和;优先性都大于do”，所以遇输入符o和;移进；遇#号归约。在I6中：“;号服从左结合”，所以遇输入符属于Follow(S)的都应归约。在I8中：“;号优先性大于do”，所以遇输入符为;号移进；遇o和#号归约。此外，在I1中：接受和移进可以不看成冲突，因为接受只有遇#号。由以上分析，所有存在的移进-归约冲突可用规定的终结符优先级以及算符的结合规则解决，所构造的LR分析表如下：状态ActionGoto（State）do;a#S0S2S311S4Acc2S2S353r4r4r44S2S365S7S4r26r3r3r37S2S388r1r4r1盛威网（www.snwei.com）专业的计算机学习网站21 《编译原理》课后习题答案第七章附加题问题1：试判别如下文法是否LR(0)或SLR(1)文法:a)文法G[E]:E→E+T⏐TT→(E)⏐id⏐id[E]其中E,T为非终结符,其余符号为终结符b)文法G[S]:S→Ab⏐ABcA→aA⏐aB→b其中S,A,B为非终结符,其余符号为终结符答案：a)增加产生式S→E，得增广文法G’[S]构造识别活前缀的有限状态机如下：盛威网（www.snwei.com）专业的计算机学习网站22 《编译原理》课后习题答案第七章可验证：状态I3有移进-归约冲突，所以G[E]不是LR(0)文法；进一步，因Follow(T)={+,},},#}，不含[，所以G[E]是SLR(1)文法。b)增加产生式S’→S，得增广文法G’[S’]构造识别活前缀的有限状态机如下：I4存在归约/归约冲突，I3存在归约/移进冲突.因此不是LR(0)文法。考察能否使用SLR(1)方法解决冲突：I4中，因为Follow(S)={#}而Follow(B)={c}.所以可以解决。I3中，因Follow(A)={b}，不含a，因此该移进/归约冲突也可解决.文法是SLR(1)文法参考解答：为下列文法构造LR（1）分析表，并给出串baab#的分析过程:增广文法文法G[S’]:(0)S"→S(1)S→XX(2)X→aX(3)X→b其中S’,S,X为非终结符,其余符号为终结符参考解答：参见教材P146的例子,自行补充对输入串baab#的分析过程盛威网（www.snwei.com）专业的计算机学习网站23 《编译原理》课后习题答案第七章问题2：（1）构造下列文法G（P’）的LR（1）FSM，验证它是LR（1）文法:(0)P"→P(1)P→P(P)(2)P→Aa(3)P→ε(4)A→ε其中P’,P,A为非终结符（2）通过合并同芯集（状态）的方法构造相应于上述LR（1）FSM的LALR（1）FSM，并判断G（P’）是否LALR（1）文法？答案：（1）构造文法G（P’）的LR（1）项目集族和转换函数如下：PI0:I1:I9:S′→.P,#S′→P.,#P→Aa.,(/)P→.P(P),(/#P→P.(P),(/#P→.Aa,(/#(aP→.,(/#A→.,aI3:AI6:AP→P(.P),(/#P→A.a,(/)P→.P(P),(/)AI2:P→.Aa,(/)P→A.a,(/#P→.,(/)I8:A→.,aP→P(.P),(/)aPP→.P(P),(/)I4:P→.Aa,(/)(P→Aa.,(/#I5:P→.,(/)P→P(P.),(/#A→.,a)P→P.(P),(/)(PI10:)I7:I11:P→P(P.),(/)P→P(P).,(/#P→P(P).,(/)P→P.(P),(/)其中的每个状态均无宏冲突，所以G（P’）是LR（1）文法。（2）可以看出：I2和I6，I3和I8，I4和I9，I5和I10，I7和I11是同芯状态.通过合并同芯状态的方法构造相应于上述LR（1）转换图的LALR（1）转换图如下：盛威网（www.snwei.com）专业的计算机学习网站24 《编译原理》课后习题答案第七章PI0:I1:S′→.P,#S′→P.,#P→.P(P),(/#P→P.(P),(/#P→.Aa,(/#(P→.,(/#A→.,aI3-8:AP→P(.P),(/)/#P→.P(P),(/)I2-6:AP→.Aa,(/)P→A.a,(/)/#P→.,(/)A→.,aaP(I4-9:I5-10:I7-11:)P→Aa.,(/)/#P→P(P.),(/)/#P→P(P).,(/)/#P→P.(P),(/)可以看出:所有状态都不存在移进-归约和归约-归约冲突.所以,G（P’）是LALR（1）文法。问题3：设文法G为：SÆAAÆBA|εBÆaB|b(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表；(3)给出输入符号串abab的分析过程。答案：(1)拓广文法G’:(0)S’ÆS(1)SÆA(2)AÆBA(3)AÆε(4)BÆaB(5)BÆbFIRST(A)={ε,a,b}盛威网（www.snwei.com）专业的计算机学习网站25 《编译原理》课后习题答案第七章FIRST(B)={a,b}构造的DFA如下:I1:[S’ÆS•,#]SI2:I0:[SÆA•,#][S’Æ•S,#]A[SÆ•A,#][AÆ•BA,#]I3:BI6:[AÆ•,#]B[AÆB•A,#][AÆBA•,#][BÆ•aB,a|b|#][AÆ•BA,#]A[BÆ•b,a|b|#][AÆ•,#]a[BÆ•aB,a|b|#][BÆ•b,a|b|#]bbaI7:B[BÆaB•,a|b|#]I5:bI4:[BÆb•,a|b|#][BÆa•B,a|b|#][BÆ•aB,a|b|#][BÆ•b,a|b|#]a由项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。(2)LR(1)分析表如下：ActionGoto状态aB#SAB0S4S5r31231acc2r13S4S5r3634S4S575r5r5r5盛威网（www.snwei.com）专业的计算机学习网站26 《编译原理》课后习题答案第七章6r27r4r4r4(3)输入串abab的分析过程为：步骤状态栈符号栈当前字符剩余字符串动作(1)0#abab#移进(2)04#abab#移进(3)045#abab#归约BÆb(4)047#aBab#归约BÆaB(5)03#Bab#移进(6)034#Bab#移进(7)0345#Bab#归约BÆb(8)0347#BaB#归约BÆaB(9)033#BB#归约AÆε(10)0336#BBA#归约AÆBA(11)036#BA#归约AÆBA(12)02#A#归约SÆA(13)01#S#acc问题4：给定文法G’(S’):S’→SS→（L）⏐aL→L,S⏐S试为该文法配上属性计算的语义规则（或动作）集合（即设计一个属性文法），它输出配对括号的个数。如对于句子(a,(a))，输出是2。答案：产生式语义规则S′→S{print(S.num)}S→(L){S.num:=L.num+1}S→a{S.num:=0}L→L1,S{L.num:=L1.num+S.num}L→S{L.num:=S.num}盛威网（www.snwei.com）专业的计算机学习网站27 《编译原理》课后习题答案第七章问题5：给定文法G[S]:S→（L）⏐aL→L,S⏐S如下是相应于G[S]的一个属性文法：(1)S→（L）{S.num:=L.num+1;}(2)S→a{S.num:=0;}(3)L→L1,S{L.num:=L1.num+S.num;}(4)L→S{L.num:=S.num;}下图分别是输入串(a，(a))的语法分析树和对应的带标注语法树，但其属性值没有标出，试将其标出（即填写右下图中符号“=”右边的值）。答案：盛威网（www.snwei.com）专业的计算机学习网站28 《编译原理》课后习题答案第七章问题6：对上题中所给的G[S]的属性文法是一个S-属性文法，故可以在自下而上分析的过程中，增加一个语义栈来计算属性值。下图（a）是G[S]的一个LR分析表,图(b)描述了输入串(a，(a))的分析和计值过程（语义栈中的值对应S.num或L.num），其中，第14），15）行没有给出，试补齐之。题3图（a）盛威网（www.snwei.com）专业的计算机学习网站29 《编译原理》课后习题答案第七章题3图（b）答案：14）0246--1-#(L)#15）01-2#S#问题7：下面的属性文法G[N]可以将一个二进制小数转换为十进制小数，令N.val为G[N]生成的二进制数的值，例如对输入串101.101,N.val=5.625.2121−S.len2N→S‘•’S{N.val:=S.val+2*S.val;}111S→SB{S.val:=2*S.val+B.val;S.len:=S.len+1}S→B{S.val=B.val;S.len:=1}B→‘0’{B.val:=0}盛威网（www.snwei.com）专业的计算机学习网站30 《编译原理》课后习题答案第七章B→‘1’{B.val:=1}（1）试消除该属性文法（翻译模式）中的左递归，以便可以得到一个可以进行自上而下进行语义处理（翻译）的翻译模式；（2）对变换后的翻译模式，构造一个自上而下预测翻译程序。答案：（1）消去原文法中的左递归：N→S‘•’SS→BRR→BRR→εB→‘0’B→‘1’可验证该文法是LL（1）文法。再考虑语义规则，得到如下翻译模式：2121−S.len2N→S‘•’S{N.val:=S.val+2*S.val;}S→B{R.ival:=B.val;R.ilen:=1}R{S.val:=R.sval;S.len:=R.slen}1111R→B{R.ival:=2*R.ival+B.val;R.ilen:=R.ilen+1}R{R.sval:=R.sval;1R.slen:=R.slen}R→ε{R.sval:=R.ival;R.slen:=R.ilen}B→‘0’{B.val:=0}B→‘1’{B.val:=1}(2)对变换后的翻译模式，可构造一个如下的自上而下预测翻译程序：realParseN(){1(S1val,S1len):=ParseS();//变量S1val,S1len分别对应属性S.val,1S.lenMatchToken(‘•’);//匹配‘•’,函数MatchToken参见第4讲，本例省略2(S2val,S2len):=ParseS();//变量S2val,S2len分别对应属性S.val,2S.lenNval:=S1val+2^(-S2len)*S2val;/变量Nval对应属性N.valreturnNval;}(int,int)ParseS()//（int,int）代表一个记录/结构类型{盛威网（www.snwei.com）专业的计算机学习网站31 《编译原理》课后习题答案第七章Bval:=ParseB();Rival:=Bval;Rilen:=1;(Rsval,Rslen):=ParseR(Rival,Rilen);Sval:=Rsval;Slen:=Rslen;return(Sval,Slen);}(int,int)ParseR(intRival,intRilen){switch(lookahead){//lookahead为下一个输入符号case′0′,′1′:Bval:=ParseB();R1ival:=2*Rival+Bval;R1ilen:=Rilen+1；(R1sval,R1slen):=ParseR(R1ival,R1ilen);Rsval:=R1sval;Rslen:=R1slen;break;case′•′,′#′:Rsval:=Rival;Rslen:=Rilen;break;default:printf("syntaxerrorn")exit(0);}return(Rsval,Rslen);}intParseB(){switch(lookahead){case′0′:MatchToken(‘0’);Bval:=0;break;case′1′:MatchToken(‘1’);Bval:=1;break;default:printf("syntaxerrorn")exit(0);盛威网（www.snwei.com）专业的计算机学习网站32 《编译原理》课后习题答案第七章}returnBval;}问题8：对于上题（1）所得到的翻译模式（结果应满足L-属性的条件），在进行自下而上的语义处理时，语义栈中的值有两个分量，分别对应文法符号的综合属性val和len。（1）若该翻译模式中，嵌在产生式中间的语义规则集中含有除复写规则之外的语义规则，则变换该翻译模式，使嵌在产生式中间的语义规则集中仅含复写规则；（2）根据（1）所得到的新翻译模式，文法符号的所有继承属性均可以通过归约前已出现在分析栈中的综合属性进行访问。试写出在按每个产生式归约时语义处理的代码片断（设语义栈由向量v表示，归约前栈顶位置为top，语义值v[i]的两个分量分别用v[i].val和v[i].len表示）。答案：(1)将如下翻译模式2121−S.len2N→S‘•’S{N.val:=S.val+2*S.val;}S→B{R.ival:=B.val;R.ilen:=1}R{S.val:=R.sval;S.len:=R.slen}1111R→B{R.ival:=2*R.ival+B.val;R.ilen:=R.ilen+1}R{R.sval:=R.sval;1R.slen:=R.slen}R→ε{R.sval:=R.ival;R.slen:=R.ilen}B→‘0’{B.val:=0}B→‘1’{B.val:=1}变换为：2121−S.len2N→S‘•’S{N.val:=S.val+2*S.val;}S→B{M.bval:=B.val}M{R.ival:=M.sval;R.ilen:=M.val}R{S.val:=R.sval;S.len:=R.slen}1R→B{P.rival:=R.ival;P.rilen:=R.ilen;P.bval:=B.val;}P{R.ival:=P.sval;1111R.ilen:=P.slen}R{R.sval:=R.sval;R.slen:=R.slen}R→ε{R.sval:=R.ival;R.slen:=R.ilen}B→‘0’{B.val:=0}B→‘1’{B.val:=1}M→ε{M.sval:=M.bval;M.val:=1}P→ε{P.sval=2*P.rival+P.bval;P.sleP:=P.rilen+1}(2)按每个产生式归约时语义处理的代码片断:12N→S‘•’S{v[top-2].val:=v[top-2].val+2^(-v[top].len)*v[top].val;}S→BMR{v[top-2].val:=v[top].val;v[top-2].len:=v[top].len}1R→BPR{v[top-2].val:=v[top].val;v[top-2].len:=v[top].len}R→ε{v[top+1].val:=v[top].val;v[top+1].len:=v[top].len}盛威网（www.snwei.com）专业的计算机学习网站33 《编译原理》课后习题答案第七章B→‘0’{v[top].val:=0}B→‘1’{v[top].val:=1}M→ε{v[top+1].val:=v[top].val;v[top+1].len:=1}P→ε{v[top+1].val:=2*v[top-1].val+v[top].val;v[top+1].len:=v[top-1].len+1}问题9：证明LR分析过程正确性的一个重要引理：由构造LR(0)项目集规范族得到的DFA，它可以也只能读进所分析文法的活前缀。需要证明两个方面：命题1所有活前缀一定都可由DFA读进，即不会错过合法的归约。命题2DFA只能读活前缀。证明思路：首先要了解活前缀是如何产生的。活前缀的集合Prefix可归纳定义如下：（1）设S’是增广文法的开始符号，既有产生式S’→S（S是原文法的开始符号），令S∈Prefix。（2）若v∈Prefix，则v的任一前缀u都是活前缀，即u∈Prefix。（3）若v∈Prefix，且v中至少包含一个非终结符，即可以将v写成αBγ，其中B为非终结符。若有产生式B→β，则αβ的任一前缀u都是活前缀，即u∈Prefix。（4）Prefix中的元素只能通过上述步骤产生。命题1可以根据Prefix的定义进行归纳证明。基础：对于由规则（1）产生的活前缀S∈Prefix，由于在DFA的初始项目集（状态）I0中含有项目S’→·S，显然S是可以被DFA读进的。归纳：若v∈Prefix，且v可以被DFA读进，则v的前缀可以被DFA读进也是显然的。若v∈Prefix，且可以将v写成αBγ，其中B为非终结符并有产生式B→β。设DFA在从初态I0读进α后进入状态I。因为v=αBγ可以被DFA读进，所以在状态I可以读进B，根据DFA的构造过程，一定存在项目C→α·Bγ’∈I。由闭包的计算过程，可知一定有B→·β∈I，因此β是从I开始后续的可读串。所以，从初态I0开始，αβ的任一前缀u都是可读进的。命题1证毕。命题2可归纳于DFA可读序列的长度n来证明。基础：n=0。显然空序列ε是活前缀。盛威网（www.snwei.com）专业的计算机学习网站34 《编译原理》课后习题答案第七章归纳：设αX是DFA可读序列，且⏐αX⏐=n+1，其中X是某个文法符号。在读过α后，DFA一定处于状态I，在此状态下X是可读的。根据DFA的构造过程，一定存在项目C→β·Xγ∈I。该项目或者是基本项目，或者是通过闭包计算得到的项目。下面分这两种情形来讨论。1）C→β·Xγ是基本项目。若⏐β⏐=0，则该项目只能是S’→·S，此时αX=S显然是活前缀。若⏐β⏐=m≠0，则DFA从状态I0读进n-m个符号的序列μ后进入状态I’，且必定有C→·βXγ∈I’。根据DFA的构造过程，一定存在项目B→·Cγ’∈I’。这样在状态I’下，可以读进B。因为⏐μB⏐≤n，由归纳假设，可知μB是活前缀。因此，由活前缀集合的归纳定义，得知μβX=αX是活前缀。2）C→β·Xγ是通过闭包计算得到的项目。此时，β一定为空序列，而项目C→·Xγ一定是由I中的某个基本项目B→μ·C0ν直接或间接地通过闭包计算序列得到的：C0→·C1γ1，C1→·C2γ2，…，Ck→·Cγk+1。由1）的讨论结果，可知αC0是活前缀。从而αC1，αC2，…，αCk都是或前缀，αC也是活前缀。所以，αX是活前缀。命题2证毕。盛威网（www.snwei.com）专业的计算机学习网站35 《编译原理》课后习题答案第八章第8章语法制导翻译和中间代码生成第1题给出下面表达式的逆波兰表示(后缀式)：(1)a*(-b+c)(2)if(x+y)*z=0thens∶∶=(a+b)*celses=a*b*c答案：给出下面表达式的逆波兰表示(后缀式)：(1)ab-c+*(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else运算）如果写成这样：xy+z*0=sab+c*:=sabc**:=￥，则是错误的，因为写表达式和赋值语句的中间代码序列，或是写它们的代码生成过程，必须注意按照算符优先序进行，这实际上是按照LR分析过程进行的。例如：写出赋值语句a:=a+b*c*(d+e)的四元式中间代码,当前四元式序号为100。不能写成：100(+,d,e,t1)101(*,b,c,t2)102(*,t2,t1,t3)103(+,a,t3,t4)104(:=,t4,-,a)应该写成：100(*,b,c,t1)101(+,d,e,t2)102(*,t1,t2,t3)103(+,a,t3,t4)104(:=,t4,-,a)第2题请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式、四元式序列、树形、逆波兰，当前序号为100。答案：三元式：100(+,a,b)101(+,c,d)102(*,(1),(2))盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第八章103(-,(3),/)104(+,a,b)105(+,(5),c)106(-(4),(6))间接三元式：间接三元式序列间接码表100(+，a,b)(100)101(+，c,d)(101)102(*，(1),(2))(102)103(-，(3),/)(103)104(+，(1),c)(100)(104)105(-，(4),(1))(105)或者：间接三元式：100(+，a,b)101(+，c,d)102(*，(1),(2))103(-，(3),/)104(+，(1),c)105(-，(4),(1))间接码表：100101102103100104105四元式：100(+,a,b,t1)101(+,c,d,t2)102(*,t1,t2,t3)103(-,t3,/,t4)104(+,a,b,t5)105(+,t5,c,t6)106(-,t4,t6,t7)树形：盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第八章逆波兰：ab+cd+*-ab+c+-［典型例题］：写出ifAandBandC>DthenifAD的四元式*/(2)(j,_,_,13)(3)(jnz,B,_,5)(4)(j,_,_,13)(5)(j>,C,D,7)(6)(j,_,_,13)(7)(j<,A,B,9)/*AD)thenX:=Y+Z翻译成四元式答案：假定翻译的四元式序列从（100）开始：（100）ifAidE.code:=id.lexeme;问题4：有文法：S→(L)|aL→L,S|S给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对括号的个数。如对于句子(a,(a,a))，输出是2。（中国科学院计算所1994）答案：加入新开始符号S"和产生式S"→S，设num为综合属性，代表值属性，则语法制导定义如下：产生式语义规则S"→Sprint(S.num)S→(L)S.num:=L.num+1S→aS.num:=0L→L1,SL.num:=L1.num+S.numL→SL.num:=S.num盛威网（www.snwei.com）专业的计算机学习网站13 《编译原理》课后习题答案第八章问题5：文法G的产生式如下：S→(L)|aL→L,S|S①试写出一个语法制导定义，它输出配对括号个数；②写一个翻译方案，打印每个a的嵌套深度。如((a),a),打印2,1。（中国科学院软件所1999）答案：①为S,L引入综合属性num，代表配对括号个数；语法制导定义产生式语义动作S"→Sprint(S.num)S→(L)S.num:=L.num+1S→aS.num:=0L→L1,SL.num:=L1.num+S.numL→SL.num:=S.num②引入继承属性f,代表嵌套深度S"→{S.f:=0}SS→"("{L.f:=S.f+1;}L")"S→a{print(S.f);}L→{L1.f:=L.f;}L1,{S.f:=L.f}SL→{S.f:＝L．f;}S盛威网（www.snwei.com）专业的计算机学习网站14 《编译原理》课后习题答案第八章问题6：对下面的文法，只利用综合属性获得类型信息。DÆL,id|LLÆTidTÆint|real答案：语法制导定义产生式语义规则DÆL,idD.type:=L.typeaddtype(id.entry,L.type)DÆLD.type:=L.typeLÆTidL.type:=T.typeaddtype(id.entry,T.type)TÆintT.type:=integerTÆrealT.type:=real盛威网（www.snwei.com）专业的计算机学习网站15 《编译原理》课后习题答案第八章问题7：下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果为整数，否则为实数。EÆTRRÆ+TR|εTÆnum.num|numa)给出语法制导定义确定每个子表达式的类型。b)把表达式翻译成前缀形式，并且决定类型。试用一元运算符inttoreal把整型值转换为相等的实型值，以使得前缀表达式中两个运算对象是同类型的。答案：a)设type是综合属性，代表各非终结符的“类型”属性设in是继承属性，翻译方案产生式语义规则EÆT{R.i:=T.type}R{E.Type:=R.s}RÆ+T{IF(R.i=integer)and(T.type=integer)THENR1.i:=integerELSER1.i:=real}R1{R.s:=R1.s}RÆε{R.s:=R.i}TÆnum.numT.type:=realTÆnumT.type:=integerb)设属性s和i用于传递属性type，属性t和j用于传递属性val。盛威网（www.snwei.com）专业的计算机学习网站16 《编译原理》课后习题答案第八章翻译方案产生式语义规则EÆT{R.i:=T.type}{R.j:=T.val}R{E.Type:=R.s}{E.val:=R.t}RÆ+T{IF(R.i=integer)and(T.type=integer)THENBEGINR1.i:=integerPrint(‘+’,R.j,T.val)R1.j:=R.j+T.valENDELSEBEGINR1.i:=realIFR.i=integerTHENBeginR.i:=realR.j:=inttoreal(R.j)EndIFT.type=integerTHENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint(‘+’,R..j,T.val)R1.j:=R.j+T.valEND}R1{R.s:=R1.s}{R.t:=R1.t}RÆε{R.s:=R.i}{R.t:=R.j}TÆnum.num{T.type:=real}{T.val:=num.num.lexval}TÆnum{T.type:=integer}{T.val:=num.lexval}盛威网（www.snwei.com）专业的计算机学习网站17 《编译原理》课后习题答案第八章问题8：翻译算术表达式a*-(b+c)为a)一棵语法树b)后缀式*c)三地址代码auminus答案：+a)语法树：b)后缀式:bcabc+uminus*c)三地址代码:t1:=b+ct2:=-t1t3:=a*t2问题9：翻译算术表达式–(a+b)*(c+d)+(a+b+c)为a)四元式b)三元式c)间接三元式答案：先写出三地址代码为：t1:=a+bt2:=-t1t3:=c+dt4:=t2*t3t5:=a+bt6:=t5+ct7:=t4+t6a)：对应的四元式为：oparg1arg2result(0)+abt1(1)uminust1t2(2)+cdt3(3)*t2t3t4(4)+abt5(5)+t5ct6(6)+t4t6t7盛威网（www.snwei.com）专业的计算机学习网站18 《编译原理》课后习题答案第八章b)：对应的三元式为：oparg1arg2(0)+ab(1)Uminus(0)(2)+cd(3)*(1)(2)(4)+ab(5)+(4)c(6)+(3)(5)c)：对应的间接三元式为：statementoparg1arg2(0)1515+ab(1)1616uminus15(2)1717+cd(3)1818*1617(4)1519+15c(5)1920+1819(6)20问题10：将下列赋值语句译成三地址代码。A[i,j]:=B[i,j]+C[A[k,l]]+D[i+j]答案：t11:=i*20t12:=t11+jt13:=A-84;t14:=4*t12t15:=t13[t14]//A[i,j]t21:=i*20t22:=t21+jt23:=B-84;t24:=4*t22t25:=t23[t24]//B[i,j]t31:=k*20t32:=t31+l盛威网（www.snwei.com）专业的计算机学习网站19 《编译原理》课后习题答案第八章t33:=A-84t34:=4*t32t35:=t33[t34]//A[k,l]t36:=4*t35t37:=C-4t38:=t37[t36]//C[A[k,l]]t41:=i+jt42:=4*t41t43:=D-4t44:=t43[t42]//D[i+j]t1:=t25+t38t2:=t1+t44t23[t24]:=t2问题11：写出for语句的翻译方案答案：产生式动作SÆforEdoS1S.begin:=newlabelS.first:=newtempS.last:=newtempS.curr:=newtempS.code:=gen(S.first“:=”E.init)||gen(S.last“:=”E.final)||gen(“if”S.first“>”S.last“goto”S.next)||gen(S.curr“:=”S.first)||gen(S.begin“:”)||gen(“if”S.curr“>”S.Last“goto”S.next)||S1.code||gen(S.curr:=succ(S.curr))||gen(“goto”S.begin)EÆv:=initialtofinalE.init:=initial.placeE.final:=final.place盛威网（www.snwei.com）专业的计算机学习网站20 《编译原理》课后习题答案第八章问题12：写出说明语句中的名字和类型及相对地址的翻译模式，以允许在形如DÆid:T的说明中可用一串名字表来代替单个名字。答案：产生式动作PÆ{offset:=0}DDÆD;DDÆidL{enter(id.name,L.type,offset)offset:=offset+L.width}LÆid,L1{L.type:=L1.typeL.width:=L1.widthenter(id.name,L1.type,offset)offset:=offset+L1.width}LÆ:T{L.type:=T.typeL.width:=T.width}TÆinteger{T.type:=integerT.width:=4}TÆreal{T.type:=realT.width:=8}TÆarray[num]ofT1{T.type:=array(num.val,T1.TypeT.width:=num.val*T1.Width)TÆ^T1{T.type:=pointer(T1.type)T.width:=4}盛威网（www.snwei.com）专业的计算机学习网站21 《编译原理》课后习题答案第八章问题13：（浙江大学1997年）在一个移入－归约的分析中采用以下的语法制导的翻译模式，在按一产生式归约时，立即执行括号中的动作。A→aB{print“0”;}A→c{print“1”;}B→Ab{print“2”}当分析器的输入为aacbb时，打印的字符串是什么？答案：分析器的分析过程如下图所示：由于分析器采用移入－归约的方式进行分析，符号串aacbb的分析过程将如图中所标的归约顺序进行，而在按一产生式归约时，立即执行括号中的动作，所以分析器打印的字符为12020。盛威网（www.snwei.com）专业的计算机学习网站22 《编译原理》课后习题答案第九章第9章符号表第1题：根据你所了解的某个FORTRAN语言的实现版本，该语言的名字作用域有哪几种?答案：FORTRAN中，名字作用域有四种：<1>在BLOCKDATA块中定义的标识符，其作用域是整个程序。<2>在COMMON块中定义的标识符，其作用域是声明了该COMMON块的所有例程（包括函数和过程）。<3>在例程中定义的标识符（包括哑变量），其作用域是声明该标识符的例程。<4>在例程中用SAVE定义的标识符，其作用域是声明该标识符的例程，且在退出该例程时，该标识符的值仍保留（即内部静态量）。第2题：C语言中规定变量标识符的定义可分为extern,externstatic,auto,localstatic和register五种存储类：(1)对五种存储类所定义的每种变量，分别说明其作用域。(2)试给出适合上述存储类变量的内存分配方式。(3)符号表中登录的存储类属性，在编译过程中支持什么样的语义检查。答案：(1)extern定义的变量，其作用域是整个C语言程序。externstatic定义的变量，其作用域是该定义所在的C程序文件。auto定义的变量，其作用域是该定义所在的例程。localstatic定义的变量，其作用域是该定义所在的例程。且在退出该例程时，该变量的值仍保留。register定义的变量，其作用域与auto定义的变量一样。这种变量的值，在寄存器有条件时，可存放在寄存器中，以提高运行效率。(2)对extern变量，设置一个全局的静态公共区进行分配。对externstatic变量，为每个C程序文件，分别设置一个局部静态公共区进行分配。对auto和register变量，设定它们在该例程的动态区中的相对区头的位移量。而例程动态区在运行时再做动态分配。对localstatic变量，为每个具有这类定义的例程，分别设置一个内部静态区进行分配。(3)实施标识符变量重复定义合法性检查，及引用变量的作用域范围的合法性检查。盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第九章第3题：对分程序结构的语言，为其符号表建立重名动态下推链的目的是什么?概述编译过程中重名动态下推链的工作原理。答案：重名动态下推链的目的是，保证在合法重名定义情况下，提供完整确切的符号表项，从而保证引用变量的上下文合法性检查和非法重名定义检查。其工作原理是：当发生合法重名定义时，将上层重名表项下推到链中，而在符号标中原重名表项处登录当前重名定义的符号属性；在退出本层时，将最近一次下推的表项，回推登录到符号表中原重名表项处。第4题：某BASIC语言的变量名字表示为字母开头的字母或数字两个字节的标识符，该语言的符号表拟采用杂凑法组织，请为其设计实现一个有效散列的杂凑算法，并为解决散列冲突，设计实现一个再散列算法。答案：可采用下列散列杂凑算法（设表长为N）散列地址=MOD（（<第一字节值>+<第二字节值>），N）。发生冲突时再散列的方法：在该冲突处开始，向下寻找第一个空表项，若找到则该表项地址为再散列地址；若找不到空表项，则循环到表头开始，向下寻找第一个空表项，一直到发生冲突处为止，若找到空表项则该表项地址为再散列地址，否则表示符号表已满，编译系统给出符号表溢出信息，终止编译。盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第九章附加题问题1：利用Pascal的作用域规则，试确定在下面的Pascal程序中的名字a和b的每一次出现所应用的说明。programm(input,output);proceduren(u,v,x,y:integer);varm:recordm,n:intergerend;n:recordn,m:intergerend;beginwithmdobeginm:=u;n:=vend;withndobeginm:=x;n:=yend;writeln(m.m,m.n,n.m,n.n)end;beginm(1,2,3,4)end.答案：图中用蓝色数字下标相应标明。programm1(input,output);proceduren1(u,v,x,y:integer);varm2:recordm3,n2:intergerend;n3:recordn4,m4:intergerend;beginwithm2dobeginm3:=u;n2:=vend;withn3dobeginm4:=x;n4:=yend;writeln(m2.m3,m2.n2,n3.m4,n3.n4)end;beginm1(1,2,3,4)end.问题2：当一个过程作为参数被传递时，我们假定有以下三种与此相联系的环境可以考虑，下面的Pascal程序是用来说明这一问题的。一种是词法环境（lexicalenvironment），如此这样的一个过程的环境是由这一过程定义之处的各标识符的联编所构成；一种是传递环境（passingenvironment），是由这一过程作为参数被传递之处的各标识盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第九章符的联编所构成；另一种是活动环境（activationenvironment），是由这一过程活动之处的各标识符的联编所构成。试考虑在第（11）行上的作为一个参数被传递的函数f。利用对于f的词法环境、传递环境和活动环境，在第（8）行上的非局部量m将分别处在第（6）行、（10）行和（3）行上的m的说明的作用域中。（a）图示出每个过程的活动记录。（b）试为此程序画出活动树。（c）试给出程序的输出。(1)programparam(inout,output);(2)procedureb(functionh(n:integer):integer);(3)varm:integer;(4)beginm:=3;writeln(h(2))end{b};(5)procedurec;(6)varm:integer;(7)functionf(n:integer):integer;(8)beginf:=m+nend{f};(9)procedurer;(10)varm:integer;(11)beginm:=7;b(f)end{r};(12)beginm:=0;rend{c};(13)begin(14)c(15)end.答案：（a）词法环境parama控制链访问链c控制链访问链mr控制链访问链mb控制链访问链mfn=2控制链访问链盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第九章传递环境parama控制链访问链c控制链访问链mr控制链访问链mb控制链访问链mfn=2控制链访问链活动环境param控制链访问链c控制链访问链mr控制链访问链mb控制链访问链mfn=2控制链访问链盛威网（www.snwei.com）专业的计算机学习网站5 《编译原理》课后习题答案第九章（b）活动树paramcrb(f)f(2)（c）词法环境：2；传递环境：9；活动环境：5。问题3：己知程序段：BEGINintegeri;read(i);write("value=",func(i));...ENDintegerprocedurefunc(N)integerN；BEGINIFN==0THENfunc=1;ELSEIFN==1,THENfunc=1；ELSEfunc=N*func(N-1)END;求当输入i=3时，本程序执行期间对运行栈的存储分配图。答案：param控制链访问链func控制链访问链N=3func控制链访问链N=2func控制链访问链N=1盛威网（www.snwei.com）专业的计算机学习网站6 《编译原理》课后习题答案第九章问题4：某语言允许过程嵌套定义和递归调用(如Pascal语言)，若在栈式动态存储分配中采用嵌套层次显示表display解决对非局部变量的引用问题，试给出下列程序执行到语句“b：＝10；”时运行栈及display表的示意图。varx，y；PROCEDUREP；vara;PROCEDUREq；varb：BEGIN{q}b：＝10；END{q};PROCEDUREs;varc，d；PROCEDUREr;vare,f;BEGIN{r}callq；END{r}；BEGIN{s}callr；END{s}；BEGIN{p}calls;END{p}；BEGIN{main}callp；END{main}．盛威网（www.snwei.com）专业的计算机学习网站7 《编译原理》课后习题答案第九章答案：盛威网（www.snwei.com）专业的计算机学习网站8 《编译原理》课后习题答案第九章问题5：试问下面的程序将有怎样的输出？分别假定：（a）传值调用（call-by-value）；（b）引用调用（call-by-reference）；（c）复制恢复（copy-restore）；（d）传名调用（call-by-name）。programmain(input,output);procedurep(x,y,z);beginy:=y+1;z:=z+x;end;begina:=2;b:=3;p(a+b,a,a);printaend.答案：1)．传地址：所谓传地址是指把实在参数的地址传递给相应的形式参数。在过程段中每个形式参数都有一对应的单元，称为形式单元。形式单元将用来存放相应的实在参数的地址。当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可以拿得到的地方。当程序控制转入被调用段之后，被调用段首先把实参地址捎进自己相应的形式单元中，过程体对形式参数的任何引用1或赋值都被处理成对形式单元的间接访问。当调用段工作完毕返回时，形式单元(它们都是指示器)所指的实在参数单元就持有所指望的值。2)．传结果：和“传地址”相似(但不等价)的另一种参数传递力法是所谓“传结果”。这种方法的实质是，每个形式参数对应有两个申元，第1个单元存放实参的地址，第2个单元存放实参的值。在过程体中对形参的任何引用或赋值都看成是对它的第2个单元的直接访问。但在过程工作完毕返回前必须把第2个单元的内容行放到第1个单元所指的那个实参单元之中。3)．传值：所谓传值，是一种简单的参数传递方法。调用段把实在参数的值计算出来并存放在一个被调用段可以拿得到的地方。被调用段开始丁作时，首先把这些值抄入形式中元中，然后就好像使用局部名一样使用这些形式单元。如果实在参数不为指示器，那末，在被调用段中无法改变实参的值。4)．传名：所谓传名，是一种特殊的形——实参数结合方式。解释“传名”参数的意义：过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实在参数(文字替换)。它与采用“传地址”或“传值”的方式所产生的结果均不相同。(a)2；(b)8；(c)7；(d)9。盛威网（www.snwei.com）专业的计算机学习网站9 《编译原理》课后习题答案第九章问题6：下面程序的结果是120，但是如果把第11行的abs(1)改成1的话，则程序结果是1,分析为什么会有这样不同的结果。intfact(){staticinti=5;if(i==0){return(i);}else{i=i-1;return((i+abs(1))*fact());/*第11行*/}}main(){printf("factorof5=%dn",fact());}答案：(1)i是静态变量，所有地方对i的操作都是对同一地址空间的操作，所以每次递归进入fact函数后，上一层对i的赋值仍然有效。值得注意的是，每次递归时，(i+abs(1)*fact()中(i+abs(1))的值都先于fact算出。所以，第1次递归时，所求值为5*fact,第2次递归时，所求值为4*fact，第3次递归时，所求值为3*fact，如此类推，第5次递归时所求值为1*fact,而此时fact值为1。这样一来，实质上是求一个阶乘函数5*4*3*2*1，所以结果为120。(2)之所以改动abs(1)为1后会产生变化，这主要和编译时的代码生成策略有关。对于表达式(i+abs(1))*fact()，因两个子表达式都有函数调用，因此编译器先产生左子表达式代码，后产生右子表达式代码。当abs(1)改成1后，那么左子表达式就没有函数调用了，于是编译器会先产生右子表达式代码，这样一来，每次递归时，(i+abs(1))*fact()如c4)中(i+abs(1))的值都后于fact算出。第1次递归时，所求值为(i+1)*fact，第2次递归时，所求值为(i+1)*fact，第3次递归时，所求值为(i+1)*fact，如此类推，第5次递归时所求值为(i+1)*fact，而此时fact为1，i为0。这样每次递归时所求的实际都是1*fact，最后输出还是1。因此有不问的结果。盛威网（www.snwei.com）专业的计算机学习网站10 《编译原理》课后习题答案第九章问题7：下面是一个c语言程序及其运行结果。从运行结果看，函数FUNC中4个局部变量i1,j1，f1，e1的地址间隔和它们类型的大小是一致的。而4个形式参数i，j，f，e的地址间隔和它们类型的大小不一致，试分析不一致的原因。#include＜stdio.h>FUNC(i,j,f,e)shorti,j;floatf,e；{shorti1,j1;floatf1,e1;i1=i;j1=j;f1=f;e1=e;printf("Addrssesofi,j,f,e＝%ld%ld%ld%ldn",&i,&j,&f,&e);printf("Addrssesofi1,j1,f1,e1＝%ld%ld%ld%ldn",&i1,&j1,&f1,&e1);printf("sizeofshort,int,long,float,double＝%ld%ld%ld%ldn",sizeof(short),sizeof(int),sizeof(long),sizeof(float),sizeof(double));}main(){shorti,j;floatf,e;i=j=1;f=e=1.0;FUNC(i,j,f,e);}运行结果为：Addrssesofi,j,f,e＝-268438178,-268438174,-268438172,-2684364Addrssesofi1,j1,f1,e1＝-268438250,-268438252,-268438256,-268438260sizeofshort,int,long,float,double＝2,4,4,4,8答案：C编译是不作调用时形参和实参一致性检查的。注意在C语言中，整数有short，int和long共3种类型，实数有float和double两种类型。C语言的参数调用是按传值方式进行的，一个整型表达式的值究竟是按short，int还是long方式传递呢?显然，这儿约定为应该按取参数的最大方式来读取参数，即对于整数用long方式，实数用double方式。虽然参数传递是按最大方式进行，但是被调用函数中形式参数是按自己类型定义来取值的。这样一来，参数传递和取值是不—致的，就要考虑边界对齐问题。因float类型需要4字节，而double类型为8字节，故当从double类型变量取float类型的值时，应从第l~4个字节分配float类型数。short型的形参是取long型值4字节中的后两字节内容，float型的形参是取double值8字节的前4字节。这样才出现这4个形参地址的结果。盛威网（www.snwei.com）专业的计算机学习网站11 《编译原理》课后习题答案第十章第10章目标程序运行时的存储组织第5题：过程参数的传递方式有几种?简述“传地址”和“传值”的实现原理。答案：参数的传递方式有下述几种：“传值”--CallbyValue。“传地址”--CallbyAddress。“换名”--CallbyName。“得结果”--Value-result。“传值”方式，这是最简单的参数传递方法。即将实参计算出它的值，然后把它传给被调过程。具体来讲是这样的：1.形式参数当作过程的局部变量处理，即在被调过程的活动记录中开辟了形参的存储空间，这些存储位置即是我们所说的实参或形式单元。2.调用过程计算实参的值，并将它们的右值（r-value）放在为形式单元开辟的空间中。3.被调用过程执行时，就像使用局部变量一样使用这些形式单元。“传地址”方式，也称作传地址，或引用调用。调用过程传给被调过程的是指针，指向实参存储位置的指针。1.如实参是一个名字或是具有左值的表达式，则左值本身传递过去。2.如实参是一个表达式，比方a+b或2，而没有左值，则表达式先求值，并存入某一位置，然后该位置的地址传递过去。3.被调过程中对形式参数的任何引用和赋值都通过传递到被调过程的指针被处理成间接访问。盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第十章第6题：下面的程序执行时输出的a分别是什么?若(1)参数的传递办法为“传值”。(2)参数的传递办法为“传地址”。programmain(input,output);procedurep(x,y,z);beginy∶=y+1;z=∶z+x;end;begina=∶2;b∶=3;p(a+b,a,a);printaend.答案：(1)参数的传递办法为"传值"时，a为2。(2)参数的传递办法为"传地址"，a为7。盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第十章附加题问题1：下面是一个Pascal程序programPP(input,output)varK:integer;functionF(N:integer):integerbeginifN<=0thenF:=1elseF:=N*F(N-1);end;beginK:=F(10);...end;当第二次（递归地）进入F后，DISPLAY的内容是什么？当时整个运行栈的内容是什么？答案：盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第十章问题2：对如下的Pascal程序，画出程序执行到（1）和（2）点时的运行栈。programTr(input,output);vari:integer;d:integer;procedureA(k:real);varp:char;procedureB;varc:char;begin...(1)...end;{B}procedureC;vart:real;begin...(2)...end;{C}begin.....B;C;.....end;{A}begin{main}...A(d);...end.答案：程序执行到（1）点时的流程是：①主程序激活A②A激活B程序执行到（2）点时的流程是：①主程序激活A②A激活B盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第十章③B执行结束返回A④A激活C问题3：有如下示意的Pascal源程序programmain;vara,b,c:integer;procedureX(i,j:integer);vard,e:real;procedureY;varf,g:real;begin...end;{Y}procedureZ(k:integer);varh,i,j:real;begin...end;{Z}begin.....10:Y;.....11:Z;.....end;{X}begin.....X(a,b);.....end.{main}并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。当运行主程序而调用过程语句X时，试分别给出以下时刻的运行栈的内容和DISPLAY的内容。（1）已开始而尚未执行完毕的标号为10的语句。（2）已开始而尚未执行完毕的标号为11的语句。盛威网（www.snwei.com）专业的计算机学习网站5 《编译原理》课后习题答案第十章答案：程序结构：（1）（2）盛威网（www.snwei.com）专业的计算机学习网站6 《编译原理》课后习题答案第十一章第11章代码优化第１题何谓代码优化？进行优化所需要的基础是什么？答案：对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少，或两者都有。优化所需要的基础是在中间代码生成之后或目标代码生成之后。第２题编译过程中可进行的优化如何分类？答案：依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。第３题最常用的代码优化技术有哪些？答案：1.删除多余运算2.代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第十一章第4题图11.23是图11.22的C代码的部分三地址代码序列。voidquicksort(m,n)intm,n;{inti,j;intv,x;if(n<=m)return;/*fragmentbeginshere*/i=m-1;j=n;v=a[n];while(1){doi=i+1;while(a[i]v);if(i>=j)break;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x;/*fragmentendshere*/quicksort(m,j);quicksort(i+1,n);}图11.22(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=a[t1](5)i:=i+1(6)t2:=4*i(7)t3:=a[t2](8)ift3vgoto(9)(13)ifi>=jgoto(23)盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第十一章(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t6:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=x图11.23(1)请将图11.23的三地址代码序列划分为基本块并做出其流图。(2)将每个基本块的公共子表达式删除。(3)找出流图中的循环,将循环不变量计算移出循环外。(4)找出每个循环中的归纳变量，并在可能的地方删除它们。答案：（1）基本块盛威网（www.snwei.com）专业的计算机学习网站3 《编译原理》课后习题答案第十一章流图（2）B5中（14）和（16）是公共子表达式、（17）和（20）是公共子表达式，B5变为（14）t6:=4*I（15）（16）t7:=t6（17）t8:=4*J…（20）t10:=t8（21）（22）B6中（23）和（25）是公共子表达式、（26）和（29）是公共子表达式，B6变为（23）t11:=4*I（24）（25）t12:=t11（26）t13:=4*n盛威网（www.snwei.com）专业的计算机学习网站4 《编译原理》课后习题答案第十一章…（29）t15:=t13（3）循环①{B2}②{B3}③{B2，B3，B4，B5}(4)在循环{B2，B3，B4，B5}中，原来的(14)(17)都可以删除。盛威网（www.snwei.com）专业的计算机学习网站5 《编译原理》课后习题答案第十一章第5题：如下程序流图(图11.24)中，B3中的i=∶2是循环不变量，可以将其提到前置结点吗?你还能举出一些例子说明循环不变量外移的条件吗?图11.24答案：不能。因为B3不是循环出口B4的必经结点。循环不变量外移的条件外有：（a）(I)s所在的结点是L的所有出口结点的必经结点(II)A在L中其他地方未再定值(III)L中所有A的引用点只有s中A的定值才能到达（b）A在离开L之后不再是活跃的，并且条件(a)的(II)和(III)成立。所谓A在离开L后不再是活跃的是指，A在L的任何出口结点的后继结点的入口处不是活跃的（从此点后不被引用）（3）按步骤（1）所找出的不变运算的顺序，依次把符合（2）的条件(a)或(b)的不变运算s外提到L的前置结点中。如果s的运算对象（B或C）是在L中定值的，则只有当这些定值四元式都已外提到前置结点中时，才可把s也外提到前置结点。盛威网（www.snwei.com）专业的计算机学习网站6 《编译原理》课后习题答案第十一章第6题试对以下基本块B1和B2：B1：A：=B*CD：=B/CE：=A+DF：=2*EG：=B*CH：=G*GF：=H*GL：=FM：=LB2：B：=3D：=A+CE：=A*CF：=D+EG：=B*FH：=A+CI：=A*CJ：=H+IK：=B*5L：=K+JM：=L分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：（1）假设只有G、L、M在基本块后面还要被引用。（2）假设只有L在基本块后面还要被引用。答案:B1：基本块对应的DAG如下：盛威网（www.snwei.com）专业的计算机学习网站7 《编译原理》课后习题答案第十一章根据DAG图,优化后的语句序列为A：=B*CG：=AD：=B/CE：=A+DH：=A*AF：=A*HL：=FM：=F（1）假设只有G、L、M在基本块后面还要被引用；S1：=B*CG：=S1S2：=S1*S1S3：=S1*S2L：=S3M：=S3（2）假设只有L在基本块后面还要被引用；S1：=B*CS2：=S1*S1S3：=S1*S2L：=S3（备注：S1，S2，S3为新引入的临时变量）或者：盛威网（www.snwei.com）专业的计算机学习网站8 《编译原理》课后习题答案第十一章B2:基本块对应的DAG如下：优化后的四元式序列：对假设（１）B:=3盛威网（www.snwei.com）专业的计算机学习网站9 《编译原理》课后习题答案第十一章D:=A+CE:=A*CF:=D+EG:=B*FK:=B*5L:=K+FM:=L对假设（2）B:=3D:=A+CE:=A*CF:=D+EK:=B*5L:=K+F盛威网（www.snwei.com）专业的计算机学习网站10 《编译原理》课后习题答案第十一章第7题分别对图11.25和11.26的流图：(1)求出流图中各结点n的必经结点集D(n)。(2)求出流图中的回边。(3)求出流图中的循环。图11.25图11.26盛威网（www.snwei.com）专业的计算机学习网站11 《编译原理》课后习题答案第十一章答案：对图11.25：（1）流图中各结点N的必经结点集D(n)：D(1)={1}D(2)={1,2}D(3)={1,2,3}D(4)={1,2,3,4}D(5)={1,2,3,5}D(6)={1,2,3,6}D(7)={1,2,7}D(8)={1,2,7,8}（2）回边：7→2（3）循环：{2，3，4，5，6，7}对图11.26：(1)流图中各结点N的必经结点集D(n)：D(l)＝{1}D(2)＝{1,2}D(3)＝{1,2,3}D(4)={1,2,3,4}D(5)＝{1,2,5}D(6)＝{1,2,5,6}(2)求出流图中的回边：5→2，4→3(3)求出流图中的循环：回边5→2对应的循环：｛2，5，3，4｝回边4→3对应的循环：｛3，4｝盛威网（www.snwei.com）专业的计算机学习网站12 《编译原理》课后习题答案第十一章附加题问题1：给出如下4元式序列：(1)J:=0;(2)L1:I:=0;(3)IFI<8,gotoL3;(4)L2:A:=B+C;(5)B:=D*C;(6)L3:IFB=0,gotoL4;(7)WriteB;(8)gotoL5;(9)L4:I:=I+1;(10)IFI<8,gotoL2;(11)L5:J:=J+1;(12)IFJ<=3,gotoL1;(13)STOP①画出上述4元式序列的程序流程图G,②求出G中各结点N的必经结点集D(n),③求出G中的回边与循环。答案：①四元式程序基本块入口语句的条件是：(1)它们是程序的第一个语句；或，(2)能由条件转移语句或无条件转移语句转移到的语句；或，(3)紧跟在条件转移语句后的语句。(4)根据这3个条件，可以判断，设1，2，3，4，6，7，9，11，13为入口语句，故基本块为l，2/3，4/5，6，7/8，9/1O，11/12，13，故可画出程序流图如下图所示：盛威网（www.snwei.com）专业的计算机学习网站13 《编译原理》课后习题答案第十一章②D(l)＝{1}，D(2)＝{1，2}，D(3)＝{1，2，3}，D(4)={1，2，4}，D(5)＝{1，2，4，5}，D(6)＝{1，2，4，6}，D(7)＝{1，2，4，7}，D(8)＝{1，2，4，7，8}，即为所求必经结点集。③回边的定义为：假设a→b为流图中一条有向边，若bDOMa，则a→b为流图中一条回边。故当已知必经结点集时，可立即求出所有回边。易知本题回边只有7→2。(按递增顺序考察所有回边。）称满足如下两个条件的结点序列为一个循环。(1)它们强连通，即任意两个结点，必有一通路，且该通路上各结点都属于该结点序列，如序列只包含一个结点，则必有一有向边从该结点引到自身。(2)它们中间有一个而且只有一个是入口结点。所谓入口结点，是指序列中具有下列性质的结点，从序列外某结点有一有向边引到它，或它就是程序流图的首结点。求出回边7→2，可知循环为234567，即为所求。盛威网（www.snwei.com）专业的计算机学习网站14 《编译原理》课后习题答案第十一章问题2：基本块的DAG如下图所示，若(1)B在该基本块出口处不活跃,(2)B在该基本块出口处活跃的，请分别给出以下代码经过优化后的代码。A:＝B+CB:＝A-DC:＝B+CD:＝A-D答案：①当B在出口不活跃时，则B在外面就无用了，故B：=A-D这条赋值语句可删去，另外，由于代码生成方面的关系，可把D的赋值语句提前到C的赋值语句以前。故得到：A:=B+CD:=A-DC:=D+C②当B在出口活跃时，则B在出口处要引用，B的赋值语句就不可删去了，然而D与B充全一样，故D的赋值语句可简化，得：A:＝B+CB:＝A-DD:=BC:=B+C盛威网（www.snwei.com）专业的计算机学习网站15 《编译原理》课后习题答案第十二章第12章代码生成第1题一个编译程序的代码生成要着重考虑哪些问题?答案：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第十二章附加题问题1：决定目标代码的因素有哪些？答案：决定目标代码的因素主要取决于具体的机器结构、指令格式、字长及寄存器的个数和种类，并与指令的语义和所用操作系统、存储管理等都密切相关。又由于目标代码的执行效率在很大程度上依赖于寄存器的使用，所以目标代码与寄存器的分配算法也有关。问题2：为什么在代码生成时要考虑充分利用寄存器？答案：因为当变量值存在寄存器时，引用的变量值可直接从寄存器中取，减少对内存的存取次数，这样便可提高运行速度。因此如何充分利用寄存器是提高目标代码运行效率的重要途径。问题3：寄存器分配的原则是什么？答案：寄存器分配的原则是：(1)当生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中，直到寄存器不够分配时为止。(2)当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结点或多个前驱结点，同一个变量名在不同前驱结点的基本块内出口前存放的R可能不同，或没有定值，所以应在出口前把寄存器的内容放在内存中，这样从基本块外入口的变量值都在内存中。(3)对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用效率。对基本块的划分可按基本块的划分算法(见11.2.1)在生成四元式的目标代码时进行，以区分基本块的入口和出口。盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第十三章第13章编译程序的构造第1题构造一个编译程序有哪些途径？答案：编译程序的实现途径可有：（１）手工构造：用机器语言、汇编语言或高级程序设计语言书写。（２）自动构造工具：Lex,Yacc。Lex,Yacc分别是词法和语法分析器的生成器。（３）移植方式：目标程序用中间语言。（４）自展方式：用T型图表示。盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第十三章附加题问题1:如何用T型图表示一个编译程序的实现？答案：用T型图表示编译程序的实现问题2：如何用自展方式在PC机上实现C语言的编译程序？请用T型图表示。答案：用自展方式在PC机上实现C语言的编译程序，首先把C划分成真包含的子集C1和C2，然后分3步实现。盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第十三章问题3：什么叫做软件移植？答案：通常把某个机器(称为宿主机)上已有的软件移植到另一台机器(称为目标机)问题4：什么叫做交叉编译？答案：交叉编译是指把一个源语言在宿主机上经过编译产生目标机的汇编语言或机器语言。问题5：编译程序的实现应考虑的问题有那些？答案：编译程序的实现应考虑：开发周期、目标程序的效率、可移植性、可调试性、可维护性、可扩充性等。盛威网（www.snwei.com）专业的计算机学习网站3'