桂林电子科技大学试卷
20122013学年第2学期课号适用班级（或年级、专业）01应本姓名七10八15九10十成绩100课程名称编译原理试题、答案和评分标准（A卷闭卷）考试时间120分钟题号满分得分评卷人一20二8班级三6四6五15学号六10
一、填空题（每题4分，共20分）1乔母斯基定义的3型文法（线性文法）产生式形式ABaa或AaBa，A，B∈V
ab∈Vt。2语法分析程序的输入是单词符号，其输出是语法单位。3型为BaB的LR（0）项目被称为移进项目，型为BaB的LR（0）项目被称为待约项目，4在属性文法中文法符号的两种属性分别为继承属性和综合属性。5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。二已知文法GS1ETET2TFFF3F（E）i（1）写出句型（TFi）的最右推到并画出语法树。（4分）（2）写出上述句型的短语，直接短语和句柄。（4分）
答：（1）最右推到（2分）ETFEETEFEiTiTFi2语法树（2分）
（3）（4分）短语：（TFi），TFi，TF，i
直接短语：TF，i句柄：TF
1
f三证明文法GS：SSaSε答：句子aaa对应的两颗语法树为：
是二义的。（6分）
因此，文法是二义文法四给定正规文法G（S）：1SSaAbb2ASa请构造与之等价的DFA。（6分）答：对应的NFA为：（6分）
状态转换表：FSSAaΦSASAbSΦS
五构造识别正规语言babbab最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分）
（2）将（1）所得的NFA确定化：（5分）ab01，3013Φ2，3231323
2
f（5分）六已知文法GS1SaT2TTSS试：（1）消除文法的左递归；（4分）（2）构造相应的first和follow集合。（6分）答：（1）消除文法的左递归后文法G’（S）为：1SaT2TST’S3T’ST’ε（4分）（2）（6分）firstfollowSaTaT’ε七已知文法GS1SSiAA2AABB3BA（试构造非终止符的firstVT和lastVT集合。（10分）答：（10分）firstVTlastVTSiiAB八已知文法GS1SBBS2BaBB3Bb的follow集合如表：试：（1）给出该文法的LR（0）项目集规范族划分；（2）填写相应的SLR（1）的分析表。（15分）答：（1）LR（0）项目集规范族划分8分I0S’SSBBBr