《编译原理》(清华大学出版社第二版)课后习题答案.doc

资源描述

1、第一章第 1 章引论第 1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。（2）源程序：源语言编写的程序称为源程序。（3）目标程序：目标语言书写的程序称为目标程序。（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号

2、表管理等工作。（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。第 2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的

3、机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以

4、说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。第 3 题何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？答案：翻译程序是指将用某种语言编写的程序转换成另一种语言

5、形式的程序的程序，如编译程序和汇编程序等。编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功能的实现，完成后返回到解释程序的总控部分再读人下一条语句继续进行解释、执行，如此反复；另一种方式是，一边翻译一边执行，即每读出源程序的一条语句，解释程序就将其翻译成一段机器指令并执行之，然后再读人下一条语句继续进行解释

6、、执行，如此反复。无论是哪种方式，其加工结果都是源程序的执行结果。目前很多解释程序采取上述两种方式的综合实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行中间代码程序，最后得到运行结果。广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是边翻译（解释）边执行，不产生目标代码，输出源程序的运行结果。而编译程序只负责把源程序翻译成目标程序，输出与源程序等价的目标程序，而目标程序的执行任务由操作系统来完成，即只翻译不执行。第 4 题对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。（1） else

7、没有匹配的 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

8、编写 L2 的编译程序 T2，如此逐步扩展下去，好似滚雪球一样，直到我们所要求的编译程序。（4）移植：将 A 机器上的某高级语言的编译程序搬到 B 机器上运行。第题计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么? 答案：计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。像Basic之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反复。总而言之，是边翻译边执行。像C，Pascal

9、之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上看，编译型的高级语言比解释型的高级语言更快。 3编译原理课后习题答案第二章第 2 章 PL/0 编译程序的实现第 1 题 PL/0 语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。答案： PL/0 语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。（数组 CODE 存放的只读目标程序，它在运行时不改变。）运行时的数据区 S 是由解释程序定义的一维整型数组，解释执行时对数据空间 S 的管理遵循后进先出

10、规则，当每个过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题。第 2 题若 PL/0 编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题，试写出下列程序执行到赋值语句 b=10 时运行栈的布局示意图。 var x,y; procedure p; var a; procedure q; var b; begin (q) b=10; end (q); procedure s; var c,d; procedure r; var e,f; be

11、gin (r) call q; end (r); begin (s) call r; end (s); begin (p) call s; end (p); begin (main) call p; end (main). 答案：程序执行到赋值语句 b=10 时运行栈的布局示意图为：第 3 题写出题 2 中当程序编译到 r 的过程体时的名字表 table 的内容。 name kind level/val adr size 答案：题 2 中当程序编译到 r 的过程体时的名字表 table 的内容为： name kind level/val adr sizex variable 0 dx

12、y variable 0 dx+1 p procedure 0 过程 p 的入口（待填） 5 a variable 1 dx q procedure 1 过程 q 的入口 4 s procedure 1 过程 s 的入口（待填） 5 c variable 2 dx d variable 2 dx r procedure 2 过程 r 的入口 5 e variable 3 dx f variable 3 dx+1 注意：q 和 s 是并列的过程，所以 q 定义的变量 b 被覆盖。第 4 题指出栈顶指针 T，最新活动记录基地址指针 B，动态链指针 DL，静态链指针 SL 与返回地址 RA 的用

13、途。答案：栈顶指针 T，最新活动记录基地址指针 B，动态链指针 DL，静态链指针 SL 与返回地址RA 的用途说明如下： T：栈顶寄存器 T 指出了当前栈中最新分配的单元(T 也是数组 S 的下标)。 B：基址寄存器，指向每个过程被调用时，在数据区 S 中给它分配的数据段起始地址，也称基地址。 SL：静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，用以引用非局部（包围它的过程）变量时，寻找该变量的地址。 DL：动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。 RA：返回地址，记录调用该过程

14、时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。在每个过程被调用时在栈顶分配 3 个联系单元，用以存放 SL，DL， RA。第 5 题 PL/0 编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。（） INT 0 A （） OPR 0 0 （） CAL L A 答案： PL/0 编译程序所产生的目标代码中有 3 条非常重要的特殊指令，这 3 条指令在 code 中的位置和功能以及所完成的操作说明如下： INT 0 A 在过程目标程序的入口处，开辟 A 个单元的数据段。A 为

15、局部变量的个数+3。 OPR 0 0 在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器 B 和栈顶寄存器 T 的值，并将返回地址送到指令地址寄存器 P 中，以使调用前的程序从断点开始继续执行。 CAL L A 调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器 B 中，目标程序的入口地址 A 的值送指令地址寄存器 P 中，使指令从 A 开始执行。第 6 题给出对 PL/0 语言作如下功能扩充时的语法图和 EBNF 的语法描述。 (1) 扩充条件语句的功能使其为： if条件then语句else语句 (2) 扩充 r

16、epeat 语句为： repeat语句；语句until条件答案：对 PL/0 语言作如下功能扩充时的语法图和 EBNF 的语法描述如下： (1) 扩充条件语句的语法图为： EBNF 的语法描述为：条件语句:= if条件then语句else语句 (2) 扩充 repeat 语句的语法图为： EBNF 的语法描述为：重复语句:= repeat语句；语句until条件 3编译原理课后习题答案第三章第 3 章文法和语言第 1 题文法 G(A,B,S,a,b,c,P,S)其中 P 为： SAc|aB Aab Bbc 写出 L(GS)的全部元素。答案： L(GS)=abc 第 2 题文

17、法 GN为： ND|ND D0|1|2|3|4|5|6|7|8|9 GN的语言是什么？答案: GN的语言是 V+。V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD. =NDDDD.D=D.D 或者：允许 0 开头的非负整数？第题为只包含数字、加号和减号的表达式，例如 9-25，3-1，等构造一个文法。答案： GS: S-S+D|S-D|D D-0|1|2|3|4|5|6|7|8|9 第 4 题已知文法 GZ： ZaZb|ab 写出 L(GZ)的全部元素。答案： Z=aZb=aaZbb=aaa.Z.bbb= aaa.ab.bbb n nL(GZ)=a b |n=1 第 5

18、题写一文法，使其语言是偶正整数的集合。要求： (1) 允许 0 打头； (2)不允许 0 打头。答案： (1)允许 0 开头的偶正整数集合的文法 ENT|D TNT|D ND|1|3|5|7|9 D0|2|4|6|8 (2)不允许 0 开头的偶正整数集合的文法 ENT|D TFT|G ND|1|3|5|7|9 D2|4|6|8 FN|0 GD|0 第 6 题已知文法 G： := :=* :=（）i 试给出下述表达式的推导及语法树。（） i+(i+i) （） i+i*i 答案： + + i i i （ ) (5) = = =（） =（） =（） =（i） =（i） =（i） =（ii

19、） =（ii） =（ii） =i（ii） + * i i i (6) = =* =*i =*i =i*i =i*i =i*i =ii*i 第 7 题证明下述文法 G表达式是二义的。表达式=a|(表达式)|表达式运算符表达式运算符=+|-|*|/ 答案：可为句子 a+a*a 构造两个不同的最右推导: 最右推导 1 表达式表达式运算符表达式表达式运算符a 表达式* a 表达式运算符表达式* a 表达式运算符a * a 表达式+ a * a a + a * a 最右推导 2 表达式表达式运算符表达式表达式运算符表达式运算符表达式表达式运算符表达式运算符 a 表达式运算符表达式 * a 表

20、达式运算符a * a 表达式+ a * a a + a * a 第 8 题文法 GS为： SAc|aB Aab Bbc 该文法是否为二义的？为什么？答案：对于串 abc (1)S=Ac=abc (2)S=aB=abc 即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串 abc，能构造两棵不同的语法树，所以它是二义的。 S a B b c S A c a b 第 9 题考虑下面上下文无关文法： SSS*|SS+|a S S S * a S S + a a (1)表明通过此文法如何生成串 aa+a*，并为该串构造语法树。 (2)GS的语言是什么？答案： (1)此文法生成

22、+T*F，所以 E+T*F 句型此句型相对于 E 的短语有:E+T*F；相对于 T 的短语有 T*F 直接短语为：T*F 句柄为：T*F 第 13 题一个上下文无关文法生成句子 abbaa 的推导树如下： (1)给出串 abbaa 最左推导、最右推导。 (2)该文法的产生式集合 P 可能有哪些元素？ B S A B S a S B A b b a (3)找出该句子的所有短语、直接短语、句柄。 a 答案： (1)串 abbaa 最左推导: S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa 最右推导： S=ABS=ABAa=ABaa=ASBBaa=ASBba

25、子。（）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。附加题问题 1：给出下述文法所对应的正规式： S0A|1B A1S|1 B0S|0 答案： R = (01 | 10) ( 01 | 10 )* 问题 2：已知文法 GA，写出它定义的语言描述 GA: A 0B|1C B 1|1A|0BB C 0|0A|1CC 答案

26、: GA定义的语言由 0、1 符号串组成，串中 0 和 1 的个数相同. 问题 3：给出语言描述，构造文法. 构造一文法,其定义的语言是由算符+, *, (,)和运算对象 a 构成的算术表达式的集合. 答案一： GE EE+T|T TT* F|F F(E)|a 答案二： GE EE+E|E* E|(E)|a 问题 4：已知文法 GS: SdAB AaA|a B|bB 相应的正规式是什么？GS能否改写成为等价的正规文法？答案：正规式是 daa*b*；相应的正规文法为(由自动机化简来)： GS:SdA Aa|aB BaB|a|b|bC CbC|b 也可为(观察得来):GS:SdA Aa|

27、aA|aB BbB| 问题 5：已知文法 G： EE+T|E-T|T TT*F|T/F|F F(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) E

28、E + T E + T i T F F (E ) i T F i F (4)E + T T T * F F i i E + T i T F i F i E E T F F i (1) i (2) (3) 问题 6：已知文法 GE: EET+|T TTF* | F FF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄. 答案：该句型对应的语法树如下：该句型相对于 E 的短语有 FF* 相对于 T 的短语有 FF*,F 相对于 F 的短语有 F;F 简单短语有 F;F 句柄为 F. 问题 7：适当变换文法，找到下列文法所定义语言的一个无二义的文法： S SaS SbS

29、ScS d 答案：该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做进一步变换，即可消除二义性。设 a、b 和 c 的优先级别依次增高，根据优先级联规则将文法变换为： S SaS A A AbA C C CcC d 规定结合性为左结合，进一步将文法变换为： S SaA A A AbC C C CcF F F d 该文法为非二义的。问题 8：构造产生如下语言的上下文无关文法：（1） anb2ncm | n，m 0 （2） anbmc2m | n，m 0 （3） ambn m n （4） a m b n c p d q m+n = p+q （5） uawb u,w

30、 a, b* | u | = | w | 答案：（1）根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如 anb2n 和形如 cm 的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是特别指明，通常可以忽略这一点。对于该语言，存在一个由以下产生式定义的上下文无关文法 GS： S AB A aAbb B cB （2）同样，要产生形如anbmc2m的串，可以分别产生形如 an 和形如 bmc2m 的串。对于该语言，存在一个由以下产生式定义的上下文无关文法GS： S AB A aA B bBcc （3）考虑在先产生同样数目的 a,b，然后再生成多余

31、的 a。以下 GS是一种解法： S aSb aS （4）以下 GS是一种解法： S aSd A D A bAd B D aDc B B bBc 注：a 不多于 d 时，b 不少于 c；反之，a 不少于 d 时，b 不多于 c。前一种情形通过对应 A，后一种情形对应 D。（5）以下 GS是一种解法： S Ab A BAB a B a b 问题 9：下面的文法 G(S)描述由命题变量 p、q ，联结词（合取）、（析取）、（否定）构成的命题公式集合： S S T T T T F F F F p q 试指出句型 F q p 的直接短语（全部）以及句柄。答案：直接短语：p，q，F 句柄：F

32、问题 10：设字母表 A=a，符号串 x=aaa，写出下列符号串及其长度：x0,xx,x5 以及 A+. 答案： x0=(aaa)0= | x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1 A2 . A n =a,aa,aaa,aaaa,aaaaa A* = A0 A1 A2 . A n =,a,aa,aaa,aaaa,aaaaa 问题 11：令=a，b，c，又令 x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3 答案： xy=abcb |xy|=4 xyz=abcbaab |xyz|=

33、7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 问题 12：已知文法 GZ：Z=U0V1 、 U=Z11 、 V=Z00 ,请写出全部由此文法描述的只含有四个符号的句子。答案： Z=U0=Z10=U010=1010 Z=U0=Z10=V110=0110 Z=V1=Z00=U000=1000 Z=V1=Z00=V100=0100 问题 13：已知文法 GS： S=AB A=aA B=bBcbc , 写出该文法描述的语言。答案： A=aA描述的语言: an|n=0 B=bBcbc描述的语言:,bncn|n=1 L(GS)=anbmcm|n=0,m=1

34、问题 14：已知文法E=TE+TE-T 、 T=FT*FT/F 、 F=(E)i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。答案：开始符号：E VT=+, - , * , / ,（ , ）, i VN=E , F , T 问题 15：设有文法 GS：S=S*S|S+S|(S)|a，该文法是二义性文法吗？答案：根据所给文法推导出句子 a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。 S S S * S + S a a a S S S +S * S a a a 问题 16：写一文法，使其语言是奇正整数集合。答案： A:=1|3|5|7|9|NA N:=

35、N0|N1|N2|N3|N4|N5|N6|N7|N8|N9| N:=0|1|2|3|4|5|6|7|8|9 盛威网（）专业的计算机学习网站 15编译原理课后习题答案第四章第 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 确定化 . 0 1 X . A A A AB AB AC AB AC A ABY ABY AC AB 除 X，A 外，重新命名其他状态，令 AB 为 B、AC 为 C、ABY 为 D，因为 D 含有 Y（NFA 的终态），所以 D 为终态。 . 0 1 X . A A A B B C B C A D D C B DFA 的状态图：: (2)先构造NFA： XA1B1C0D1E0F1G0H1I0J1KL0Y用子集法将NFA确定化 0 1 X X T0=X A A ABFL T1= ABFL Y CG Y Y CG CGJ T2= Y

展开阅读全文