编译原理期末考试习题及答案.doc

一、填空题|（每题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 à B B
（2) B à a B
（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 à not E then S1
其语义解释为：
针对自上而下的语法分析器，
（1） 分段产生式;（3分）
(2) 写出每个产生式对应的语义动作。(7分）
答：（1）分段产生式（3分）及语义动作(7分）
（1） R à not E then { Backpatch(＄2。FC ，nxq )；
$$。chain = $2。Tc }
(2） S à R S1 ｛ 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 à do S1 while E
其语义解释为:
针对自上而下的语法分析器，
(1） 分段产生式；(3分）
（2) 写出每个产生式对应的语义动作。（7分）
答：（1）分段产生式（3分）
G(S) ： （1) R à do
（2) U à R S1 while
（3) S à U E
(2） 产生式对应的语义动作(7分）
（1） R à do ｛ ＄＄。loop = nxq }
（2） U à R S1 while ｛ $$.loop = ＄1。loop ｝
（3) S à U E { backpatch(＄2.FC , ＄1。loop ）；
Backpatch($2。TC , nxq ） }
4