2022年广工编译原理复习例题有客观题的答案.docx

《2022年广工编译原理复习例题有客观题的答案.docx》由会员分享，可在线阅读，更多相关《2022年广工编译原理复习例题有客观题的答案.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆编译原理复习例题一 挑选题1编译的各阶段工作都涉及 B ；A 词法分析 B 表格治理 C 语法分析 D 语义分析2 D 型文法也称为正规文法；A 0 B 1 C 2 D 3 3 D 文法不是 LL1 的；A 递归 B 右递归 C2 型 D 含有公共左因子的4文法 EE+E|E*E|i 的句子 i*i+i*i 有 C 棵不同的语法树；A 1 B 3 C 5 D 7 5文法 S aaS|abc Aa 2k bc|k0 Ca 2k-1 bc|k0 定义的语言是 C ；待约项目归约 / 归约；Bakbc|k0 Dakakbc|

2、k0 6如 B为非终结符,就 A .B为 D ；A移进项目 B归约项目 C接受项目 D7同心集合并可能会产生新的 D 冲突； A二义 B移进 / 移进 C移进 / 归约 D8代码优化时所依据的是 C ；A语法规章 B词法规章C等价变换规章 D语义规章9表达式 a-b*c的逆波兰表示（ 为单目减）为 B Aa-bc* Babc*- Cab- Dabc-* 名师归纳总结 10 过程的 DISPLAY表是用于存取过程的 B ；+ 第 1 页,共 12 页A非局部变量 B嵌套层次 C返回地址 D入口地址11. 已知右图所示自动机M,请问以下哪个字符串不是M所能识别的； D - a 1 a A bbaa

3、 B abba C abab D aabb a b 0 b b 2 + 12.如状态 k 含有项目“A . ”,且仅当输入符号aFOLLOWA 时,才用规章“A ”归约的语法分析方法是 D ；A LALR分析法 B LR0分析法C LR1分析法D SLR1分析法- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆13.有一语法制导翻译如下所示: （第 8 章） S-bAb print “ 1” , 就输出是 B ； A-B print “ 2 ” A-a print “ 3” B-Aa print “ 4” 如输入序列为baaaab,就采纳自下

4、而上的分析方法A 32224441 B 34242421 C 12424243 D 34442212 14. 局部优化是对 D 进行的优化；A 表达式 B 部分代码C 循环体 D 基本块15. 削减运算强度是对 D 的一种优化；A 表达式 B 过程 C 基本块 D 循环二 填空题1词法分析阶段的任务式从左到右扫描 源程序,从而逐个识别 单词；2对于文法 GE ：ET|E+T TF|T*F FPF|P PE|i,句型 T+T*F+i 的句柄是 T；3最右推导的逆过程称为 最左规约,也称为 规范规约；4符号表的信息栏中登记了每个名字的有关属性,如 符号名、符号的类型、符号的储备类别 和 符号的作用

5、域及可视性 等；5. 一个确定有穷自动机由五部分组成：有穷状态集、 有穷字母表、 转换函数、初态 和 终态集；6. 最常用的两类语法分析方法是 自顶向下 和 自底向上 分析法；7. 单词的三种描述工具：正规文法、正规式 和 有穷自动机 相互之间具有等价性；8. 在 PL/0 的目标代码说明执行时, 寄存器 B 总是指向当前执行过程活动记录的 起始地址,而寄存器 T 总是指向 栈顶；9LR0 分析法的名字中 ” L” 表示 自左向右扫描输入符号串,” R” 表示 最右推导的逆过程,“ 0” 表示 向前看的输入符号的个数；10. 两种常用的动态储备安排方法是 栈式 动态安排和 堆式 动态分配；名师

6、归纳总结 - - - - - - -第 2 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆三 判定题（认为正确的填 “ T” ,错的填 “ F” ）【 T 】1 同心集的合并有可能产生“ 归约 / 归约” 冲突；【 T 】2 一个文法全部句子的集合构成该文法定义的语言；【 F 】3 非终结符可以有综合属性,但不能有继承属性；【 T 】4 逆波兰表示法表示表达式时无需使用括号；【 F 】5 一个确定有穷自动机有且只有一个终态；【 F 】6 如过程 p 第 k 次被调用,就 p 的 DISPLAY 表中就有 k+1 个元素；四 解答题1给定文法 G 和

7、句型 T+F*i+T, G: E E+T | T TT*F | F FE | i （ 1）画出句型的语法树；（ 2）写出句型的全部短语、简洁短语和句柄；解：（略）2设有文法 G：SS+S|S*S|i|S；（ 1）对于输入串 i+i*i 给出一个最左推导；（ 2）该文法是否是二义性文法？请证明你的结论；解：（1）i+i*i 的最左推导：S = S+S = i+S = i+S*S = i+i*S = i+i*i （2）该文法是二义性的；由于对于句子i+i*i可以画出两棵语法树（语法树略） ；3给出语言 ambmcn |m1,n 0的上下文无关文法（2 型）；解：G: S AB|A AaAb|ab

8、BcB|c 4给出语言 akbmcn |k,m,n1 的正规文法（ 3 型）；解： G: AaA|aB BbB|bC CcC|c 5将文法 G 改写成等价的正规文法（3 型）； G: SdAB AaA|a BbB|b 解： G: SdA AaA|aB 名师归纳总结 - - - - - - -第 3 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆BbB|b 6设有字母表 a ,b 上的正规式R=ab|a*；（1 ）构造 R 的相应有限自动机；解：2 -a 1 b +0 3 a （2 ）构造 R 的相应确定有限自动机；解： 将（ 1）所得的非确定有限自

9、动机确定化-+013 Ia Ib 123 +123 123 13 +13 123 -+ab 2 +a 0 1 +a （3 ）构造 R 的相应最小确定有限自动机；解： 对（ 2）得到的 DFA 化简,合并状态 0 和 2 为状态 2：2 -+b a 1 +a （4 ）构造与 R 等价的正规文法解：令状态 1 和 2 分别对应非终结符 B 和 A G: A aB|a| BaB|bA|a|b| 可化简为：G: A aB| 名师归纳总结 BaB|bA|第 4 页,共 12 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆7已知正规文法GS: S

10、aS | bA | a A aS （1 ）构造与之等价的自动机b NFA M Z a a S A a （2 ）将 NFA M 确定化为 DFA M -0 I S Ia Ib SZ A +1 SZ SZ A 2 A S a a 0 a 1 b 2 b 8. 有穷自动机 M 接受字母表0,1 上全部满意下述条件的串：串中至少包含两个连续的 0 或两个连续的 1 ；请写出与 M 等价的正规式；解： 0|1*00|110|1* 9对右图所示的有限自动机a b b 5 a 3 1 （1）如是确定的,就写出其转换矩阵；如不是,就将其b b a a a 确定化；a 6 （2 ）最小化；2 4 （注：确定化和

11、最小化均应给出转换矩阵和图示）；解：（1 ）名师归纳总结 状态符号a b 第 5 页,共 12 页-1 2 3 2 1 4 +3 2 5 +4 1 6 5 5 5 6 6 6 - - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆（2 ）第一将状态按终态和非终态分成两个集合1,2,5,6和3,4 检查子集 1,2,5,6,由于f1,a=2, f2,a=1,f5,a=4,f6,a=3,所以子集 1,2,5,6可进一步划分为1,2和5,6 ,f4,b=6,所以检查子集 3,4,由于 f3,a=2,f4,a=1以及 f3,b=5不用进一步划分了；检查子

12、集 1,2,由于 f1,a=2,f2,a=2以及 f1,b=3,f2,b=4,所以不用进一步划分了；检查子集 5,6,由于 f5,a=4,f6,a=3以及 f5,b= , f6,b= ,所以不需要进一步划分了；因此最终划分的结果是 1,2、3,4 和5,6,重新命名状态, 令1,2 为 1 ,3,4为 3 和5,6 为 5,就得到化简后的 DFA 为符号a b 状态-1 1 3 +3 1 5 5 5 5 10 写出在 a,b 上,不以 a 开头,但以 aa 结尾的字符串集合的正规式（并构造与之等价的最简 DFA）；解：依题意,“ 不以 a 开头” ,就必以 b 开头,又要“ 以 aa 结尾”

13、,故正规式为： ba|b*aa （构造与之等价的最简 DFA,此略）11 写一个 LL1 文法 G,使其语言是LG= a mb nc 2n | m=0,n0 并证明文法是 LL1；解： 文法 G（S）：S aS | E E bEE Ecc | cc SelectS aSSelect S E= SelectE EccSelect Ecc = 故文法为 LL1 的12 将文法 G 改写成等价的 LL1 文法,并构造猜测分析表； G ：SS*aT|aT|*aT T+aT|+a （编写递归下降子程序）解： 排除左递归后的文法G : S aTS |*aTSS *aTS | T +aT|+a 提取左公因子

14、得文法G :S aTS |*aTSS *aTS | T+aT 名师归纳总结 - - - - - - -第 6 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆T T| SelectS aTS =a SelectS *aTS =* SelectS aTS SelectS*aTS = SelectS *aTS =* SelectS =Follows =# SelectS *aTS SelectS = SelectT +aT =+ SelectT T=FirstT =+ SelectT =FollowT =*,# SelectT T SelectT = 所

15、以该文法是 LL1 文法；猜测分析表：S * + a # S Ta, N TS T, N SS Ta, N T a, N , N , P T , P , P TT, P a # OK （递归下降子程序,略）13 对文法 GS: S aSb | PP bPc | bQcQ Qa | a构造简洁优先关系表；该文法是否是简洁优先文法？解： 简洁优先关系矩阵如下：S a b P Q c S = a = b = = = Q = = c 由于矩阵中有元素存在 多种优先关系 ,故不是简洁优先文法；14 考虑文法 G: S AS | b A SA | a （1）构造文法的可归前缀图（活前缀的 DFA）；（2）

16、判定文法是否是 LR0 文法,并说明理由；解：（1）可归前缀图名师归纳总结 - - - - - - -第 7 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆I1:SS. I5:AS.A AS.A .SA SbAa.SA bSAI7:ASA. AAA.a A.a S.AS S.AS bS.b SS.b aAI0:S.S aI2:Aa. SA.S S.AS I3:Sb. abaS.AS S.b bS.b A.SA A.SA SA.aA.aabI6:SAS. ASI4:SA.S AAS.A AS.AS SA.SA S.b A.a A.SA S.AS （2

17、 ）由于存在冲突,所以不是A.a S.b LR0文法；15 已知文法 GS ： S Uta | Tb T S | Sc | d U US | e 1 试判定 G 是 LR0,SLR1,LALR1仍是 LR1,说明理由；2 构造相应的分析表；解：名师归纳总结 1 第一拓广文法为G ,增加产生式S SS 第 8 页,共 12 页 0 S S 1SUTa 2 STb 3 T4 T Sc 5 Td 6 UUS 7 U eG 的 LR0项目集族及识别活前缀的DFA 如下图所示：- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆（2 ）在 I1 中：S

18、S. 为接受项目, T S. 为归约项目, T S.c 为移进项目,存在接受- 归约和移进- 归约冲突,因此所给文法不是 LR0 文法；在 I1 中：FollowS FollowT= # a ,b=FollowT c= a ,b c=在 I8 中：FollowU FollowT c=d,e a ,b c=所以在 I1 中的接受 - 归约和移进 - 归约冲突与I8 中的移进 - 归约和归约 - 归约冲突可以由 Follow集解决,所以G 是 SLR1文法；SGotoT构造的 SLR1分析表如下：状态（ State）Actionabcde#U0 S5S4 123 1 r3r3S6Acc 8.7 2

19、 S5S4 23 S9.4 r7r7 5 r5r5.6 r4r4.7 S10S9.8 r3r3.S6r6r6.9 r2r2.r2r2r2r2 10 r1r1.r1r1r1r116 文法 G 及其 LR 分析表如下,请给出对串dada# 的分析过程；名师归纳总结 状态G: S VdB S GOTO V 第 9 页,共 12 页V e V B a B Bda B ACTION d e a # B 0 r3 S3 acc 1 6 2 1 S4 2 3 r2 r6 4 r6 S5 5 r4 r4 6 S7 r1 - - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,

20、思而不学就殆7 S8 8 r5 r5 解： 对输入串 dada# 的分析过程步骤 状态栈 符号栈 剩余输入符号 动作1 0 # dada# 用 V 归约2 02 #V dada# 移进3 024 #Vd ada# 移进4 0245 #Vda da# 用 B a 归约5 0246 #VdB da# 移进6 02467 #VdBd a# 移进7 024678 #VdBda # 用 B Bda 归约8 0246 #VdB # 用 S VdB 归约9 01 #S # 接受17 对以下文法,请写出关于配对括号数目 ps 的属性文法；文法规章 语 义 规 就ST Si TT,S TS 解： h 表示配对括

21、号数目（1） S.h = T.h + 1 （2 ）S.h = 0 （3） T.h = T .h+S.h （4）T.h = S.h 18 把以下语句if x0 and y0 then z： x y else x： x 2 翻译成四元式序列；解：略19 对传值、传地址和传名3 种参数传递方法分别写出以下程序的输出：void p int x, int y, int z y *= 3; z += x; void main int a=5, b=2; pa*b,a,a; 名师归纳总结 - - - - - - -第 10 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而

22、不学就殆printf“ %dn” , a;这些参数传递机制如何实现？解：（1）传值 5 ；（2）传地址 25 ；（3）传名 45 （参数传递机制,略）20 将下面程序划分为基本块,并画出其程序流图；b := 1 b := 2 if w = x goto L2 e := b goto L2 L1:goto L3 L2:c := 3 b := 4 c := 6 L3:if y = z goto L4 halt L4:g := g + 1 h := 8 goto L1 解：（1）基本块：（2）程序流图 b := 1 b := 2 （1）1 4 if w = x goto L2 e := b （2）2

23、 5 goto L2 L1: goto L3 （3）L2: c := 3 b := 4 c := 6 （ 4）6 7 L3: if y = z goto L4 （5）3 halt （6）L4: g := g + 1 h := 8 goto L1 （7）21 对 PL/0 语言 If ELSE 子句填空 : := IF THEN ELSE 注： FOR 语句和 WHILE 语言的填空请在空缺处填空,完成条件语句的编译算法：名师归纳总结 switch SYM 第 11 页,共 12 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆 case

24、IFSYM: ; CONDITIONSymSetUnionSymSetNewTHENSYM,FSYS,LEV,TX; if SYM=THENSYM GetSym; else Error16; CX1=CX; GENJPC,0,0; STATEMENTSymSetUnionSymSetNewELSESYM,FSYS,LEV,TX; CX2=CX; GENJMP,0,0; ; If GetSym; STATEMENTFSYS,LEV,TX; ; break ; 解：1 getSym 2 CodeCX1.A=CX 3 SYM=ELSESYM 4 CodeCX2.A=CX 名师归纳总结 - - - - - - -第 12 页,共 12 页