编译原理第二版课后习答案.doc

《编译原理》课后习题答案第一章
第 1 章引论
第 1 题
解释下列术语：
（1）编译程序
（2）源程序
（3）目标程序
（4）编译程序得前端
（5）后端
（6）遍
答案：
（1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上得汇编语言或机器语
言，则此翻译程序称为编译程序。
（2） 源程序：源语言编写得程序称为源程序。
（3） 目标程序：目标语言书写得程序称为目标程序。
（4） 编译程序得前端：它由这样一些阶段组成：这些阶段得工作主要依赖于源语言而与
目标机无关。通常前端包括词法分析、语法分析、语义分析与中间代码生成这些阶
段，某些优化工作也可在前端做，也包括与前端每个阶段相关得出错处理工作与符
号表管理等工作。
（5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关得那些阶段，
即目标代码生成，以及相关出错处理与符号表操作。
（6） 遍：就是对源程序或其等价得中间语言程序从头到尾扫视并完成规定任务得过程。
第 2 题
一个典型得编译程序通常由哪些部分组成？各部分得主要功能就是什么？并画出编译程
序得总体结构图。
答案：
一个典型得编译程序通常包含 8 个组成部分，它们就是词法分析程序、语法分析程序、语
义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序与
错误处理程序。其各部分得主要功能简述如下。
词法分析程序：输人源程序，拼单词、检查单词与分析单词，输出单词得机内表达形式。
语法分析程序：检查源程序中存在得形式语法错误，输出错误处理信息。
语义分析程序：进行语义检查与分析语义信息，并把分析得结果保存到各类语义信息表
中。
中间代码生成程序：按照语义规则，将语法分析程序分析出得语法单位转换成一定形式
得中间语言代码，如三元式或四元式。
中间代码优化程序：为了产生高质量得目标代码，对中间代码进行等价变换处理。
目标代码生成程序：将优化后得中间代码程序转换成目标代码程序。
表格管理程序：负责建立、填写与查找等一系列表格工作。表格得作用就是记录源程序得
各类信息与编译各阶段得进展情况，编译得每个阶段所需信息多数都从表格中读取，产生得
中间结果都记录在相应得表格中。可以说整个编译过程就就是造表、查表得工作过程。需要指
出得就是，这里得“表格管理程序”并不意味着它就就是一个独立得表格管理模块，而就是指编译
程序具有得表格管理功能。
错误处理程序：处理与校正源程序中存在得词法、语法与语义错误。当编译程序发现源
程序中得错误时，错误处理程序负责报告出错得位置与错误性质等信息，同时对发现得错误
进行适当得校正（修复），目得就是使编译程序能够继续向下进行分析与处理。
注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，
就回答八部分。
第 3 题
何谓翻译程序、编译程序与解释程序？它们三者之间有何种关系？
答案：
翻译程序就是指将用某种语言编写得程序转换成另一种语言形式得程序得程序，如编译程
序与汇编程序等。
编译程序就是把用高级语言编写得源程序转换（加工）成与之等价得另一种用低级语言编
写得目标程序得翻译程序。
解释程序就是解释、执行高级语言源程序得程序。解释方式一般分为两种：一种方式就是，
源程序功能得实现完全由解释程序承担与完成，即每读出源程序得一条语句得第一个单词，
则依据这个单词把控制转移到实现这条语句功能得程序部分，该部分负责完成这条语句得功
能得实现，完成后返回到解释程序得总控部分再读人下一条语句继续进行解释、执行，如此
反复；另一种方式就是，一边翻译一边执行，即每读出源程序得一条语句，解释程序就将其翻
译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、执行，如此反复。无论
就是哪种方式，其加工结果都就是源程序得执行结果。目前很多解释程序采取上述两种方式得综
合实现方案，即先把源程序翻译成较容易解释执行得某种中间代码程序，然后集中解释执行
中间代码程序，最后得到运行结果。
广义上讲，编译程序与解释程序都属于翻译程序，但它们得翻译方式不同，解释程序就是
边翻译（解释）边执行，不产生目标代码，输出源程序得运行结果。而编译程序只负责把源
程序翻译成目标程序，输出与源程序等价得目标程序，而目标程序得执行任务由操作系统来
完成，即只翻译不执行。
第 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 机器上运行。
第６题
计算机执行用高级语言编写得程序有哪些途径?它们之间得主要区别就是什么?
答案：
计算机执行用高级语言编写得程序主要途径有两种，即解释与编译。
像Basic 之类得语言，属于解释型得高级语言。它们得特点就是计算机并不事先对高级语
言进行全盘翻译，将其变为机器代码，而就是每读入一条高级语句，就用解释器将其翻译为一
条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反复。
总而言之，就是边翻译边执行。
像C，Pascal 之类得语言，属于编译型得高级语言。它们得特点就是计算机事先对高级语
言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上瞧，
编译型得高级语言比解释型得高级语言更快。
《编译原理》课后习题答案第二章
第 2 章 PL/0 编译程序得实现
第 1 题
PL/0 语言允许过程嵌套定义与递归调用，试问它得编译程序如何解决运行时得存储管
理。
答案：
PL/0 语言允许过程嵌套定义与递归调用，它得编译程序在运行时采用了栈式动态存储
管理。（数组CODE 存放得只读目标程序，它在运行时不改变。）运行时得数据区S 就是由
解释程序定义得一维整型数组，解释执行时对数据空间S 得管理遵循后进先出规则，当每
个过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配得数据空间被释放。
应用动态链与静态链得方式分别解决递归调用与非局部变量得引用问题。
第 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;
begin (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 size
x variable 0 dx
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 得用途。
答案：
栈顶指针 T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL 与返回地址
RA 得用途说明如下：
T： 栈顶寄存器T 指出了当前栈中最新分配得单元(T 也就是数组S 得下标)。
B：基址寄存器，指向每个过程被调用时，在数据区S 中给它分配得数据段起始 地址，
也称基地址。
SL： 静态链，指向定义该过程得直接外过程（或主程序）运行时最新数据段得基地址，
用以引用非局部（包围它得过程）变量时，寻找该变量得地址。
DL： 动态链，指向调用该过程前正在运行过程得数据段基地址，用以过程执行结束释
放数据空间时，恢复调用该过程前运行栈得状态。
RA： 返回地址，记录调用该过程时目标程序得断点，即调用过程指令得下一条指令得
地址，用以过程执行结束后返回调用过程时得下一条指令继续执行。
在每个过程被调用时在栈顶分配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 为局部变量得个数+3。
OPR 0 0
在过程目标程序得出口处，释放数据段（退栈），恢复调用该过程前正在运行得过程得
数据段基址寄存器B 与栈顶寄存器T 得值，并将返回地址送到指令地址寄存器P 中，以使
调用前得程序从断点开始继续执行。
CAL L A
调用过程，完成填写静态链、动态链、返回地址，给出被调用过程得基地址值，送入基
址寄存器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〈条件〉
《编译原理》课后习题答案第三章
第3 章 文法与语言
第1 题
文法G＝({A,B,S},{a,b,c},P,S)其中P 为：
S→Ac|aB
A→ab
B→bc
写出L(G[S])得全部元素。
答案：
L(G[S])={abc}
第2 题
文法G[N]为：
N→D|ND
D→0|1|2|3|4|5|6|7|8|9
G[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|D
D->0|1|2|3|4|5|6|7|8|9
第4 题
已知文法G[Z]：
Z→aZb|ab
写出L(G[Z])得全部元素。
答案：
Z=>aZb=>aaZbb=>aaa、、Z、、、bbb=> aaa、、ab、、、bbb
L(G[Z])={anbn|n>=1}
第5 题
写一文法，使其语言就是偶正整数得集合。 要求：
(1) 允许0 打头；
(2)不允许0 打头。
答案：
(1)允许0 开头得偶正整数集合得文法
E→NT|D
T→NT|D
N→D|1|3|5|7|9
D→0|2|4|6|8
(2)不允许0 开头得偶正整数集合得文法
E→NT|D
T→FT|G
N→D|1|3|5|7|9
D→2|4|6|8
F→N|0
G→D|0
第6 题
已知文法G：
<表达式>::=<项>｜<表达式>＋<项>
<项>::=<因子>｜<项>*<因子>
<因子>::=（<表达式>）｜i
试给出下述表达式得推导及语法树。
（５）i+(i+i)
（６）i+i*i

答案：
<表达式>
<表达式> + <项>
<因子>
<表达式>
<表达式> + <项>
<因子>
i
<项>
<因子>
i
<项>
<因子>
i
（ )
(5) <表达式>
=><表达式>＋<项>
=><表达式>＋<因子>
=><表达式>＋（<表达式>）
=><表达式>＋（<表达式>＋<项>）
=><表达式>＋（<表达式>＋<因子>）
=><表达式>＋（<表达式>＋i）
=><表达式>＋（<项>＋i）
=><表达式>＋（<因子>＋i）
=><表达式>＋（i＋i）
=><项>＋（i＋i）
=><因子>＋（i＋i）
=>i＋（i＋i）
<表达式>
<表达式> + <项>
<项> * <因子>
<因子> i
<项>
<因子>
i
i
(6) <表达式>
=><表达式>＋<项>
=><表达式>＋<项>*<因子>
=><表达式>＋<项>*i
=><表达式>＋<因子>*i
=><表达式>＋i*i
=><项>＋i*i
=><因子>＋i*i
=>i＋i*i
第7 题
证明下述文法G[〈表达式〉]就是二义得。
〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉
〈运算符〉∷=+|-|*|/
答案：
可为句子a+a*a 构造两个不同得最右推导:
最右推导1 〈表达式〉〈表达式〉〈运算符〉〈表达式〉
〈表达式〉〈运算符〉a
〈表达式〉* a
〈表达式〉〈运算符〉〈表达式〉* a
〈表达式〉〈运算符〉a * a
〈表达式〉+ a * a
a + a * a
最右推导2 〈表达式〉〈表达式〉〈运算符〉〈表达式〉
〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉
〈表达式〉〈运算符〉〈表达式〉〈运算符〉 a
〈表达式〉〈运算符〉〈表达式〉 * a
〈表达式〉〈运算符〉a * a
〈表达式〉+ a * a
a + a * a

第8 题
文法G[S]为：
S→Ac|aB
A→ab
B→bc
该文法就是否为二义得？为什么？
答案：
对于串abc
(1)S=>Ac=>abc (2)S=>aB=>abc
即存在两不同得最右推导。所以，该文法就是二义得。
或者：
对输入字符串abc，能构造两棵不同得语法树，所以它就是二义得。
S
a B
b c
S
A c
a b
第9 题
考虑下面上下文无关文法：
S→SS*|SS+|a
(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。
S
S S *
S S + a
a a
(2)G[S]得语言就是什么？
答案：
(1)此文法生成串aa+a*得最右推导如下
S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*
(2)该文法生成得语言就是：*与+得后缀表达式，即逆波兰式。
第10 题
文法S→S(S)S|ε
(1) 生成得语言就是什么？
(2) 该文法就是二义得吗？说明理由。
答案：
（１） 嵌套得括号
（２） 就是二义得，因为对于（）（）可以构造两棵不同得语法树。
第11 题
令文法G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(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 可能有哪些元素？
(3)找出该句子得所有短语、直接短语、句柄。
B
a
S
A B S
a
S B A
ε b b a

答案：
(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→a B→SBB|b
可能元素有：ε aa ab abbaa aaabbaa ……
(3)该句子得短语有：
a 就是相对A 得短语
ε 就是相对S 得短语
b 就是相对B 得短语
εbb 就是相对B 得短语
aa 就是相对S 得短语
aεbbaa 就是相对S 得短语
直接短语有：a ε b
句柄就是：a
第14 题
给出生成下述语言得上下文无关文法：
（1）{ anbnambm| n，m>=0}
（2）{ 1n0m 1m0n| n，m>=0}
（3）{WaWr|W 属于{0|a}*，Wr 表示W得逆}
答案：
（１）
S→AA
A→aAb|ε
（２）
S→1S0|A
A→0A1|ε
（３）
S→0S0|1S1|ε
第16 题
给出生成下述语言得三型文法：
(1){an|n >=0 }
(2) { anbm|n,m>=1 }
(3){anbmck|n,m,k>=0 }
答案：
(1) S→aS|ε
(2)
S→aA
A→aA|B
B→bB|b
(3)
A→aA|B
B→bB|C
C→cC|ε
第17 题
习题７与习题11 中得文法等价吗？
答案：
等价。
第18 题
解释下列术语与概念：
（１） 字母表
（２） 串、字与句子
（３） 语言、语法与语义
答案：
（１）字母表：就是一个非空有穷集合。
（２）串：符号得有穷序列。
字：字母表中得元素。
句子：如果 Z x , x ∈V *T 则称 x 就是文法 G 得一个句子。 +
《编译原理》课后习题答案第四章
第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：
X 1 A
ε B
1 C 0 D 1 E
0
ε
F 1 G 0 H 1 I 0 J 1 K
L
ε ε
0
Y
ε
ε
ε
ε
用子集法将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
CGI 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
将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 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
0 1 0
12
1 2
7
10 8
3
4
5
6
9
11 13 14
1
1
0
1
0
1
0
1
1
0
1
1
0
1
0
1
0 1
0
1
0
1
(3) 先构造NFA：
先构造NFA：
X a A
ε B
a,b
ε
D a E a F
C
ε
Y
ε
ε
b
ε
b
用子集法将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 BEF 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
0 a 1 b 3
2
a
5
a 4
b
a
b
a
b
a
b
(4) 先构造NFA：
X A
b
ε B
a
F b G b H
E
ε
Y
a
ε
C D b ε
I b
ε
ε
ε
ε
用子集法将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 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 得状态图：
0 b 1 b
2
a
4
5
3
b
b
a
b
a
b
第２题
已知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
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 得状态图：
A
0 1
0
F
E
D
0
B
1
0
1
0
1
0
1
C
《编译原理》课后习题答案第四章
第3 题
将下图确定化：
答案：
用子集法将NFA 确定化：
、 0 1
S VQ QU
VQ VZ QU
QU 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 得状态图：
第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}
这就是最后分划了
最小DFA：
第5 题
构造一个DFA，它接收Σ={0,1}上所有满足如下条件得字符串：每个1 都有0 直接跟在
右边。并给出该语言得正规式。
答案：
按题意相应得正规表达式就是(0*10)*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 得状态图：
可将该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：
X
d
、 B
d
F G
d
H
10
d
A
ε
C
10
d
D
s
ε
E d
Y
d
s
ε
d
用子集法将NFA 确定化：
ε • 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 DE
T5=G H
T6=H H
T7=DE E Y
E E
Y Y
T8=E Y
T9=Y Y
将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。
• s 10 d
0 1 2 3
1 4
2 5 6
3 1 2 3
4 7 4
5 6
6 6
7 8 9
8 9
9 9
DFA 得状态图：

•
d
6
2 5
d
3
d
d
4 7
8
9
0
1
10
d
s
•
10
10
d
d
s
d
d
d
第7 题
给文法G[S]：
S→aA|bQ
A→aA|bB|b
B→bD|aQ
Q→aQ|bD|b
D→bB|aA
E→aB|bF
F→bD|aE|b
构造相应得最小得DFA。
答案：
先构造其NFA：
S
a
A
a
Z
Q
b
B
D
a
E
b
F
b
b
a
b
a
a
b
b b
b
a
b
用子集法将NFA 确定化：
a b
S A Q
A A BZ
Q Q DZ
BZ Q D
DZ A B
D A B
B Q D
将S、A、Q、BZ、DZ、D、B 重新命名，分别用0、1、2、3、4、5、6 表示。因为3、
4 中含有z，所以它们为终态。
a b
0 1 2
1 1 3
2 2 4
3 2 5
4 1 6
5 1 6
6 2 5
DFA 得状态图：
0
a
a
5
2
b
3
a
a
b
4
1
6
b
a
a
b
b
b
a
b
令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。
最小化为：

A
a , b
D C
a
a
B
b
a
b
b
第８题
给出下述文法所对应得正规式：
S→0A|1B
A→1S|1
B→0S|0
答案：
解方程组S 得解：
S=0A|1B
A=1S|1
B=0S|0
将A、B 产生式得右部代入S 中
S=01S|01|10S|10=（01|10）S|（01|10）
所以：S= (01|10)*(01|10)
第9 题
将下图得DFA 最小化，并用正规式描述它所识别得语言。
1
a
2
6
c
3
c
b
5
4 7
b
b
a b
b
b
d
d
a
答案：
令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。
最小化为：
A
a
C D
b
d
B
b
c
a
b
r=b*a(c|da)*bb*=b*a(c|da)*b+
《编译原理》课后习题答案第五章
第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