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

一、填空题|（每题4分，共20分）1。 乔母斯基定义的3型文法（线性文法）产生式形式 ABaa,或AaB|a，A，BVn,a，bVt .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) = (TF+i）（2) 语法树(2分）(3）（4分） 短语： (T*F+i) ，TF+i ,TF ， i 直接短语：T*F ， i 句柄:TF 三. 证明文法 G（S） : S SaS 是二义的。（6分）答:句子 aaa对应的两颗语法树为：因此，文法是二义文法四。给定正规文法G（S）： （1） S Sa | Ab b（2) A Sa 请构造与之等价的DFA。（6分）答：对应的NFA为： (6分)状态转换表：abFSSS，AS，AS,AS五。 构造识别正规语言ba(bb*a）b 最小的DFA(要求写出求解过程）。（15分）答:（1)对应的NFA（5分） (2）将（1）所得的NFA确定化：（5分）ab01，301,32，32,31,32,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 , + , ， ( i ， + , ， (A+ ， ， （+ , , (B , （* ， (FollowS#Ba,b,#八.已知文法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分)I0S .SS .BBB .aBB .b- I1- I2- I3- I4SBa bI1S S.I2S B.BB .aBB .b- I5- I3- I4Ba bI3B a.BB .aBB .b- I6- I3- I4Ba bI4B b.I5S BB.I6B aB. (2） SLR（1）分析表(7分）状态ActionGotoabSB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九设某语言的not-thenelse 语句的语法形式为：S not E then S1 其语义解释为：针对自上而下的语法分析器，（1） 分段产生式;（3分）(2) 写出每个产生式对应的语义动作。(7分）答：（1）分段产生式（3分）及语义动作(7分） （1） R not E then Backpatch(2。FC ，nxq )；$。chain = $2。Tc (2） S R S1 Backpatch（2.chain ， nxq )一、填空题（每题4分，共20分）1。 乔母斯基定义的2型文法(上下文无关文法）产生式形式 A，AVn, V+。2。词法分析程序的输入是 字符串 ，其输出是 单词符号 。3 算符有限分析方法每次都是对 最左素短语 进行规约。型为 B aB。 的LR（0)项目被称为 规约 项目.4、写出x：=b*(de)/(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分） （2）将（1)所得的NFA确定化：(5分）ab11，21，21，21，2 （5分)六. 已知文法G(S) ：(1) S | a | （T)(2） T ST | S（3) T ,ST |试：求first和follow集合，构造改文法的LL(1)分析表。（10分）答：文法相应的first 和 follow 集合 (5分)firstfollowSa ( ， ）Ta （)T， ）其LL(1）分析表如下:七. 已知文法G(S） ：（1） S SiA | A（2) A A+B B(3） B A* （非终止符的firstVT和lastVT集合如下：firstVTlastVTSi ， + ， ， （ i , + , , （A+ , * ， (+ ， * , (B ， (* ， (试构造算符的优先关系表.(10分）答：i+（)*I)八已知文法G（S) ：（1） S a aAb b | bBa(2) A 1A0 | (3） B 1B0 求 :该文法的LR(0）项目集规范族。（15分）答：九设某语言的DOwhile 语句的语法形式为: S do S1 while E 其语义解释为:针对自上而下的语法分析器，(1） 分段产生式；(3分）（2) 写出每个产生式对应的语义动作。（7分）答：（1）分段产生式（3分） G(S) ： （1) R do （2) U R S1 while （3) S U E(2） 产生式对应的语义动作(7分） （1） R do 。loop = nxq （2） U R S1 while $.loop = 1。loop （3) S U E backpatch(2.FC , 1。loop ）； Backpatch($2。TC , nxq ） 4