编译原理期末考试习题及答案
- 格式：pdf
- 大小：406.57 KB
- 文档页数：9
编译原理期末考试习题及答案
⼀、填空题|（每题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分）
五. 构造识别正规语⾔b*a(bb*a)*b* 最⼩的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分）
（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分）
七. 已知⽂法 G(S) :(1) S → SiA | A
(2) A → A+B | B
(3) B → A* | （
试构造⾮终⽌符的firstVT 和lastVT 集合。（10分）
⼋.已知⽂法 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分)
I 0 S ’→ .S S → .BB B → .aB B → .b ---→ I 1 ---→ I 2 --→ I 3 --→ I 4 S B a b I 1 S ’→ S. I 2 S → B.B B → .aB B → .b ---→ I 5 --→ I 3 --→ I 4 B a b I 3 B → a.B B → .aB B → .b ---→ I 6 --→ I 3 --→ I 4 B a b I 4 B → b. I 5 S → BB. I 6 B → aB.
九．设某语⾔的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 }
{ Backpatch（$2.chain ， nxq ）}
(2) S → R S
1
⼀、填空题|（每题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分）
（5分）
六. 已知⽂法G(S) :(1) S → ^ | a | (T)
(2) T → ST’ | S
(3) T’→ ,ST’ |ε
试：求first和follow集合，构造改⽂法的LL（1）分析表。（10分）
集合（5分）
七. 已知⽂法G(S) :(1) S → SiA | A
(2) A → A+B | B
(3) B → A* | （:
⼋已知⽂法G(S) :(1) S → a | aAb | b | bBa
(2) A → 1A0 | ε
(3) B → 1B0 | ε
求：该⽂法的LR（0）项⽬集规范族。（15分）答：
九．设某语⾔的DO-while 语句的语法形式为： S → do Swhile E
1其语义解释为：
针对⾃上⽽下的语法分析器，(1) 分段产⽣式；（3分）
(2) 写出每个产⽣式对应的语义动作。（7分）
答：（1）分段产⽣式（3分）G(S) : (1) R → do
while
(2) U → R S
1
(3) S → U E
(2) 产⽣式对应的语义动作(7分)(1) R → do { $$.loop = nxq }
(2) U → R S
while { $$.loop = $1.loop }
1
(3) S → U E { backpatch（$2.FC ， $1.loop ）；
Backpatch（$2.TC ， nxq ） }
