编译原理期末考试习题及答案.doc
《编译原理期末考试习题及答案.doc》由会员分享，可在线阅读，更多相关《编译原理期末考试习题及答案.doc（8页珍藏版）》请在冰点文库上搜索。
一、填空题|（每题4分，共20分）
1.乔母斯基定义的3型文法（线性文法）产生式形式AàBa|a,或AàaB|a，A，B∈Vn,a,b∈Vt。
2.语法分析程序的输入是单词符号，其输出是语法单位。
3型为Bà.aB的LR（0）项目被称为移进项目，型为Bàa.B的LR（0）项目被称为待约项目，
4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。
5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。
二.已知文法G（S）
（1）EàT|E+T
（2）TàF|F*F
（3）Fà（E）|i
（1）写出句型（T*F+i）的最右推到并画出语法树。
（4分）
（2）写出上述句型的短语，直接短语和句柄。
（4分）
答：
（1）最右推到（2分）
E==>T==>F==>（E）==>（E+T）==>（E+F）==>（E+i）==>（T+i）==>（T*F+i）
（2）语法树（2分）
（3）（4分）
短语：
（T*F+i），T*F+i，T*F，i
直接短语：
T*F，i
句柄：
T*F
三.证明文法G（S）：
SàSaS|ε是二义的。
（6分）
答：
句子aaa对应的两颗语法树为：
因此，文法是二义文法
四.给定正规文法G（S）：
（1）SàSa|Ab|b
（2）AàSa
请构造与之等价的DFA。
（6分）
答：
对应的NFA为：
（6分）
状态转换表：
a
b
{F}
Φ
{S}
{S}
{S,A}
Φ
{S,A}
{S,A}
{S}
五.构造识别正规语言b*a（bb*a）*b*最小的DFA（要求写出求解过程）。
（15分）
答：
（1）对应的NFA（5分）
（2）将
（1）所得的NFA确定化：
（5分）
a
b
{0}
{1，3}
{0}
{1,3}
Φ
{2，3}
{2,3}
{1,3}
{2,3}
（5分）
六.已知文法 G（S）:
（1）Sà^|a|（T）
（2）TàT,S|S
试：
（1）消除文法的左递归；（4分）
（2）构造相应的first和follow集合。
（6分）
答：
（1）消除文法的左递归后文法G’（S）为：
（1）Sà^|a|（T）
（2）TàST’|S
（3）T’à,ST’|ε（4分）
（2）（6分）
first
follow
S
a^（
#,）
T
a^（
）
T’
ε
）
七.已知文法 G（S）:
（1）SàSiA|A
（2）AàA+B|B
（3）BàA*|（
试构造非终止符的firstVT和lastVT集合。
（10分）
答：
（10分）
firstVT
lastVT
S
i,+,*,（
i,+,*,（
A
+,*,（
+,*,（
B
*,（
*,（
Follow
S
#
B
a,b,#
八.已知文法 G（S）:
（1）SàBB
（2）BàaB
（3）Bàb
的follow集合如表：
试：
（1）给出该文法的LR（0）项目集规范族划分；
（2）填写相应的SLR
（1）的分析表。
（15分）
答：
（1）LR（0）项目集规范族划分（8分）
I0
S’à.S
Sà.BB
Bà.aB
Bà.b
---àI1
---àI2
--àI3
--àI4
S
B
a
b
I1
S’àS.
I2
SàB.B
Bà.aB
Bà.b
---àI5
--àI3
--àI4
B
a
b
I3
Bàa.B
Bà.aB
Bà.b
---àI6
--àI3
--àI4
B
a
b
I4
Bàb.
I5
SàBB.
I6
BàaB.
（2）SLR
（1）分析表（7分）
状态
Action
Goto
a
b
#
S
B
0
S3
S4
1
2
1
Acc
2
S3
S4
5
3
S3
S4
6
4
R3
R3
R3
5
R1
6
R2
R2
R2
九．设某语言的not-then-else语句的语法形式为：
SànotEthenS1
其语义解释为：
针对自上而下的语法分析器，
（1）分段产生式；（3分）
（2）写出每个产生式对应的语义动作。
（7分）
答：
（1）分段产生式（3分）及语义动作（7分）
（1）RànotEthen{Backpatch（$2.FC，nxq）;
$$.chain=$2.Tc}
（2）SàRS1{Backpatch（$2.chain，nxq）}
一、填空题|（每题4分，共20分）
1.乔母斯基定义的2型文法（上下文无关文法）产生式形式Aàβ,A∈Vn,β∈V+。
2.词法分析程序的输入是字符串，其输出是单词符号。
3算符有限分析方法每次都是对最左素短语进行规约。
型为BàaB.的LR（0）项目被称为规约项目。
4、写出x:
=b*（d-e）/（c-d）+e的逆波兰式__xbde-*cd-/e+:
=__。
5、常用的两种动态存贮分配办法是__栈式存储分配和堆式存储__分配。
二．已知文法 G（S）:
（1）Sà^|a|（T）
（2）TàT,S|S
试：
（1）写出句型（a,（a,a））的最左推到并画出语法树。
（4分）
（2）写出上述句子的短语，直接短语和句柄。
（4分）
答：
（1）最左推到（2分）
S==>（T）==>（T,S）==>（S,S）==>（a,S）==>（a,（T））==>（a,（T,S））==>（a,（S,S））==>（a,（a,S））==>（a,（a,a））
（2）语法树（2分）
（3）（4分）
短语：
（a,（a,a）），a,（a,a），（a,a），a,a,a
直接短语：
a
句柄：
a
三．证明文法G（S）：
SàaSb|Sb|b是二义的。
（6分）
答：
句子aabbbb对应的两颗语法树为：
因此，文法是二义文法
四.给定正规文法G（S）：
（1）SàaA
（2）AàaB|bA
（3）BàaA|b
请构造与之等价的DFA。
（6分）
答：
对应的DFA为：
（6分）
五.构造识别正规语言（ab*|a）*最小的DFA（要求写出求解过程）。
（15分）
答：
（1）对应的NFA（5分）
（2）将
（1）所得的NFA确定化：
（5分）
a
b
{1}
{1,2}
Φ
{1,2}
{1,2}
{1,2}
（5分）
六.已知文法 G（S）:
（1）Sà^|a|（T）
（2）TàST’|S
（3）T’à,ST’|ε
试：
求first和follow集合，构造改文法的LL
（1）分析表。
（10分）
答：
文法相应的first和follow集合（5分）
first
follow
S
a^（
#,）
T
a^（
）
T’
ε
）
其LL
（1）分析表如下：
七.已知文法 G（S）:
（1）SàSiA|A
（2）AàA+B|B
（3）BàA*|（
非终止符的firstVT和lastVT集合如下:
firstVT
lastVT
S
i,+,*,（
i,+,*,（
A
+,*,（
+,*,（
B
*,（
*,（
试构造算符的优先关系表。
（10分）
答：
i
+
（
）
*
I
>
<
<
<
+
>
>
<
<
>
（
>
>
>
）
<
<
<
*
>
>
>
八已知文法 G（S）:
（1）Sàa|aAb|b|bBa
（2）Aà1A0|ε
（3）Bà1B0|ε
求：
该文法的LR（0）项目集规范族。
（15分）
答：
九．设某语言的DO-while语句的语法形式为：
SàdoS1whileE
其语义解释为：
针对自上而下的语法分析器，
（1）分段产生式；（3分）
（2）写出每个产生式对应的语义动作。
（7分）
答：
（1）分段产生式（3分）
G（S）:
（1）Ràdo
（2）UàRS1while
（3）SàUE
（2）产生式对应的语义动作（7分）
（1）Ràdo{$$.loop=nxq}
（2）UàRS1while{$$.loop=$1.loop}
（3）SàUE{backpatch（$2.FC，$1.loop）；
Backpatch（$2.TC，nxq）}
8
升级会员 