2022年编译原理期末考试习题及答案 .pdf-得力文库

资源描述

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

1、1 一、填空题 | （每题 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

2、+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 对应的两颗语法树为：因此，文法是二义文法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

3、 - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 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

5、ow 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

6、（1）的分析表。（15 分）答：（1）LR （0）项目集规范族划分 (8 分) (2) SLR(1)分析表（ 7 分）状态Action 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 6 R2 R2 R2 I0S .S S .BB B .aB B .b- I1- I2- I3- I4S B a bI1S S. I2S B.B B .aB B .b- I5- I3- I4B a bI3B a.B B .aB B .b- I6- I3- I4B a bI4B b. I5S BB. I6B aB. Follo

7、w S # B a,b,# 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 4 九设某语言的not-then-else 语句的语法形式为： S not E then S1 其语义解释为：针对自上而下的语法分析器，(1) 分段产生式；（3 分）(2) 写出每个产生式对应的语义动作。（7 分）答：（1）分段产生式（ 3分）及语义动作 (7 分) (1) R not E then Backpatch（$2.FC ，nxq ）; $

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

9、| (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 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - -

10、- - - 5 （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分）名师资料总

11、结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 6 （2）将（ 1）所得的 NFA确定化：（5 分）a b 1 1,2 1,2 1,2 1,2 （5 分）六. 已知文法G(S) :(1) S | a | (T) (2) T ST | S (3) T ,ST | 试：求 first和 follow集合，构造改文法的LL（1）分析表。（10 分）答：文法相应的first 和 follow 集合（5 分）first follow S a (

12、# , ) T a ( ) T, ) 其 LL（1）分析表如下：七. 已知文法G(S) : 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 7 (1) S SiA | A (2) A A+B | B (3) B A* | （非终止符的 firstVT和 lastVT 集合如下 : firstVT lastVT S i , + , * , ( i , + , * , ( A + , * , ( + , * , ( B * , (

13、* , ( 试构造算符的优先关系表。（10 分）答：i + ( ) * I ( ) 八已知文法G(S) : (1) S a | aAb | b | bBa (2) A 1A0 | (3) B 1B0 | 求：该文法的 LR（0）项目集规范族。（15 分）答：九设某语言的DO-while 语句的语法形式为： S do S1 while E 其语义解释为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 8 针对自上而下的语法分析

14、器，(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 ）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -

展开阅读全文