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

1 一、填空题|（每题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 对应的两颗语法树为： 因此，文法是二义文法 2 四.给定正规文法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 (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...