复习例题答案.docx
《复习例题答案.docx》由会员分享，可在线阅读，更多相关《复习例题答案.docx（12页珍藏版）》请在冰点文库上搜索。
复习例题答案
编译原理复习例题
一选择题
1．编译的各阶段工作都涉及b。
[A]词法分析[B]表格管理[C]语法分析[D]语义分析
2．d型文法也称为正规文法。
[A]0[B]1[C]2[D]3
3．d文法不是LL
（1）的。
[A]递归[B]右递归[C]2型[D]含有公共左因子的
4．文法E→E+E|E*E|i的句子i*i+i*i有c棵不同的语法树。
[A]1[B]3[C]5[D]7
5．文法S→aaS|abc定义的语言是c。
[A]{a2kbc|k>0}[B]{akbc|k>0}
[C]{a2k-1bc|k>0}[D]{akakbc|k>0}
6．若B为非终结符，则A→.B为d。
[A]移进项目[B]归约项目[C]接受项目[D]待约项目
7．同心集合并可能会产生新的d冲突。
[A]二义[B]移进/移进[C]移进/归约[D]归约/归约
8．代码优化时所依据的是c。
[A]语法规则[B]词法规则
[C]等价变换规则[D]语义规则
9．表达式a-（-b）*c的逆波兰表示（@为单目减）为b。
[A]a-b@c*[B]ab@c*-[C]ab@-[D]ab@c-*
10．过程的DISPLAY表是用于存取过程的A。
[A]非局部变量[B]嵌套层次[C]返回地址[D]入口地址
二填空题
1．词法分析阶段的任务式从左到右扫描 源程序 ，从而逐个识别单词 。
2．对于文法G[E]：
E→T|E+TT→F|T*FF→P^F|P
P→（E）|i，句型T+T*F+i的句柄是 T 。
3．最右推导的逆过程称为最左规约，也称为规范推导。
4．符号表的每一项是由名字栏和信息栏两个栏目组成。
在目标代码生成阶段，符号表是内存分配的依据。
三判断题（认为正确的填“T”，错的填“F”）
【T】1．同心集的合并有可能产生“归约/归约”冲突。
【T】2．一个文法所有句子的集合构成该文法定义的语言。
【F】3．非终结符可以有综合属性，但不能有继承属性。
【T】4．逆波兰表示法表示表达式时无需使用括号。
【F】5．一个有穷自动机有且只有一个终态。
【F】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。
四解答题
1．给定文法G和句型（T+F）*i+T,
G:
E→E+T|TT→T*F|FF→（E）|i
（1）画出句型的语法树；
（2）写出句型的全部短语、简单短语和句柄。
解：
（略）
2．设有文法G：
S→S+S|S*S|i|（S）。
（1）对于输入串i+i*i给出一个最左推导；
（2）该文法是否是二义性文法？
请证明你的结论。
解：
（1）i+i*i的最左推导：
S=>S+S=>i+S=>i+S*S=>i+i*S=>i+i*i
（2）该文法是二义性的。
因为对于句子i+i*i可以画出两棵语法树（语法树略）。
3．给出语言{ambmcn|m≥1,n≥0}的上下文无关文法（2型）。
解：
G:
S→AB|A
A→aAb|ab
B→cB|c
4．给出语言{akbmcn|k,m,n≥1}的正规文法（3型）。
解：
G:
A→aA|aB
B→bB|bC
C→cC|c
5．将文法G改写成等价的正规文法（3型）。
G:
S→dAB
A→aA|a
B→bB|b
解：
G:
S→dA
A→aA|aB
B→bB|b
6．构造一文法产生任意长的a，b串，使得
|a|≤|b|≤2|a|
其中，“|a|”和“|b|”分别表示串中的字符a和b的个数。
解：
b的个数在a的个数和其2倍之间，串的结构形如aSBS和BSaS，其中B为1或2个b。
故得文法
G:
S→aSBS|BSaS|ε
B→b|bb
7．设有字母表{a，b}上的正规式R=（ab|a）*。
（1）构造R的相应有限自动机；
解：
（2）构造R的相应确定有限自动机；
解：
将
（1）所得的非确定有限自动机确定化
ε
a
b
-0
1
1
3
12
2
1
+3
a
b
-+013
123
+123
123
13
+13
123
（3）构造R的相应最小确定有限自动机；
解：
对
（2）得到的DFA化简，合并状态0和2为状态2：
（4）构造与R等价的正规文法
解：
令状态1和2分别对应非终结符B和A
G:
A→aB|a|ε
B→aB|bA|a|b|ε
可化简为：
G:
A→aB|ε
B→aB|bA|ε
8．写出如图所示的自动机描述的语言的正规式
解：
abb*|abb*aa*b|aaa*b
9．写出在{a,b}上，不以a开头，但以aa结尾的字符串集合的正规式（并构造与之等价的最简DFA）。
解：
依题意，“不以a开头”，则必以b开头，又要“以aa结尾”，故正规式为：
b（a|b）*aa
（构造与之等价的最简DFA，此略）
10．写一个LL
（1）文法G，使其语言是
L（G）={ambnc2n|m>=0,n>0}
并证明文法是LL
（1）。
解：
文法G（S）：
SaS|E
EbE’
E’Ecc|cc
Select（SaS）∩Select（SE）=Ф
Select（E’Ecc）∩Select（E’cc）=Ф
故文法为LL
（1）的
11．将文法G改写成等价的LL
（1）文法，并构造预测分析表。
G：
S→S*aT|aT|*aT
T→+aT|+a
（编写递归下降子程序）
解：
消除左递归后的文法G’:
S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT|+a
提取左公因子得文法G’’:
S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT’
T’→T|ε
Select（S→aTS’）={a}
Select（S→*aTS’）={*}
Select（S→aTS’）∩Select（S→*aTS’）=Ф
Select（S’→*aTS’）={*}
Select（S’→ε）=Follow（s’）={#}
Select（S’→*aTS’）∩Select（S’→ε）=Ф
Select（T→+aT’）={+}
Select（T’→T）=First（T）={+}
Select（T’→ε）=Follow（T’）={*,#}
Select（T’→T）∩Select（T’→ε）=Ф
所以该文法是LL
（1）文法。
预测分析表：
*
+
a
#
S
S’Ta,N
→aTS’
S’
S’Ta,N
ε,P
T
T’a,N
T’
ε,P
T,P
ε,P
a
ε,N
#
OK
（递归下降子程序，略）
12．对文法G[S]:
S→aSb|P
P→bPc|bQc
Q→Qa|a
构造简单优先关系表。
该文法是否是简单优先文法？
解：
简单优先关系矩阵如下：
S
a
b
P
Q
c
S
=
a
=
<>
<
<
>
b
<
<>
=
=<
P
>
=
Q
=
=
c
>
>
由于矩阵中有元素存在多种优先关系，故不是简单优先文法。
13．考虑文法G:
S→AS|b
A→SA|a
（1）构造文法的可归前缀图（活前缀的DFA）；
（2）判断文法是否是LR（0）文法，并说明理由。
解：
（1）可归前缀图
（2）因为存在冲突，所以不是LR（0）文法。
14．文法G及其LR分析表如下，请给出对串dada#的分析过程。
G:
S→VdB①
V→e②
V→ε③
B→a④
B→Bda⑤
B→ε⑥
状态
ACTION
GOTO
d
e
a
#
S
B
V
0
r3
S3
1
2
1
acc
2
S4
3
r2
4
r6
S5
r6
6
5
r4
r4
6
S7
r1
7
S8
8
r5
r5
解：
对输入串dada#的分析过程
步骤
状态栈
符号栈
剩余输入符号
动作
1
2
3
4
5
6
7
8
9
0
02
024
0245
0246
02467
024678
0246
01
#
#V
#Vd
#Vda
#VdB
#VdBd
#VdBda
#VdB
#S
dada#
dada#
ada#
da#
da#
a#
#
#
#
用V→ε归约
移进
移进
用B→a归约
移进
移进
用B→Bda归约
用S→VdB归约
接受
15．对传值、传地址和传名3种参数传递方法分别写出下列程序的输出：
voidp（intx,inty,intz）{
y*=3;
z+=x;
}
voidmain（）{
inta=5,b=2;
p（a*b,a,a）;
printf（“%d\n”,a）;
}
这些参数传递机制如何实现？
解：
（1）传值5；
（2）传地址25；（3）传名45
（参数传递机制，略）
16．将下面程序划分为基本块，并画出其程序流图。
b:
=1
b:
=2
ifw<=xgotoL2
e:
=b
gotoL2
L1:
gotoL3
L2:
c:
=3
b:
=4
c:
=6
L3:
ify<=zgotoL4
halt
L4:
g:
=g+1
h:
=8
gotoL1
解：
（1）基本块：
（2）程序流图
b:
=1
b:
=2
ifw<=xgotoL2
（1）
e:
=b
gotoL2
（2）
L1:
gotoL3（3）
L2:
c:
=3
b:
=4
c:
=6（4）
L3:
ify<=zgotoL4（5）
halt（6）
L4:
g:
=g+1
h:
=8
gotoL1（7）
升级会员 