-
《编译原理》课后习题
第
1
章引论
第
1
题解释下列术语：
（
1
）
编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语
言，则此翻译程序称为编译程序。
（
2
）
源程序：源语言编写的程序称为源程序。
（
3
）
目标程序：目标语言书写的程序称为目标程序。
（
4
）
编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与
目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生
成这些阶
段，某些优化工作也可在前端做，也包括与前端每个
阶段相关的出错处理工作和符
号表管理等工作。
（
5
）
后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，
即目标代码生成，以及相关出错处理和符号表操作。
（
6
）
遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。
第
2
题
一个典型的编译程序通常由哪些部
分组成？各部分的主要功能是什么？并画出编译程
序的总体结构图。
答案：
一个典型的编译程序通常包含
8
个组成部分，
它们是词法分析程序
、
语法分析程序、
语义分析程序、
中间
代码生成程序、
中间代码优化程序、
目标代码生成程序、表格管
理程序
和错误处理程序。其各部分的主要功能简述如下。
词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。
语法分析程序：检查源程序中存在的形式语法错误，输出错误处理
信息。
语义分析程序：进行语义检查和分析语义信息，并把分
析的结果保存到各类语义信息表
中。
中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式<
/p>
的中间语言代码，如三元式或四元式。
中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。
目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
表格管理程序：负责建立、填写和查找等一系列表格工作。表
格的作用是记录源程序的
各类信息和编译各阶段的进展情况，
编译的每个阶段所需信息多数都从表格中读取，
产生的
中间结果都记录在相应的表格中。
可以说整个
编译过程就是造表、
查表的工作过程。
需要指
< br>
出的是，这里的
“表格管理程序”并不意味着它就是一
个独立的表格管理模块，而是指编译
程序具有的表格管理功能。
错误处理
程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源
程序中的错误时，
错误处理程序负责报告出错的位置和错误性质等信息，
同时对发现的错误
进行适当的校正（
修复）
，目的是使编译程序能够继续向下进行分析和处理。
第
3
题何
谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？
答案：
翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，<
/p>
如编译
程序和汇编程序等。
编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编
写的目标程序的翻译程序。
解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，
源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个
单词，
则依据这个单词把控制转移到实现这条语句功能的程序
部分，
该部分负责完成这条语句的功
能的实现，
完成后返回到解释程序的总控部分再读人下一条语句继续进行解释、
执行，
如此
反复；<
/p>
另一种方式是，一边翻译一边执行，即每读出源程序的一条语句，解释程序就将其翻
译成一段机器指令并执行之，然后再读人下一条语句继续进行解释、
执行，
如此反复。
无论
是哪种方式，
其加工结果都是源程序的执行结果。
目
前很多解释程序采取上述两种方式的综
合实现方案，
即先把源程序翻译成较容易解释执行的某种中间代码程序，
然后集中解释
执行
中间代码程序，最后得到运行结果。
广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是
边翻译（解释）边执行，不产生目标代码，输出源程序的运行结果。而编译程序只负责把
源
程序翻译成目标程序，
输出与源程
序等价的目标程序，
而目标程序的执行任务由操作系统来
完成，即只翻译不执行。
第
4
题对
下列错误信息，
请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、
代码生成）报告的。
（
1
）
else
没有匹配的
if
（
2
）
数组下标越界
（
3
）
使用的函数没有定义
（
4
）
在数中出现非数字字符
答案：
（
1
）
语法分析
（
2
）
语义分析
（
3
）
语法分析
（
4
）
词法分析
第
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
第３题为只包含数字、加号和减号的表达式，例如
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
→
< br>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
：
<
表达式
>::=<
项
>
｜
<
表达式
>
＋
<
项
>
< br><
项
>::=<
因子
>
｜
<
项
>*<
因子
>
<
因子
>::=
（
<
表达式
>
）｜
i
试给出下述表达式的推导及语法树。
（
1
）
i
（<
/p>
2
）
（
i
）
（
3
）
i*i
（
4
）
i*i
+i
（
5
）
i+(i+i)
（
6
）
i+i*i
第
7
题证明下述文法
G[
〈表达式〉
]
是二义的。
〈表达式〉∷
=a|(
〈表达式〉
)|
〈表达式〉
〈运算符〉
〈表达式〉
〈运算符〉∷
=+|-|*|/
答案：可为句子
a+a*a
构造两个不同的最右推导
:
最右推导
1
〈表达式〉
=>
〈表达式〉
〈运算符〉
〈表达式
〉
=>
〈表达式〉
< br>〈运算符〉
a
=>
〈表达式〉
* a
=>
〈表达式〉
〈运算符〉
〈表达式〉
* a
=>
〈表达式〉<
/p>
〈运算符〉
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
，能构造两棵不同的
语法树，所以它是二义的。
第
9
题
<
/p>
考虑下面上下文无关文法：
S
→
SS*|SS+|a
(1)
表明通过此文法如
何生成串
aa+a*
，并为该串构造语法树。
< br>
(2)G[S]
的语言是什么？
答案：
(1)
此文法生成串
aa+a*
的最右推导如下
S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* <
/p>
(2)
该文法生成的语言是：
*
和
+
的后缀表达式，即逆波兰式。
第
10
题文法
S
→
S(S)S|
ε<
/p>
(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)
找出该句子的所有短语、直接短语、句柄。
答案：
(1)
串
abbaa
最左推导
:
S=>A
BS=>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}*
，
W
r
表示
W
的逆
}
答案：
（
１）
S
→
AA
A
→
aAb|
ε
（２）
S
→
1S0|A
A
→
0A1|
ε
（３）
S
→
0S0|1S
1|
ε
第
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|
ε
第
18
题解释下列术语和概念：
答案：
（１）字母表：是一个非空有穷集合。
（２）串：符号的有穷序列。字：字母表中的元素。
句子：如果
Z-+ x , x
∈
V *T
则称
x
是文法
G
的一个句子。
（３）
语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言
就是所
有该语言的程序的全体。
语言
可以看成在一个基本符号集上定义的，
按一定规则构成的一切
基
本符号串组成的集合。
语法：表示构成语言句子的各个记号之
间的组合规律。程序的结构或形式。
语义：表示按照各种表示
方法所表示的各个记号的特定含义。语言所代表的含义。
第
4
章
词法分析
第
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)
=>
(((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
→
ε
非终结符
FIRST
集
FOLLOW
集
S
{a,
∧
,(}
{#,,,)}
T
{a,
∧
,(}
{)}....
N
{,,ε}
{)}....
对左部为
N
的产生式可知：
FIRST
（→
, S
N
）
={
，
}
FIRST
（→
ε
< br>）
={
ε
}
FOLLOW
（
N
< br>）
={)}
由于
SELECT(N
→
, S
N)
∩
SELECT(N
→
ε
)
={
，
}
∩
{ )}=
所以文法是
LL(1)
的。
预测分析表（
Predicting Analysis
Table
）
也可由预测分析表中无多重入口判定文法是
< br>LL(1)
的。
(3)
对输入串（
a,a
）
#
的分析过程为：
可见输入串（
a,a
）
#
是文法的句子。
第
3
题
<
/p>
已知文法
G[S]
：
S
→
MH|a
H
→
LSo|
ε
K
→
dML|
ε
L
→
eHf
M
→
K|bLM
判断
G
是否是
LL(1)
文法，如果是，构造
LL(1)
< br>分析表。
答案：
文法展开为：
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 }=
SELECT(K
→
d M L)
∩
SELECT(K
→
ε
) ={ d }
∩
{ e,#,o }=
SELEC
T(M
→
K)
∩
SELECT(M
→
b L M) ={
d
，
e,#,o
}
∩
{ b }=
所以文法是
LL(1)
的。
预测分析表：
由预测
分析表中无多重入口也可判定文法是
LL(1)
的。
第
7
题
对于一个文法若消除了左递归，提
取了左公共因子后是否一定为
LL(1)
文法
< br>?
试对下面
文法进行改写，并对改写后的文法进行判断。
(
１
)A<
/p>
→
baB|
ε
B
→
Abb|a
(2)
A
→
aABe|a
B
→
Bb|d
(3)
S
→
Aa|b
A
→
SB
B
→
ab
答案：
(
１
)
先改写文法为：
0) A
→
baB
1) A
→
ε
2) B
→
baBbb
3) B
→
bb
4) B
→
a
再改写文法为：
0)
A
→
baB
1)
A
→
ε
2)
B
→
bN
3)
B
→
a
4)
N
→
aBbb
5)
N
→
b
预测分析表：
由预测分析表中无多重入口判定文
法是
LL(1)
的。
（
2
）
文法：
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
{a}
{#,d}
B
{d}
{e}
N
{a,ε}
{#,d}
N1
{b,ε}
{e}
对相同左部的产生式可知：
SELECT(N
→
A B e)
∩
SELECT(N
→
ε
) ={ a }
∩
{#,d }=
SELECT(N1
→
b N1)
∩
SELECT(N1
→
< br>ε
) ={ b }
∩
{ e }=
所以文法是
LL(1)
的。
预测分析表（
Predicting Analysis
Table
）
也可由预测分析表中无多重入口判定文法是
< br>LL(1)
的。
（
3
）文法：
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}
{#}
B
{a}
{a}
N
{ε,a}
{#}
对相同左部的产生式可知：
SELECT(N
< br>→
B a N)
∩
SELECT
(N
→
ε
) ={ a
}
∩
{# }=
所以文法是
LL(1)
的。
预测分析表（
Predicting Analysis
Table
）
也可由预测分析表中无多重入口判定文法是
< br>LL(1)
的。
第
2
种改写：
用
S
的产生式右部代替
A
的产生式右部的
S
得：
S
→
Aa|b
A
→
AaB|bB
B
→
ab
消除左递归后文法变为：
0)
S
→
A a
1)
S
→
b
2)
A
→
b B N
3)
N
→
a B N
4)
N
→
ε
-
-
-
-
-
-
-
-
-
上一篇：最新电子科技大学半导体物理期末考试试卷a试题答案
下一篇：投资学英语词汇