编译原理期末考试习题及答案_高等教育-试题.pdf

《编译原理期末考试习题及答案_高等教育-试题.pdf》由会员分享，可在线阅读，更多相关《编译原理期末考试习题及答案_高等教育-试题.pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、.c.一、填空题|（每题 4 分，共 20 分）1.乔母斯基定义的 3 型文法（线性文法）产生式形式 ABa|a,或 AaB|a，A，BVn,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）的最右推到并

2、画出语法树。（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 对应的两颗语法树为：.c.因此，文法是二义文法 四.给定正规文法 G（S）：(1)S Sa|Ab|b(2)A Sa 请构造与之等价的 DFA。（6 分）答：对应的 NFA 为：（6 分）状态转换表：a b F S S S

3、,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)单位型为的项目被称为移进项目型为的项目被称为待约项目在属性文法中文法符号的两种属性分别为继承

4、属性和综合属性运行时存贮管理方案有静态存储分配动态存储分配和堆式存储分配和方案二已知文法写出句型的最右推到并画的分答句子对应的两颗语法树为因此文法是二义文法四给定正规文法请构造与之等价的分答对应的为分状态转换表五构造识别正规语言最小的要求写出求解过程分答对应的分将所得的确定化分分六已知文法试消除文法的左递归分构合如表试给出该文法的项目集规范族划分填写相应的的分析表分答项目集规范族划分分分析表分状态九设某语言的语句的语法形式为其语义解释为针对自上而下的语法分析器分段产生式分写出每个产生式对应的语义动作分答分段产.c.(2)T ST|S(3)T ,ST|（4 分）（2）（6 分）first fol

5、low 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 i,+,*,(i,+,*,(A+,*,(+,*,(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 分)(2)SLR(1)分析表（7 分）状态 Ac

6、tion Goto a b#S B 0 S3 S4 1 2 1 Acc 2 S3 S4 5 3 S3 S4 6 4 R3 R3 R3 5 R1 I0 S.S S .BB B .aB B .b -I1-I2-I3-I4 S B a b I1 S S.I2 S B.B B .aB B .b -I5-I3-I4 B a b I3 B a.B B .aB B .b -I6-I3-I4 B a b I4 B b.I5 S BB.I6 B aB.Follow S#B a,b,#单位型为的项目被称为移进项目型为的项目被称为待约项目在属性文法中文法符号的两种属性分别为继承属性和综合属性运行时存贮管理方案有静态

7、存储分配动态存储分配和堆式存储分配和方案二已知文法写出句型的最右推到并画的分答句子对应的两颗语法树为因此文法是二义文法四给定正规文法请构造与之等价的分答对应的为分状态转换表五构造识别正规语言最小的要求写出求解过程分答对应的分将所得的确定化分分六已知文法试消除文法的左递归分构合如表试给出该文法的项目集规范族划分填写相应的的分析表分答项目集规范族划分分分析表分状态九设某语言的语句的语法形式为其语义解释为针对自上而下的语法分析器分段产生式分写出每个产生式对应的语义动作分答分段产.c.6 R2 R2 R2 九设某语言的 not-then-else 语句的语法形式为：S not E then S1 其语

8、义解释为：针对自上而下的语法分析器，(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）项目被称为 规

9、约 项目。4、写出 x:=b*(d-e)/(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 分）单位型为的项目被称为移进项目型为的项目被称为待约项目在属性文法中

10、文法符号的两种属性分别为继承属性和综合属性运行时存贮管理方案有静态存储分配动态存储分配和堆式存储分配和方案二已知文法写出句型的最右推到并画的分答句子对应的两颗语法树为因此文法是二义文法四给定正规文法请构造与之等价的分答对应的为分状态转换表五构造识别正规语言最小的要求写出求解过程分答对应的分将所得的确定化分分六已知文法试消除文法的左递归分构合如表试给出该文法的项目集规范族划分填写相应的的分析表分答项目集规范族划分分分析表分状态九设某语言的语句的语法形式为其语义解释为针对自上而下的语法分析器分段产生式分写出每个产生式对应的语义动作分答分段产.c.（3）（4 分）短语：（a,(a,a)），a,(a,

11、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 分）单位型为的项目被称为移进项目型为的项目被称为待约项目在属性文法中文法符号的两种属性分别为继承属性和综合属性运行时存贮管理方案有静态存储分配动态存储分配和堆式存储分配和方案二已知文法写出句型的最右推到并画的分答句子对应的两颗语法树为因此文法是二义文法四给定正规

12、文法请构造与之等价的分答对应的为分状态转换表五构造识别正规语言最小的要求写出求解过程分答对应的分将所得的确定化分分六已知文法试消除文法的左递归分构合如表试给出该文法的项目集规范族划分填写相应的的分析表分答项目集规范族划分分分析表分状态九设某语言的语句的语法形式为其语义解释为针对自上而下的语法分析器分段产生式分写出每个产生式对应的语义动作分答分段产.c.五.构造识别正规语言(ab*|a)*最小的 DFA（要求写出求解过程）。（15 分）答：（1）对应的 NFA （5 分）（2）将（1）所得的 NFA 确定化：（5 分）a b 1 1,2 1,2 1,2 1,2 （5 分）六.已知文法 G(S):

13、(1)S|a|(T)(2)T ST|S(3)T ,ST|试：求 first 和 follow集合，构造改文法的 LL（1）分析表。（10 分）答：文法相应的 first 和 follow 集合 （5 分）单位型为的项目被称为移进项目型为的项目被称为待约项目在属性文法中文法符号的两种属性分别为继承属性和综合属性运行时存贮管理方案有静态存储分配动态存储分配和堆式存储分配和方案二已知文法写出句型的最右推到并画的分答句子对应的两颗语法树为因此文法是二义文法四给定正规文法请构造与之等价的分答对应的为分状态转换表五构造识别正规语言最小的要求写出求解过程分答对应的分将所得的确定化分分六已知文法试消除文法的左

14、递归分构合如表试给出该文法的项目集规范族划分填写相应的的分析表分答项目集规范族划分分分析表分状态九设某语言的语句的语法形式为其语义解释为针对自上而下的语法分析器分段产生式分写出每个产生式对应的语义动作分答分段产.c.first follow S a (#,)T a ()T ,)其 LL（1）分析表如下：七.已知文法 G(S):(1)S SiA|A(2)A A+B|B(3)B A*|（非终止符的 firstVT 和 lastVT 集合如下:firstVT lastVT S i,+,*,(i,+,*,(A+,*,(+,*,(B*,(*,(试构造算符的优先关系表。（10 分）答：i+()*I ()八

15、已知文法 G(S):(1)S a|aAb|b|bBa(2)A 1A0|(3)B 1B0|求：该文法的 LR（0）项目集规范族。（15 分）答：单位型为的项目被称为移进项目型为的项目被称为待约项目在属性文法中文法符号的两种属性分别为继承属性和综合属性运行时存贮管理方案有静态存储分配动态存储分配和堆式存储分配和方案二已知文法写出句型的最右推到并画的分答句子对应的两颗语法树为因此文法是二义文法四给定正规文法请构造与之等价的分答对应的为分状态转换表五构造识别正规语言最小的要求写出求解过程分答对应的分将所得的确定化分分六已知文法试消除文法的左递归分构合如表试给出该文法的项目集规范族划分填写相应的的分析表

16、分答项目集规范族划分分分析表分状态九设某语言的语句的语法形式为其语义解释为针对自上而下的语法分析器分段产生式分写出每个产生式对应的语义动作分答分段产.c.九设某语言的 DO-while 语句的语法形式为：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

17、E backpatch（$2.FC，$1.loop）；Backpatch（$2.TC，nxq）单位型为的项目被称为移进项目型为的项目被称为待约项目在属性文法中文法符号的两种属性分别为继承属性和综合属性运行时存贮管理方案有静态存储分配动态存储分配和堆式存储分配和方案二已知文法写出句型的最右推到并画的分答句子对应的两颗语法树为因此文法是二义文法四给定正规文法请构造与之等价的分答对应的为分状态转换表五构造识别正规语言最小的要求写出求解过程分答对应的分将所得的确定化分分六已知文法试消除文法的左递归分构合如表试给出该文法的项目集规范族划分填写相应的的分析表分答项目集规范族划分分分析表分状态九设某语言的语句的语法形式为其语义解释为针对自上而下的语法分析器分段产生式分写出每个产生式对应的语义动作分答分段产