《编译原理》课后习题答案.pdf

《《编译原理》课后习题答案.pdf》由会员分享，可在线阅读，更多相关《《编译原理》课后习题答案.pdf（167页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。1编译原理课后习题答案第一章 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。表格管理程序：负

4、责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。注意：如果问编译程序有哪些主要构成成分，只要回答六部

5、分就可以。如果搞不清楚，就回答八部分。第第 3 题题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？答案：答案：翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这

6、条语句的功能的实现，完成后返回到解释程序的总控部分再读人下一条语句继续进行解释、执行，如此反复；另一种方式是，一边翻译一边执行，即每读出源程序的一条语句，解释程序就将其翻译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如此反复。无论2编译原理课后习题答案第一章 是哪种方式，其加工结果都是源程序的执行结果。目前很多解释程序采取上述两种方式的综合实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行中间代码程序，最后得到运行结果。广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是边翻译（解释）边执行，不产生目标代码，输出源程序的运

7、行结果。而编译程序只负责把源程序翻译成目标程序，输出与源程序等价的目标程序，而目标程序的执行任务由操作系统来完成，即只翻译不执行。第第 4 题题 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。（1）else 没有匹配的没有匹配的 if（2）数组下标越界）数组下标越界（3）使用的函数没有定义）使用的函数没有定义（4）在数中出现非数字字符）在数中出现非数字字符 答案：答案：（1）语法分析（2）语义分析（3）语法分析（4）词法分析 第 5 题第 5 题 编译程序大

8、致有哪几种开发技术？编译程序大致有哪几种开发技术？答案：答案：（1）自编译：用某一高级语言书写其本身的编译程序。（2）交叉编译：A 机器上的编译程序能产生 B 机器上的目标代码。（3）自展：首先确定一个非常简单的核心语言 L0，用机器语言或汇编语言书写出它的编译程序 T0，再把语言 L0 扩充到 L1，此时 L0 L1,并用 L0 编写 L1 的编译程序 T1，再把语言 L1 扩充为 L2，有 L1 L2,并用 L1 编写 L2 的编译程序 T2，如此逐步扩展下去，好似滚雪球一样，直到我们所要求的编译程序。（4）移植：将 A 机器上的某高级语言的编译程序搬到 B 机器上运行。3编译原理课后习题

9、答案第一章 第题 第题 计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?答案：答案：计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。像 Basic 之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反复。总而言之，是边翻译边执行。像 C，Pascal 之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘

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

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

12、ocedure q;var b;begin(q)b=10;end(q);procedure s;var c,d;procedure r;var e,f;begin(r)call q;end(r);begin(s)call r;end(s);begin(p)call s;1编译原理课后习题答案第二章 end(p);begin(main)call p;end(main).答案：答案：程序执行到赋值语句 b=10 时运行栈的布局示意图为：第第 3 题题 写出题写出题 2 中当程序编译到中当程序编译到 r 的过程体时的名字表的过程体时的名字表 table 的内容。的内容。name kind level

13、/val adr size 答案：答案：题 2 中当程序编译到 r 的过程体时的名字表 table 的内容为：name kind level/val adr sizex variable 0 dx y variable 0 dx+1 p procedure 0 过程 p 的入口（待填）5 2编译原理课后习题答案第二章 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 d

14、x f variable 3 dx+1 注意：注意：q 和 s 是并列的过程，所以 q 定义的变量 b 被覆盖。第第 4 题题 指出栈顶指针指出栈顶指针 T，最新活动记录基地址指针，最新活动记录基地址指针 B，动态链指针，动态链指针 DL，静态链指针，静态链指针 SL 与返回地址与返回地址 RA 的用途。的用途。答案：答案：栈顶指针 T，最新活动记录基地址指针 B，动态链指针 DL，静态链指针 SL 与返回地址RA 的用途说明如下：T：栈顶寄存器 T 指出了当前栈中最新分配的单元(T 也是数组 S 的下标)。B：基址寄存器，指向每个过程被调用时，在数据区 S 中给它分配的数据段起 始 地址，也

15、称基地址。SL：静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，用以引用非局部（包围它的过程）变量时，寻找该变量的地址。DL：动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。在每个过程被调用时在栈顶分配 3 个联系单元，用以存放 SL，DL，RA。第第 5 题题 PL/0 编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成

16、的操作。编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。（）（）INT 0 A （）（）OPR 0 0 （）（）CAL L A 答案：答案：PL/0 编译程序所产生的目标代码中有 3 条非常重要的特殊指令，这 3 条指令在 code 中的位置和功能以及所完成的操作说明如下：3编译原理课后习题答案第二章 INT 0 A 在过程目标程序的入口处，开辟 A 个单元的数据段。A 为局部变量的个数+3。OPR 0 0 在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器 B 和栈顶寄存器 T 的值，并将返

17、回地址送到指令地址寄存器 P 中，以使调用前的程序从断点开始继续执行。CAL L A 调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器 B 中，目标程序的入口地址 A 的值送指令地址寄存器 P 中，使指令从 A 开始执行。第第 6 题题 给出对给出对 PL/0 语言作如下功能扩充时的语法图和语言作如下功能扩充时的语法图和 EBNF 的语法描述。的语法描述。(1)扩充条件语句的功能使其为：扩充条件语句的功能使其为：if条件条件then语句语句else语句语句(2)扩充扩充 repeat 语句为：语句为：repeat语句语句；语句；语句until条件条件 答案：

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

19、 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)的全部元素。的全部元素。1编译原理课后习题答案第三章 答案：答案：Z=a

20、Zb=aaZbb=aaa.Z.bbb=aaa.ab.bbb L(GZ)=anbn|n=1 第第 5 题题 写一文法，使其语言是偶正整数的集合。写一文法，使其语言是偶正整数的集合。要求：要求：(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 试给出下述表达式的推导及

21、语法树。试给出下述表达式的推导及语法树。（）（）i+(i+i)（）（）i+i*i 2编译原理课后习题答案第三章 答案：答案：+i i i（)(5)=（）=（）=（）=（i）=（i）=（i）=（ii）=（ii）=（ii）=i（ii）+*i i i(6)=*=*i=*i=i*i=i*i=i*i=ii*i 3编译原理课后习题答案第三章 第第 7 题题 证明下述文法证明下述文法 G表达式表达式是二义的。是二义的。表达式表达式=a|(表达式表达式)|表达式 运算符 表达式表达式 运算符 表达式 运算符运算符=+|-|*|/答案：答案：可为句子 a+a*a 构造两个不同的最右推导:最右推导 1 表达式表达

22、式 运算符 表达式 表达式 运算符a 表达式*a 表达式 运算符 表达式*a 表达式 运算符a*a 表达式+a*a a+a*a 最右推导 2 表达式表达式 运算符 表达式 表达式 运算符 表达式 运算符 表达式 表达式 运算符 表达式 运算符 a 表达式 运算符 表达式*a 表达式 运算符a*a 表达式+a*a a+a*a 4编译原理课后习题答案第三章 第第 8 题题 文法文法 GS为：为：SAc|aB Aab Bbc 该文法是否为二义的？为什么？该文法是否为二义的？为什么？答案：答案：对于串 abc(1)S=Ac=abc (2)S=aB=abc 即存在两不同的最右推导。所以，该文法是二义的。

23、或者：对输入字符串 abc，能构造两棵不同的语法树，所以它是二义的。S a B b c S A c a b 第第 9 题题 考虑下面上下文无关文法：考虑下面上下文无关文法：SSS*|SS+|a(1)表明通过此文法如何生成串表明通过此文法如何生成串 aa+a*，并为该串构造语法树。，并为该串构造语法树。S S S*a S S+a a(2)GS的语言是什么？的语言是什么？答案：答案：(1)此文法生成串 aa+a*的最右推导如下 S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a*(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。5编译原理课后习题答案第三章 第第 10 题题 文法

24、文法 SS(S)S|(1)生成的语言是什么？生成的语言是什么？(2)该文法是二义的吗？说明理由。该文法是二义的吗？说明理由。答案：答案：（）嵌套的括号（）是二义的，因为对于（）（）可以构造两棵不同的语法树。第第 11 题题 令文法令文法 GE为：为：ET|E+T|E-T TF|T*F|T/F F(E)|i 证明证明 E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案：答案：此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导序列:E=E+T=E+T*F，所以 E+T*F 句型 此句型相对于 E 的短语有:E+

25、T*F；相对于 T 的短语有 T*F 直接短语为：T*F 句柄为：T*F 第第 13 题题 一个上下文无关文法生成句子一个上下文无关文法生成句子 abbaa 的推导树如下：的推导树如下：(1)给出串给出串 abbaa 最左推导、最右推导。最左推导、最右推导。(2)该文法的产生式集合该文法的产生式集合 P 可能有哪些元素？可能有哪些元素？(3)找出该句子的所有短语、直接短语、句柄。找出该句子的所有短语、直接短语、句柄。B a S A B S a S B A b b a 6编译原理课后习题答案第三章 答案：答案：(1)串 abbaa 最左推导:S=ABS=aBS=aSBBS=aBBS=abBS=a

26、bbS=abbAa=abbaa 最右推导：S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa (2)产生式有：SABS|Aa|Aa BSBB|b 可能元素有：aa ab abbaa aaabbaa (3)该句子的短语有：a 是相对 A 的短语 是相对 S 的短语 b 是相对 B 的短语 bb 是相对 B 的短语 aa 是相对 S 的短语 abbaa 是相对 S 的短语 直接短语有：a b 句柄是：a 第第 14 题题 给出生成下述语言的上下文无关文法：给出生成下述语言的上下文无关文法：（1）anbnambm|n，m=0 （2）1n0m 1m0n|n

27、，m=0 （3）WaWr|W 属于属于0|a*，Wr表示表示 W 的逆的逆 答案：答案：（）SAA AaAb|（）S1S0|A A0A1|（）S0S0|1S1|7编译原理课后习题答案第三章 第第 16 题题 给出生成下述语言的三型文法：给出生成下述语言的三型文法：(1)an|n=0 (2)anbm|n,m=1 (3)anbmck|n,m,k=0 答案：答案：(1)SaS|(2)SaA AaA|B BbB|b(3)AaA|B BbB|C CcC|第第 17 题题 习题和习题习题和习题 11 中的文法等价吗？中的文法等价吗？答案：答案：等价。第第 18 题题 解释下列术语和概念：解释下列术语和概念

28、：（）字母表（）字母表（）串、字和句子（）串、字和句子（）语言、语法和语义（）语言、语法和语义 答案：答案：（）字母表：是一个非空有穷集合。（）串：符号的有穷序列。字：字母表中的元素。句子：如果 Z x,x V*T 则称 x 是文法 G 的一个句子。+8编译原理课后习题答案第三章（）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所 有该语言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。

29、9编译原理课后习题答案第三章 附加题附加题 问题问题 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 答案答案:GA定义的语言由 0、1 符号串组成，串中 0 和 1 的个数相同.问题问题 3：给出语言描述，构造文法给出语言描述，构造文法.构造一文法 构造一文法,其定义的语言是由算符其定义的语言是由算符+,*,(,)和运算对象和运算对象 a 构成的算术表

30、达式的集合构成的算术表达式的集合.答案一：答案一：GE EE+T|T TT*F|F F(E)|a 答案二：答案二：GE EE+E|E*E|(E)|a 问题问题 4：已知文法已知文法 GS:SdAB 10编译原理课后习题答案第三章 AaA|a B|bB 相应的正规式是什么？相应的正规式是什么？GS能否改写成为等价的正规文法？能否改写成为等价的正规文法？答案：答案：正规式是 daa*b*；相应的正规文法为(由自动机化简来)：GS:SdA Aa|aB BaB|a|b|bC CbC|b 也可为(观察得来):GS:SdA Aa|aA|aB BbB|问题问题 5：已知文法已知文法 G：EE+T|E-T|T

31、 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 E E +T T T *F F i i E +T i T F

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

33、文法所定义语言的一个无二义的文法：S SaS SbS 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 该文法为非二义的。12编译原理课后习题答案第三章 问题问题 8：构造产生如下语言的上下文无关文法：构造产生如下语言的上下文无关文法：（1）anb2ncm|n，m 0 （2）anbmc2m|n，m 0（3）

34、ambn m n （4）a m b n c p d q m+n=p+q （5）uawb u,w a,b*|u|=|w|答案：答案：（1）根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如 anb2n 和形如 cm 的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是特别指明，通常可以忽略这一点。对于该语言，存在一个由以下产生式定义的上下文无关文法 GS：S AB A aAbb B cB （2）同样，要产生形如anbmc2m的串，可以分别产生形如 an 和形如 bmc2m 的串。对于该语言，存在一个由以下产生式定义的上下文无关文法GS：S AB A aA

35、 B bBcc （3）考虑在先产生同样数目的 a,b，然后再生成多余的 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 13编译原理课后习题答案第三章 B a b 问题问题 9：下面的文法下面的文法 G(S)描述由命题变量描述由命题变量 p、q，联结词，联结词（合取）、（析取）、（否定）构成的命题公式集合：（合取）、（析取）、（否

36、定）构成的命题公式集合：S S T T T T F F F F p q 试指出句型试指出句型 F q p 的直接短语（全部）以及句柄。的直接短语（全部）以及句柄。答案：答案：直接短语：p，q，F 句柄：F 问题问题 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

37、,aaa,aaaa,aaaaa 问题问题 11：令令=a，b，c，又令，又令 x=abc，y=b，z=aab，写出如下符号串及它们的长度：，写出如下符号串及它们的长度：xy，xyz，（，（xy）3 答案：答案：xy=abcb|xy|=4 xyz=abcbaab|xyz|=7(xy)3=(abcb)3=abcbabcbabcb|(xy)3|=12 问题问题 12：已知文法 已知文法 GZ：Z=U0V1、U=Z11 、V=Z00,请写出全部由此文法描述的只含有四个符号的句子。请写出全部由此文法描述的只含有四个符号的句子。14编译原理课后习题答案第三章 答案：答案：Z=U0=Z10=U010=101

38、0 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 问题问题 14：已知文法已知文法E=TE+TE-T、T=FT*FT/F、F=(E)i，写出该文法的开始符号、终结符号集合，写出该文法的开始符号、终结符号集合VT、非终结符号集合、非终结符号集合VN。答案：答案：开始符号：E V

39、T=+,-,*,/,（,）,i VN=E,F,T 问题问题 15：设有文法设有文法 GS：S=S*S|S+S|(S)|a，该文法是二义性文法吗？，该文法是二义性文法吗？答案：根据所给文法推导出句子 a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。15编译原理课后习题答案第三章 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:=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9|N:=0|1|2|3|4|5|6|7|8|9 16编

40、译原理课后习题答案第四章 第第 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

41、C A D D C B DFA 的状态图：:1编译原理课后习题答案第四章(2)先构造 NFA：XA1B1C0D1E0F1G0H1I0J1KL0Y用子集法将 NFA 确定化 0 1 X X T0=X A A ABFL T1=ABFL Y CG Y Y CG CGJ T2=Y T3=CGJ DH K DH DH K ABFKL T4=DH EI EI ABEFIL T5=ABFKL Y CG T6=ABEFIL EJY CG EJY ABEFGJLY T7=ABEFGJLY EHY CGK EHY ABEFHLY CGK ABCFGJKL T8=ABEFHLY EY CGI EY ABEFLY C

42、GI CGJI T9=ABCFGJKL DHY CGK DHY DHY T10=ABEFLY EY CG T11=CGJI DHJ K DHJ DHJ T12=DHY EI T13=DHJ EIK EIK ABEFIKL T14=ABEFIKL EJY CG 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，所以它们都为终态。0 1 0 1 1 2 3 2 3 4 5 4 6 5 2

43、 3 6 7 3 7 8 9 8 10 11 9 12 9 10 10 3 11 13 5 12 6 13 14 14 7 3 01012127810345691113141 10 10 10 110 1101 01100 1 01 3编译原理课后习题答案第四章(3)先构造 NFA：先构造 NFA：XAaBa,bDaEaFCYbb 用子集法将 NFA 确定化 a b X X T0=X A A ABCD T1=ABCD BE BY BE ABCDE BY ABCDY T2=ABCDE BEF BEY BEF ABCDEF BEY ABCDEY T3=ABCDY BE BY T4=ABCDEF B

44、EF BEY T5=ABCDEY BEF BEY 将T0、T1、T2、T3、T4、T5重新命名，分别用 0、1、2、3、4、5 表示。因为 3、5 中含有Y，所以它们都为终态。a b 0 1 1 2 3 2 4 5 3 2 3 4 4 5 5 4 5 0ab132a 54ab ababab 4编译原理课后习题答案第四章(4)先构造 NFA：XAbBa FbGbHEYaCDb Ib 用子集法将 NFA 确定化：a b X X T0=X A A ABDEF T1=ABDEF CI G CI CI G G T2=CI DY DY ABDEFY T3=G H H ABEFH T4=ABDEFY CI

45、G T5=ABEFH CI G 将T0、T1、T2、T3、T4、T5重新命名，分别用 0、1、2、3、4、5 表示。因为 4 中含有Y，所以它为终态。a b 0 1 1 2 3 2 4 3 5 4 2 3 5 2 3 DFA 的状态图：5编译原理课后习题答案第四章 0bb12a 453b b a b a b 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。答案：答案：先构造其矩阵 0 1

46、x z x y x,y z x,z y 用子集法将 NFA 确定化：0 1 x z x z xz y xz xz xy y xy xy xyz x xyz xyz xy 将 x、z、xz、y、xy、xyz 重新命名，分别用 A、B、C、D、E、F 表示。因为 B、C、F中含有 z，所以它为终态。0 1 A B A B C D C C E D E E F A F F E DFA 的状态图：7A010 FED0 B1 0 10 1 0 1 C编译原理课后习题答案第四章 第第 3 题题 将下图确定化：将下图确定化：答案：答案：用子集法将 NFA 确定化：.0 1 S VQ QU VQ VZ QU Q

47、U V QUZ VZ Z Z V Z.QUZ VZ QUZ Z Z Z 重新命名状态子集，令 VQ 为 A、QU 为 B、VZ 为 C、V 为 D、QUZ 为 E、Z 为 F。.0 1 S A B A C B B D E C F F D F.E C E F F F DFA 的状态图：8编译原理课后习题答案第四章 第第 4 题题 将下图的（将下图的（a）和（）和（b）分别确定化和最小化：）分别确定化和最小化：答案：答案：初始分划得 0：终态组0，非终态组1,2,3,4,5 对非终态组进行审查：1,2,3,4,5a 0,1,3,5 而0,1,3,5既不属于0，也不属于1,2,3,4,5 4 a 0

48、，所以得到新分划 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 这是最后分划了 9编译原理课后习题答案第四章 最小 DFA：第第 5 题题 构造一个 构造一个 DFA，它接收，它接收=0,1上所有满足如下条件的字符串：每个上所有满足如下条件的字符串：每个 1 都有都有 0 直接跟在右边。并给出该语言的正规式。直接跟在右边。并给出该语言的正规式。答案：答案：按题意相应的正规表达式是(0*10)

49、*0*，或 0*(0|10)*0*构造相应的 DFA，首先构造 NFA 为 用子集法确定化：I I0 I1 X,0,1,3,Y 0,1,3,Y 2 1,3,Y 0,1,3,Y 0,1,3,Y 1,3,Y 1,3,Y 2 2 2 重新命名状态集：S 0 1 1 2 3 4 2 2 4 4 3 3 3 DFA 的状态图：10编译原理课后习题答案第四章 可将该 DFA 最小化：终态组为1,2,4，非终态组为3，1,2,40 1,2,4，1,2,41 3，所以 1,2,4 为等价状态，可合并。第题第题 设无符号数的正规式为：设无符号数的正规式为：=dd*|dd*.dd*|.dd*|dd*10(s|=d

50、d*|dd*.dd*|.dd*|dd*10(s|)dd*|10(s|10(s|)dd*|.dd*10(s|10(s|)dd*|dd*.dd*10(s|10(s|)dd*化简，画出的 DFA，其中 d=0,1,2,9，s=，化简，画出的 DFA，其中 d=0,1,2,9，s=，答案：答案：先构造 NFA：XdB.d FGdH10d AC10dDsEd Yd sd 用子集法将 NFA 确定化：11编译原理课后习题答案第四章 s 10 d X XA T0=XA B F A B B F FG A A T1=B C C C T2=FG G H G G H H T3=A B F A T4=C D C D