编译原理期末考试习题集与答案解析

1、、填空题| (每题4分，共20分)1 .乔母斯基定义的3型文法(线性文法)产生式形式 A Ba|a,或A aB|a,A, BNn, a,bt 。2 .语法分析程序的输入是 单词符号,其输出是 语法单位o3型为 B .aB的LR (0)项目被称为 移进 项目，型为B a.B的LR (0) 项目被称为待约 项目，4 .在属性文法中文法符号的两种属性分别为继承属性和综合属性 。5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。二.已知文法G(S) ET | E+T(2) TF | F*F(3) F(E) | i(1)写出句型(T*F+i)的最右推到并画出语法树。(4分)(2)写

2、出上述句型的短语，直接短语和句柄。(4分)答：(1)最右推到(2分)E = T = F = (E) = (E+T) = (E+F) = (E+i) = (T+i) = (T*F+i)(2)语法树(2分)/|ViX(3) (4 分)短语： (T*F+i), T*F+i , T*F , i直接短语：T*F , i句柄：T*F3 .证明文法 G(S) : S SaS | e是二义的。(6分)答：句子 aaa对应的两颗语法树为：因此，文法是二义文法4 .给定正规文法G (S):(1) SSa | Ab |b(2) ASa请构造与之等价的DFA。(6分)答：对应的NFA为：(6分)FSSS，AS，AS，

3、AS五.构造识别正规语言b*a（bb*a）*b*最小的DFA （要求写出求解过程）。（15分）答：（1）对应的NFA （5分）(5分)（2）将（1）所得的NFA确定化：（5分）ab01, 301,32, 32,31,32,3六.已知文法G(S): S 人 I a I (T)(2) T T,S | S试：（1）消除文法的左递归；（4分）(2)构造相应的first和follow 集合。(6分)答：(1)消除文法的左递归后文法 G (S)为： S 人 I a I (T)(2) T ST | S(3) T ,ST | (4 分)七.已知文法G(S):(1) S SiA | A AA+B|B BA*|

4、(试构造非终止符的firstVT和lastVT集合。(10分)firstVTlastVTSi , + , * ,(i , + , * ,(A+ , * ,(+ , * ,(B* ,(* ,(答：(10分)八.已知文法 G(S):FollowS# 1Ba,b,#(1) S B BB a BB b的follow集合如表: 试：(1)给出该文法的LR (0)项目集规范族划分;(2)填写相应的SLR (1)的分析表。(15分)I 1I 2I 3I 4I 1S S.I4B b.I 3Ba.B-B.aB-B.b-答：(1) LR (0)项目集规范族划分(8分)S B.B - I 5 a ,B.aB - b

5、 I 3I 5S BB.B.b- I 4I 6B aB.(2) SLR(1)分析表(7分)状态ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九.设某语言的not-then-else 语句的语法形式为：S not E then Si其语义解释为：针对自上而下的语法分析器，(1)分段产生式；(3分)(2)写出每个产生式对应的语义动作。(7分)答：(1)分段产生式(3分)及语义动作(7分)1 1) R not E then Backpatch ($2.FC , nxq );$.chain = $2.Tc 2 2) S R Si Back

6、patch ($2.chain , nxq ) 一、填空题| (每题4分，共20分)3 .乔母斯基定义的2型文法(上下文无关文法)产生式形式A &ANn, B V+。4 .词法分析程序的输入是 字符串,其输出是 单词符号。3算符有限分析方法每次都是对 最左素短语进行规约。型为 B aB.的LR (0) 项目被称为规约 项目。4、写出 x:=b*(d-e)/(c-d)+e 的逆波兰式 xbde-*cd-/e+:=。5、常用的两种动态存贮分配办法是栈式存储分配和堆式存储 分配。二.已知文法 G(S): S 人 I a I (T)(2) T T,S | S试：(1)写出句型(a,(a,a)的最左推到

7、并画出语法树。(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分)/l(I ) /l T ， S /l (T ) A /l T ， SS aIa(3) (4 分)短语：(a,(a,a), a,(a,a) , (a,a) , a,a , a直接短语：a句柄：a.证明文法 G(S) : S aSb | Sb | b 是二义的。(6分)答：句子aabbbb对应的两颗语法树为:

8、四.给定正规文法G (S):(1) SaA(2) AaB | bA(3) B aA | b请构造与之等价的DFA。（6分）五.构造识别正规语言（ab*|a）*最小的DFA （要求写出求解过程）。（15分）答：（1）对应的NFA （5分）ab11,21,21,21,2（2）将（1）所得的NFA确定化：（5分）a(5分)六.已知文法 G(S): S 人 I a I (T)(2) T ST | ST,ST |e试：求first和follow集合，构造改文法的LL (1)分析表。(10分)答：文法相应的first和follow集合 (5分)firstfollowSa A (# ,)Ta a ()T，,

9、 )其LL (1)分析表如下:ab(sS-CT)TT- STI ST*Tf 5丁rT-它V七.已知文法G(S):(1) S SiA | A AA+B|B BA*| (非终止符的firstVT和lastVT集合如下:firstVTlastVTSi , + , * ,(i , + , * ,(A+ , * ,(+ , * ,(B* ,(* ,(试构造算符的优先关系表。(10分)i+()*I()八已知文法 G(S): S a | aAb | b | bBa A1A0| B1B0| 求：该文法的LR(0)项目集规范族。(15分)L： SI： SF-S-/Io： S5SS fitAS-a AbA IAOaAbSt bBaB?B 5 1BOM SrbBaa I|0： SbBa九.设某语百的DO-while语句的语法形式为:S do Si while E其语义解释为:针对自上而下的语法分析器,(1)分段产生式；(3分) (2)写出每个产生式对应的语义动作。(7分)答：(1)分段产生式(3分)G(S) :(1)Rdo(2) UR S