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

一、填空题|（每题 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 分)状态转换表：ab｛F}Φ{S｝{S｝｛S，A}Φ｛S，A｝{S,A｝｛S｝五。 构造识别正规语言 b＊a(bb*a）＊b＊ 最小的 DFA(要求写出求解过程）。（15 分）答:（1)对应的 NFA（5 分） (2）将（1）所得的 NFA 确定化：（5 分）ab｛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 分)firstfollowSa ^ （＃ ， ）Ta ^ （）T’, ε)七。 已知文法 G（S） :(1) S  SiA ｜ A(2) A  A+B | B（3） B  A＊ ｜ (试构造非终止符的 firstVT 和 lastVT 集合。（10 分）答：(10 分）firstVTlastVTSi , ...