编译原理试题
1、回答下列问题：(30分)
1.(6分)对于下面程序段
program  test (input, output)
var  i, j: integer;
procedure  CAL(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分)
考虑下面的属性文法
B→b        C→c                B.v := B.u                C.v := 1
(1)画出字符串abc 的语法树;
(2)对于该语法树，假设S.u 的初始值为5，属性计算完成后，S.v 的值为多少?
4.(4分)运行时的DISPLAY 表的内容是什么？它的作用是什么？
5. (5分)对下列四元式序列生成目标代码：
A:=B*C D:=E+A G:=B+C H:=G*D
其中，H 在基本块出口之后是活跃变量， R0和R1是可用寄存器。
6.(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。
2、(8分)构造一个DFA ，它接受={a ，b}上所有包含ab 的字符串。
3、 (6分)写一个文法使其语言为L(G)={a n b n c m | m,n≥1，n 为奇数，m 为偶
数}。
4、(8分)对于文法G(S):）
Ma  L a |(L  M bMb  S →→→1. 写出句型b(Ma)b 的最右推导并画出语法树。2. 写出上述句型的短语，直接短语和句柄。
5、(12分)对文法G(S)：
S → a | ^ | (T)T → T ，S | S
(1) 构造各非终结符的FIRSTVT 和LASTVT 集合;(2) 构造算符优先表;(3) 是算符优先文法吗?(4) 构造优先函数。
6、(8分)设某语言的do-while 语句的语法形式为    S → do  S (1)  While  E
其语义解释为：
针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，将该语句翻译成四元式：
(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作。
7、(10分)将语句
while C>0 do if A ∨ B=0 then C:=C+D else C:=C*D 翻译成四元式。
8、(10分)设有基本块如下：T1:=3T2:=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 是出基本块后的活跃变量，请给出优化后的四元式序列。
9、(8分)文法G(S)及其LR分析表如下，请给出串baba#的分析过程。
(1) S → DbB(2) D → d(3) D → ε
(4) B → a(5) B → Bba(6) B → ε
(注：答案格式为  步骤状态符号输入串)
编译原理试题答案
1、回答下列问题：(30分)
1.(6分)对于下面程序段
program  test (input, output)
var  i, j: integer;
procedure  CAL(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}
检查文法的所有产生式，我们可以得到：
1. 该文法不含左递归，
2. 该文法中每一个非终结符M，T，B，D的各个产生式的候选首符集两两不相交。
3. 该文法的非终结符T、B和D，它们都有 候选式，而且
FIRST(T)∩FOLLOW(T)={ a，b，e，d }≠
所以该文法不是LL(1)文法。(2分)
画出while语句的流程图
3.(4分)
考虑下面的属性文法
(3)画出字符串abc的语法树;
(4)对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为
多少。
答：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。