一、填空题|（每题 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 , ...
