编译原理考试陈火旺含答案Word文档格式.docx
《编译原理考试陈火旺含答案Word文档格式.docx》由会员分享，可在线阅读，更多相关《编译原理考试陈火旺含答案Word文档格式.docx（17页珍藏版）》请在冰点文库上搜索。
G（M）：
M→TB
T→Ba|ε
B→Db|eT|ε
D→d|ε
3.（4分）考虑下面的属性文法
产生式
语义规则
S→ABC
A→a
B→b
C→c
B.u:
=S.u
A.u:
=B.v+C.v
S.v:
=A.v
A.v:
=3*A.u
B.v:
=B.u
C.v:
=1
（1）画出字符串abc的语法树;
（2）对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少
（3）
4.（4分）运行时的DISPLAY表的内容是什么它的作用是什么
5.
6.（5分）对下列四元式序列生成目标代码：
A:
=B*C
D:
=E+A
G:
=B+C
H:
=G*D
其中，H在基本块出口之后是活跃变量，R0和R1是可用寄存器。
7.（5分）写出表达式a+b*（c-d）对应的逆波兰式、三元式序列和抽象语法树。
二、（8分）构造一个DFA，它接受∑={a，b}上所有包含ab的字符串。
三、（6分）写一个文法使其语言为L（G）={anbncm|m,n≥1，n为奇数，m为偶数}。
四、（8分）对于文法G（S）:
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
其语义解释为：
针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，将该语句翻译成四元式：
（1）写出适合语法制导翻译的产生式；
（2）写出每个产生式对应的语义动作。
七、（10分）将语句
whileC>
0doifA∨B=0thenC:
=C+DelseC:
=C*D
翻译成四元式。
八、（10分）设有基本块如下：
T1:
=3
T2:
=A*B
T3:
=9+T1
M:
T4:
=C-D
L:
=T3*T4
=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
r3
s3
1
2
acc
s4
3
r2
4
r6
S5
6
5
r4
s7
r1
7
S8
8
r5
（注：
答案格式为步骤状态符号输入串）
答：
（1）3
（2）16（3）16（每个值2分）
解答：
计算文法的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分）
（4）画出字符串abc的语法树;
（5）对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少。
（1）（2分）
（2）S.v的值为18（2分）
DISPLAY表是嵌套层次显示表。
每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层（主程序，0层）等每层过程的最新活动记录的起始地址。
通过DISPLAY表可以访问其外层过程的变量。
答:
目标代码序列
LDR0B
MULR0C
LDR1E
ADDR1R0
ADDR0C
MULR0R1
STR0H
逆波兰式：
（abcd-*+）（1分）
三元式序列:
（2分）
OPARG1ARG2
（1）-cd
（2）*b
（1）
（3）+a
（2）
抽象语法树：
（2分）构造相应的正规式：
（a|b）*ab（a|b）*
（3分）
aa
εεabεε
bb
（3分）确定化：
I
{0,1,2}
{1,2,3}
{1,2}
{1,2,4,5,6}
{1,2,3,5,6}
{1,2,5,6}
bb
ba
aaaa
abb
b
最小化：
{0，1，2}{3，4，5}
{0，2}，1，{3，4，5}
文法G（S）:
1.（4分）
2.（4分）
短语:
Ma），（Ma），b（Ma）b
直接短语:
Ma）
句柄:
（1）（4分）
（2）（4分）
^
（
）
>
<
=
（3）是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。
（1分）
（4）优先函数（3分）
F
G
（1）.适合语法制导翻译的文法（4分）
G（S）:
R→do
U→RS
（1）While
S→UE
（2）.（4分）
{R.QUAD:
=NXQ}
{U.QUAD:
=R.QUAD;
BACKPATCH（S.CHAIN,NXQ）}
{BACKPATCH（E.TC,U.QUAD）;
S.CHAIN:
=E.FC}
答案二：
（1）S→doM1S
（1）WhileM2E
M→ε（4分）
（2）M→ε{M.QUAD:
=NXQ}（4分）
S→doM1S
（1）WhileM2E
{
BACKPATCH（S
（1）.CHAIN,M2.QUAD）;
BACKPATCH（E.TC,M1.QUAD）;
=E.FC
}
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）
111（j，-，-，100）
112
3.画出DAG图；
4.设L，M，N是出基本块后的活跃变量，请给出优化后的四元式序列。
1.（6分）
L
*
T2,MT4T2,N
*-+
T1T3
3AB12CD
S1:
=12*S1
九、（8分）文法G（S）及其LR分析表如下，请给出串baba#的分析过程。
步骤状态符号输入串
00#baba#
102#Dbaba#
2024#Dbaba#
30245#Dbaba#
40246#DbBba#
502467#DbBba#
6024678#DbBba#
70246#DbB#
801#S#acc
升级会员 