admin 管理员组文章数量: 1184232
2025年1月1日发(作者：writeprocessmemory被hook)
编译原理考试陈火旺（含答案）
编译原理试题 A (2003.12.4)
一、回答下列问题：(30 分)
1.(6分)对于下面程序段
programtest(input,output)
vari,j:integer;
procedureCAL(x,y:integer);
begin
y:=y*y;x:=x-y;y:=y-x
end;
begin
i:=2;j:=3;CAL(i,j)
writeln(j)
end.
若参数传递的方法分别为(1) 传值、(2) 传地址，(3)传名，请写出
程序执行的输出结果。
2.(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，
并判断该文
法是否是LL(1) 的，请说明理由。
G(M)：
M→TB
T→Ba|
B→Db|eT|
D→d|
3. (4分)考虑下面的属性文法
产生式语义规则
S→ABC B.u:=S.u
A.u:=
B.v+
C.v
S.v:=A.v
A→a A.v:=3*A.u
B→b B.v:=B.u
C→c C.v:=1
(1)画出字符串abc的语法树;
(2)对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v
的值为多少?
4.(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？
5.(5分)对下列四元式序列生成目标代码：
1
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。
6.(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽
象语法树。二、(8分)构造一个DFA，它接受={a，b}上所有包含ab的
字符串。
三、(6 分)写一个文法使其语言为L(G)={ a n b n c m|m,n≥1，n
为奇数，m为偶数}。
四、(8分)对于文法G(S):
S bMb
M(L|a
LMa）
1.写出句型b(Ma)b的最右推导并画出语法树。
2.写出上述句型的短语，直接短语和句柄。
五、(12 分)对文法G(S)：
S→a|^|(T)
T→T，S|S
(1)构造各非终结符的FIRSTVT和LASTVT集合;
(2)构造算符优先表;
(3)是算符优先文法吗?
(4)构造优先函数。
六、(8分)设某语言的do-while 语句的语法形式为
S doS (1)WhileE
其语义解释为：
S(1)的代码
真
E的代码假
2
针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，
将该语句翻译成四元式：
(1)写出适合语法制导翻译的产生式；
(2)写出每个产生式对应的语义动作。
七、(10 分)将语句
whileC>0doifA B=0thenC:=C+DelseC:=C*D
翻译成四元式。
八、(10 分)设有基本块如下：
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
1.画出DAG图；
2.设L，M，N是出基本块后的活跃变量，请给出优化后的四元式
序列。
九、(8 分)文法G(S)及其LR分析表如下，请给出串baba#的分析
过程。
(1)S→DbB (2)D →d (3)D →ε
(4)B→a (5)B →Bba (6)B →ε
LR分析表
ACTION GOTO
b D a # S B D
0 r3 s3 1 2
1 acc
2s4
3r2
4 r6 S
5 r
6 6
5 r4 r4
6 s
7 r1
7 S8
8 r5 r5
(注：答案格式为步骤状态符号输入串)
3
编译原理试题 A (2003.12.4)
一、回答下列问题：(30 分)
1.(6分)对于下面程序段
programtest(input,output)
vari,j:integer;
procedureCAL(x,y:integer);
begin
y:=y*y;x:=x-y;y:=y-x
end;
begin
i:=2;j:=3;CAL(i,j)
writeln(j)
end.
若参数传递的方法分别为(1)传值、(2)传地址，(3)传名，请写出
程序执行的输出结果。
答：(1)3 (2)16 (3)16 (每个值2分)
2.(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，
并判断该文法是否是LL(1)的，
请说明理由。
G(M)：
M→TB
T→Ba|
B→Db|eT|D→
d|
解答：
计算文法的FIRST和FOLLOW集合：(4分)
FIRST(M)={a ，b，e，d，} FIRST(T)={a ，b，e，d，}
FIRST(B)={b ，e，d，} FIRST(D)={d ，}
FOLLOW(M)={#} FOLLOW(T)={a ，b，e，d，#}
FOLLOW(B)={a ，#} FOLLOW(D)={b}
检查文法的所有产生式，我们可以得到：
4
1.该文法不含左递归，
2.该文法中每一个非终结符M，T，B，D的各个产生式的候选首
符集两两不相
交。
3.该文法的非终结符T、B和D，它们都有候选式，而且
FIRST(T)∩FOLLOW(T)={a ，b，e，d}≠
所以该文法不是LL(1) 文法。(2分)
3.(4分)考虑下面的属性文法
产生式语义规则
S→ABC B.u:=S.u
A.u:=
B.v+
C.v
S.v:=A.v
A→a A.v:=3*A.u
B→b B.v:=B.u
C→c C.v:=1
(3)画出字符串abc的语法树;
(4)对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v
的值为多少。
答：(1)(2 分)
S
A B C
a b c
(2)S.v 的值为18(2 分)
4.(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？
答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建
立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进
入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个
单元依次存放着现行层、直接外层、?、直至最外层(主程序，0层)等
每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外
层过程的变量。
5
5.(5分)对下列四元式序列生成目标代码：
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。
答: 目标代码序列
LD R0 B
MUL R0 C
LD R1 E
ADD R1 R0
LD R0 B
ADD R0 C
MUL R0 R1
ST R0 H
6.(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽
象语法树。答：逆波兰式：(abcd-*+)(1 分)
三元式序列:(2 分)
OPARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
抽象语法树：(2分)
+
*
-
a
b
c d
二、(8分)构造一个DFA，它接受={a，b}上所有包含ab的字符
串。
答：
6
(2分)构造相应的正规式：(a|b)*ab(a|b)*
(3分)
a a
0 1 2 3
a b
b b
(3分)确定化：
I I0
{0,1,2} {1,2,3}
{1,2,3} {1,2,3}
{1,2} {1,2,3} {1,2,4,5,6} {1,2,3,5,6}
{1,2,3,5,6} {1,2,3,5,6}
{1,2,5,6} {1,2,3,5,6}
b b
b a
a a a a
0 1 2
a b b
b
最小化：
{0，1，2}{3 ，4，5}
{0，2}，1，{3，4，5}
b a a
a b
0 1 3
4 5 6
I1
{1,2}
{1,2,4,5,6}
{1,2}
{1,2,5,6}
{1,2,4,5,6}
{1,2,5,6}
3 4 5
三、(6
b nnm
分)写一个文法使其语言为L(G)={abc|m,n≥1，n为奇数，m为偶
数}。
答：
文法G(S):
7
S AC
A aaAbb|ab
CccCcc|cc
四、(8分)对于文法G(S):
S bMb
M(L|a
LMa）
1.写出句型b(Ma)b的最右推导并画出语法树。
2.写出上述句型的短语，直接短语和句柄。答：
1.(4 分) S
S bMb b(Lb b(Ma)b
2.(4 分)
短语:Ma) ，(Ma) ，b(Ma)b 直接短语:Ma)
句柄:Ma) b M b
( TL
M a )
五、(12 分)对文法G(S)：
S→a|^|(T)
T→T，S|S
(1)构造各非终结符的FIRSTVT和LASTVT集合;
(2)构造算符优先表;
(3)是算符优先文法吗?
(4)构造优先函数。
答：
(1)(4 分)
FIRSTVT(S) {a,^,(}
FIRSTVT(T) {,,a,^,(}
LASTVT(S) {a,^,)}
LASTVT(T) {,,a,^,)}
(2)(4 分)
a ^ ( ) ,
8
a > >
^ > >
( < < < = <
) > >
, < < < > >
(3)是算符优先文法，因为任何两个终结符之间至多只有一种优先
关系。(1分)
(4)优先函数(3分)
a ^ ( ) ,
F 4 4 2 4 4
G 5 5 5 2 3
六、(8分)设某语言的do-while 语句的语法形式为
S doS (1)WhileE
其语义解释为：
S(1)的代码
真
E的代码
假
针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，
将该语句翻译成四元式：
(1)写出适合语法制导翻译的产生式；
(2)写出每个产生式对应的语义动作。答：
(1).适合语法制导翻译的文法(4分)
G(S):
R do
U RS(1)While
S UE
(2).(4 分)
R do
{:=NXQ }
9
U RS(1)While
{:=;BACKPATCH(
,NXQ)}
S UE
{BACKPATCH(,);:=
}
答案二：
(1)S doM 1 S(1)WhileM 2 E
M ε(4 分)
(2) M ε{:=NXQ} ( 4分)
S doM 1 S(1)WhileM 2 E
{
BACKPATCH(S(1).CHAIN,M );
BACKPATCH(,M );
:=
}
七、(10 分)将语句
whileC>0doifA B=0thenC:=C+DelseC:=C*D
翻译成四元式。
答：
100(j>，C，0，102)
101(j，-，-，112)
102(jnz，A，-，106)
103(j，-，-，104)
104(j=，B，0，106)
105(j，-，-，109)
106(+，C，D，T1)
107(:=，T1，-，C)
108(j，-，-，100)
109(*，C，D，T2)
110(:=，T2，-，C)
10
111(j，-，-，100)
112
八、(10 分)设有基本块如下：
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
3.画出DAG图；
4.设L，M，N是出基本块后的活跃变量，请给出优化后的四元式
序列。答：
1.(6 分)
L n9
*
T2,M n4T4 T2,N n8 n10
* - +
n1 n2 n3 n5 n6 n7
T1 T3
3 A B12 C D
2.(4
分)M:=A*BS1
:=C-
DL:=12*S1N:
=C+D
九、(8分)文法G(S)及其LR分析表如下，请给出串baba#的分析
过程。
(1)S →DbB (2)D →d (3)D →ε
(4)B →a (5)B →Bba (6)B →ε
LR分析表
11
ACTION GOTO
b D a # S B D
0r3 s3 1 2 1acc
2s4
3r2
4r6 S5 r6 6
5r4 r4
6s7 r1
7S8
8r5 r5
解答：
步骤状态符号输入串
0 0 # baba#
1 02 #D baba#
2 024 #Db aba#
3 0245 #Dba ba#
4 0246 #DbB ba#
5 02467 #DbBb a#
6 024678 #DbBba #
7 0246 #DbB #
8 01 #S # acc
12
版权声明：本文标题：编译原理考试陈火旺(含答案) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1735805045a1689884.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论