第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
编译原理习题.doc
第一章 编译程序概述
它不生成目标代码，它每遇到一个语句，就要对这个语句进行
1.1 什么是编译程序
分析以决定语句的含义，执行相应的动作。右面的图示意了它
编译程序是现代计算机系统的基本组成部分之一，而且多
的工作机理
数计算机系统都含有不止一个高级语言的编译程序。对有些高
级语言甚至配置了几个不同性能的编译程序。
第二章：PL/0 编译程序
1.2 编译过程概述和编译程序的结构
问答第 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)
编译程序还能自动校正错误，这些工作称之为出错处理。图 1.3
call q; end (r); begin (s) call r; end (s);
begin (p)
表示了编译的各个阶段。
图 1.3 编译的各个阶段
call s; end (p); begin (main) call p;
end (main).
答 ： 程序执行到赋值语句 b∶=10 时运行栈的布局示意图为：
1.3 高级语言解释系统
为了实现在一个计算机上运行高级语言的程序,主要有两
个途径：第一个途径是把该程序翻译为这个计算机的指令代码
序列，这就是我们已经描述的编译过程。第二个途径是编写一
个程序，它解释所遇到的高级语言程序中的语句并且完成这些
语句的动作，这样的程序就叫解释程序。从功能上说，一个解
释程序能让计算机执行高级语言。它与编译程序的主要不同是
1
问答第 3 题
用过程时的下一条指令继续执行。
写出题 2 中当程序编译到 r 的过程体时的名字表 table 的
在每个过程被调用时在栈顶分配 3 个联系单元，用以存放
内容。
name kind level/val adr size
SL，DL， RA。
问答第 5 题
答
题 2 中当程序编译到 r 的过程体时的名字表 table 的内
容为：
name kind
level/val adr size
procedure 1
入 口 （ 待
5
该过程前正在运行的过程的数据段基址寄存器 B 和栈顶寄存器 T
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
在过程目标程序的出口处，释放数据段（退栈），恢复调用
的值，并将返回地址送到指令地址寄存器 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 语句的语法图为：
x
y
p
a
q
s
c
d
r
e
f
variable 0
variable 0
dx
dx+1
过 程 p 的
procedure 0
入 口 （ 待
4
variable 1
procedure 1
填）
dx
过 程 q 的
入口
4
过 程 s 的
variable 2
variable 2
procedure 2
variable 3
variable 3
填）
dx
dx+1
5
过 程 r 的
入口
dx
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： 返回地址，记录调用该过程时目标程序的断点，即调
用过程指令的下一条指令的地址，用以过程执行结束后返回调
2
EBNF 的语法描述为： 〈 重复语句〉::= repeat〈语句〉{；
〈语句〉}until〈条件〉
第三章：词法分析程序
问答第 1 题
构造正规式 1(0|1) *101 相应的 DFA.
答：先构造 NFA：
S
VQ
QU
VZ
V
QUZ
Z
VQ
VZ
V
Z
Z
VZ
Z
QU
QU
QUZ
Z
.
QUZ
Z
重新命名状态子集，令 VQ 为 A、QU 为 B、VZ 为 C、V 为 D、QUZ
为 E、Z 为 F。
用子集法将 NFA 确定化
.
X
A
AB
AC
0
.
A
AC
A
1
A
AB
AB
ABY
ABY
AC
AB
.
S
A
B
C
D
E
F
0
A
C
D
F
F
C
F
1
B
B
E
F
.
E
F
除 X，A 外，重新命名其他状态，令 AB 为 B、AC 为 C、ABY 为 D，
DFA 的状态图：
因为 D 含有 Y（NFA 的终态），所以 D 为终态。
.
X
A
B
C
D
0
.
A
C
A
C
1
A
B
B
D
B
DFA 的状态图：:
问答第 2 题
将下图确定化：
解：
用子集法将 NFA 确定化：
.
0
1
问答第 3 题
将下图的（a）和（b）分别确定化和最小化：
3
2
3
4
2
4
4
3
3
DFA 的状态图：
解：
初始分划得
Π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}
可将该 DFA 最小化：
{2,3} a
{1,3}，故状态 2 和状态 3 不等价，得到新分划
终态组为{1,2,4}，非终态组为{3}，{1,2,4}0 {1,2,4}，
Π3：{0}，{2}，{3}，{4}，{1, 5}
{1,2,4}1 {3}，所以 1,2,4 为等价状态，可合并。
这是最后分划了
最小 DFA：
问答第 4 题
第四章 文法和语言
问答第 1 题
构造一个 DFA，它接收Σ={0,1}上所有满足如下条件的字符
写一文法，使其语言是偶正整数的集合。 要求：
串：每个 1 都有 0 直接跟在右边。并给出该语言的正规式。
解：按题意相应的正规表达式是(0*10)*0*，或 0*(0 | 10)*0* 构
(1) 允许 0 打头；
(2)不允许 0 打头。
造相应的 DFA，首先构造 NFA 为
答 ：(1)允许 0 开头的偶正整数集合的文法
用子集法确定化：
I
I0
I1
{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}
重新命名状态集：
S
1
0
2
1
3
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
问答第 2 题
证明下述文法 G[〈表达式〉]是二义的。
〈表达式〉∷=a|(〈表达式〉)|〈表达式〉
〈运算符〉〈表达式〉 〈运算符〉∷=+|-|*|/
答：可为句子 a+a*a 构造两个不同的最右推导:
4
最右推导 1 〈表达式〉 〈表达式〉〈运算符〉〈表达式〉
〈表达式〉〈运算符〉a
〈表达式〉* a
〈表达式〉〈运算符〉〈表达式〉* a
B→bB|b
(2)
A→aA|B
B→bB|C
C→cC|ε
〈表达式〉〈运算符〉a * a
问答第 6 题
〈表达式〉+ a * a
a + a * a
最右推导 2 〈表达式〉 〈表达式〉〈运算符〉〈表达式〉
〈表达式〉〈运算符〉〈表达式〉〈运算
给出下述文法所对应的正规式：
S→0A|1B
A→1S|1
B→0S|0
符〉〈表达式〉
符〉 a
问答第 3 题
令文法 G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
〈表达式〉〈运算符〉〈表达式〉〈运算
第五章 自顶向下语法分析方法
答： R = (01 | 10) ( 01 | 10 )*
〈表达式〉〈运算符〉〈表达式〉 * a
〈表达式〉〈运算符〉a * a
〈表达式〉+ a * a
a + a * a
问答第 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
证明 E+T*F 是它的一个句型，指出这个句型的所有短语、
的句子。
直接短语和句柄。
答 ： 因为存在推导序列: E
E+T
E +
* F 所以
E+T*F 是文法 G[E]的一个句型
句型 E+T*F 的
短语有:E+T*F,T*F
直接短语有:T*F
句柄为:T*F
问答第 4 题
给出生成下述语言的上下文无关文法：
（1）{ anbnambm| n，m>=0}
（2） { 1n0m 1m0n| n，m>=0}
答： (1)
S→AA
(2)
A→aAb|ε
S→1S0|A
A→0A1|ε
问答第 5 题
给出生成下述语言的三型文法：
(1) { anbm|n,m>=1 }
(2){anbmck|n,m,k>=0 }
答： (1)
S→aA
A→aA|B
答：文法
S→a|∧|(T)
T→T,S|S
(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)
5
(((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)
(((a,a),∧,(a)),S)
(((a,a),∧,(a)),a)
(2) 改写文法为：
0) S→a
1) S→∧
2) S→( T )
3) T→S N
4) N→, S N
5) N→ε
非终结
符
S
T
N
FIRST 集
FOLLOW
集
{a,∧,(} {#,,,)}
{a,∧,(} {)}....
{,,ε}. {)}....
对左部为 N 的产生式可知：
FIRST （→, S N）={，}
FIRST （→ε）={ε}
FOLLOW （N）={)}
由于 SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}=
所以文法是 LL(1)的。
预测分析表（Predicting Analysis Table）
a ∧ (
)
,
#
S →a →∧ →(T)
→S
→S
N
N
→S N
T
N
→ε
→,
S N
也可由预测分析表中无多重入口判定文法是 LL(1)的。
(3) 对输入串（a,a）#的分析过程为：
栈（STACK）
当 前 输 入 符
（CUR_CHAR）
#S
#)T(
#)T
#)NS
#)Na
(
(
a
a
a
剩 余 输 入 符
所 用 产 生 式
（INOUT_STRING）
（OPERATION）
a,a)#...
a,a)#...
,a)#...
,a)#...
,a)#...
..
S→(T)
.
T→SN
S→a
#)N
#)NS,
#)NS
#)Na
#)N
#)
#
,
,
a
a
)
)
#
a)#...
a)#...
)#...
)#...
#...
#...
.
N→,SN
.
S→a
.
N→ε
可见输入串（a,a）#是文法的句子。
问答第 2 题
已知文法 G[S]：
S→MH|a
H→LSo|ε
K→dML|ε
L→eHf
M→K|bLM
判断 G 是否是 LL(1)文法，如果是，构造 LL(1)分析表。
答：文法：
S→MH|a
H→LSo|ε
K→dML|ε
L→eHf
M→K|bLM
展开为：
0） S→M H
1） S→a
2） H→L S o
3） H→ε
4） K→d M L
5） K→ε
6） L→e H f
7） M→K
8） M→b L M
非
终
结
符
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→M H)∩SELECT(S→a) ={ d,b ,e，#,o }∩ { a }=
SELECT(H→L S o)∩SELECT(H→ε) ={ e }∩ { #,f,o }=
6
SELECT(K→d M L)∩SELECT(K→ε) ={ d }∩ { e,#,o }=
SELECT(M→K)∩SELECT(M→b L M) ={ d，e,#,o }∩ { b }=
所以文法是 LL(1)的。
预测分析表（Predicting Analysis Table）
a
o
d
e
f
b
#
S →a →MH →MH →MH
→MH →MH
M
H
L
K
→K →K →K
→bLM →K
→ε
→LSo →ε
→ε
→eHf
→ε →dML →ε
→ε
由预测分析表中无多重入口也可判定文法是 LL(1)的。
问答第 3 题
对于一个文法若消除了左递归，提取了左公共因子后是否
一定为 LL(1)文法?试对下面文法进行改写，并对改写后的文法
进行判断。
(1) A→aABe|a
B→Bb|d
(3) S→Aa|b
A→SB
B→ab
答：（1） 文法：
A→aABe|a
B→Bb|d
提取左公共因子和消除左递归后文法变为：
0) A→a N
1) N→A B e
2) N→ε
3) B→d N1
4) N1→b N1
5) N1→ε
非 终
FIRST
FOLLOW
结符
集
集
A
B
N
{a}... {#,d}
{d}... {e}..
{a,ε} {#,d}
N1
{b,ε} {e}..
→d
N1
B
N1
→ε
→b
N1
N →ABe
→ε →ε
也可由预测分析表中无多重入口判定文法是 LL(1)的。
（2）文法：
S→Aa|b
A→SB
B→ab
第 1 种改写：
用 A 的产生式右部代替 S 的产生式右部的 A 得：
S→SBa|b
B→ab
消除左递归后文法变为：
0) S→b N
1) N→B a N
2) N→ε
3) B→a b
非 终
FIRST
FOLLOW
结符
集
集
S
B
N
{b}... {#}
{a}... {a}
{ε,a} {#}
对相同左部的产生式可知：
SELECT(N→B a N)∩SELECT(N→ε) ={ a }∩ {# }=
所以文法是 LL(1)的。
预测分析表（Predicting Analysis Table）
a
b
#
→b
N
S
B
N
→a
b
→B
a N
→ε
也可由预测分析表中无多重入口判定文法是 LL(1)的。
对相同左部的产生式可知：
第 2 种改写：
SELECT(N→A B e)∩SELECT(N→ε) ={ a }∩ {#,d }=
用 S 的产生式右部代替 A 的产生式右部的 S 得：
SELECT(N1→b N1)∩SELECT(N1→ε) ={ b }∩ { e }=
所以文法是 LL(1)的。
预测分析表（Predicting Analysis Table）
a
e
b
d
#
A →a N
S→Aa|b
A→AaB|bB
B→ab
消除左递归后文法变为：
0) S→A a
7
1) S→b
2) A→b B N
3) N→a B N
4) N→ε
5) B→a b
非 终
FIRST
FOLLOW
结符
集
集
S
A
B
N
{b}... {#}
{b}... {a}
{a}... {a}
{a,ε} {a}
对相同左部的产生式可知：
SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠
SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠
所以文法不是 LL(1)的。
预测分析表（Predicting Analysis Table）
a
b
#
S
A
→A a..
→b....
→b B N
B →a b..
N →a B N
→ε...
也可由预测分析表中含有多重入口判定文法不是 LL(1)的。
第六章 算符优先分析法
问答第 1 题
已知文法 G[S]为：
S→a|∧|(T)
T→T,S|S
(1) 计算 G[S]的 FIRSTVT 和 LASTVT。
(2) 构造 G[S]的算符优先关系表并说明 G[S]是否为算符优
先文法。
(3) 给出输入串(a,a)#和(a,(a,a))#的算符优先分析过
程。
答：文法：
S→a|∧|(T)
T→T,S|S
展开为：
S→a
S→∧
S→(T)
T→T,S
T→S
(1) FIRSTVT -- LASTVT 表
非 终
FIRSTVT
LASTVT
结符
集
集
S
T
{
a ∧
{
a
( }..
∧ ) }..
{
a ∧
{
a
( , }
∧ ) , }
(2) 算符优先关系表（OPERATER PRIORITY RELATION TABLE）
a ∧ (
)
,
#
.
.
.
a
.
∧
.
.
.
.
.
(
)
,
#
表中无多重人口所以是算符优先（OPG）文法。
（3）对输入串（a,a）#的算符优先分析过程为
栈
当 前 输
（ S
入 字 符
TAC
（ CHAR
K）
）
剩余输入串
动
作
（ INPUT_ST
（ACTION
RING）
）
a,a)#...
Move in
,a)#...
Move in
a)#...
a)#...
)#...
#...
#...
#...
Reduce:
S→a
Move in
Move in
Reduce:
S→a
Reduce:
T→T,S
Move in
Reduce:
#
#(
(
#(a
a
#(N
,
#(N
,
,
a
#(N
)
,a
)
#(N
)
,N
#
#(N
#
#(N
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
