《2022年广工编译原理复习例题有客观题的答案 .pdf》由会员分享，可在线阅读，更多相关《2022年广工编译原理复习例题有客观题的答案 .pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学而不思则惘，思而不学则殆编译原理复习例题一选择题1编译的各阶段工作都涉及 B 。A词法分析 B表格管理 C语法分析 D语义分析2 D 型文法也称为正规文法。A 0 B 1 C2 D 3 3 D 文法不是LL(1)的。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 定义的语言是 C 。Aa2kbc|k0 Bakbc|k0 Ca2k-1bc|k0 Dakakbc|k0 6若 B为非终结符，则 A .B为 D 。A移进项目 B归约项目 C接受项目 D待约项目7同心集合并
2、可能会产生新的 D 冲突。 A二义 B移进 / 移进 C移进 / 归约 D归约 / 归约8代码优化时所依据的是 C 。A语法规则 B词法规则C等价变换规则 D语义规则9表达式 a-(-b)*c的逆波兰表示（ 为单目减）为 B 。Aa-bc* Babc*- Cab- Dabc-* 10 过程的 DISPLAY表是用于存取过程的 B 。A非局部变量 B嵌套层次 C返回地址 D入口地址11. 已知右图所示自动机M ，请问下列哪个字符串不是M所能识别的。D A bbaa B abba C abab D aabb 12.若状态 k 含有项目“ A . ” ，且仅当输入符号aFOLLOW(A) 时，才用规
3、则“A ”归约的语法分析方法是 D 。A LALR分析法 B LR(0)分析法C LR(1)分析法D SLR(1)分析法b 0 1 - a a 2 + + b a b 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 12 页学而不思则惘，思而不学则殆13.有一语法制导翻译如下所示: （第 8 章） S-bAb print “ 1” A-(B print “ 2” A-a print “ 3” B-Aa) print “ 4” 若输入序列为b(aa)a)a)b,则采用自下而上的分析方法, 则输出是 B 。A 32224441 B 3424
4、2421 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 P(E)|i，句型 T+T*F+i的句柄是T。3 最右推导的逆过程称为最左规约， 也称为规范规约。4符号表的信息栏中登记了每个名字的有关属性，如符号名、符号的类型、符号的存储类别和符号的作用域及可视性等。5. 一个确定有穷自动机由五部分组成：有穷状态
5、集、 有穷字母表、转换函数、初态和终态集。6. 最常用的两类语法分析方法是自顶向下和自底向上分析法。7. 单词的三种描述工具：正规文法、正规式和有穷自动机互相之间具有等价性。8.在 PL/0 的目标代码解释执行时， 寄存器 B 总是指向当前执行过程活动记录的起始地址，而寄存器 T 总是指向栈顶。9LR(0) 分析法的名字中 ” L” 表示自左向右扫描输入符号串，” R” 表示最右推导的逆过程， “0”表示向前看的输入符号的个数。10. 两种常用的动态存储分配办法是栈式动态分配和堆式动态分配。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共
6、 12 页学而不思则惘，思而不学则殆三判断题（认为正确的填 “ T” ，错的填 “ F” ）【 T 】1同心集的合并有可能产生“归约/ 归约”冲突。【 T 】2一个文法所有句子的集合构成该文法定义的语言。【 F 】3非终结符可以有综合属性，但不能有继承属性。【 T 】4逆波兰表示法表示表达式时无需使用括号。【 F 】5一个确定有穷自动机有且只有一个终态。【 F 】6若过程p 第 k 次被调用，则p 的 DISPLAY 表中就有k+1 个元素。四解答题1给定文法G和句型 (T+F)*i+T, G: E E+T |T TT*F|F F(E)|i （ 1）画出句型的语法树；（ 2）写出句型的全部短语
7、、简单短语和句柄。解： （略）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 Aa Ab|ab B cB|c 4给出语言 akbmcn|k,m,n1 的正规文法（ 3 型） 。解： G: A aA|aB B bB|bC C c
8、C|c 5将文法G改写成等价的正规文法（3 型） 。 G: S dAB A aA|a B bB|b 解： G: S dA A aA|aB 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 12 页学而不思则惘，思而不学则殆B bB|b 6设有字母表a ，b 上的正规式R=(ab|a)*。（1）构造 R 的相应有限自动机；解：（2）构造 R 的相应确定有限自动机；解： 将（ 1）所得的非确定有限自动机确定化Ia Ib -+013 123 +123 123 13 +13 123 （3）构造 R 的相应最小确定有限自动机；解： 对（ 2）得到的
9、 DFA 化简，合并状态0 和 2 为状态 2：（4）构造与R 等价的正规文法解：令状态 1 和 2 分别对应非终结符B 和 A G: A aB|a| BaB|bA|a|b|可化简为：G: A aB| BaB|bA|1 2 a a b -+0 1 2 a a b a-+0 1 2 3 b a a -+精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 12 页学而不思则惘，思而不学则殆7已知正规文法GS: S aS | bA | a A aS （1）构造与之等价的自动机NFA M （2）将 NFA M 确定化为DFA M I Ia Ib -
10、0 S SZ A +1 SZ SZ A 2 A S 8.有穷自动机M接受字母表0,1上所有满足下述条件的串：串中至少包含两个连续的 0 或两个连续的1。请写出与M等价的正规式。解： (0|1)*(00|11)(0|1)* 9对右图所示的有限自动机（1）若是确定的，则写出其转换矩阵；若不是，则将其确定化；（2）最小化。（注：确定化和最小化均应给出转换矩阵和图示）。解：（1）符号状态a b -1 2 3 2 1 4 +3 2 5 +4 1 6 5 5 5 6 6 6 S Z A a b a a 0 2 1 a a b b a 1 5 2 3 6 4 a a b a a b b b a a 精选学习
11、资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 12 页学而不思则惘，思而不学则殆（2）首先将状态按终态和非终态分成两个集合1,2,5,6和3,4 检查子集 1,2,5,6，由于f(1,a)=2， f(2,a)=1，f(5,a)=4，f(6,a)=3，所以子集 1,2,5,6可进一步划分为1,2和5,6 检查子集 3,4，由于 f(3,a)=2，f(4,a)=1以及 f(3,b)=5，f(4,b)=6，所以不用进一步划分了。检查子集 1,2，由于 f(1,a)=2，f(2,a)=2以及 f(1,b)=3，f(2,b)=4，所以不用进一步划分了。
12、检查子集 5,6，由于f(5,a)=4，f(6,a)=3以及 f(5,b)= ， f(6,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 结尾” ，故正规式为： b(a|b)*aa （构造与之等价的最简DFA，此略）11 写一个 LL(1)文法 G，使
13、其语言是L(G)= ambnc2n | m=0,n0 并证明文法是LL(1)。解： 文法 G（S） ：S aS | E E bEE Ecc | cc Select(S aS) Select (S E)= Select(E Ecc)Select (Ecc) = 故文法为LL(1)的12 将文法 G 改写成等价的LL(1)文法，并构造预测分析表。 G ：SS*aT|aT|*aT T+a T|+a （编写递归下降子程序）解： 消除左递归后的文法G : S aTS |*aTSS *aTS | T +aT|+a 提取左公因子得文法G :S aTS |*aTSS *aTS | T+aT 精选学习资料 -
14、- - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 12 页学而不思则惘，思而不学则殆T T| Select(S aTS )=a Select(S *aTS )=* Select(S aTS ) Select(S*aTS )= Select(S *aTS )=* Select(S )=Follow(s )=# Select(S *aTS ) Select(S )= Select(T +aT )=+ Select(T T)=First(T) =+ Select(T )=Follow(T )=*,# Select(T T) Select(T )= 所以该文法是L
15、L(1)文法。预测分析表：* + a # S S Ta, N TS T, N SS Ta, N , P T T a, N T , P T, P , P a , N # OK （递归下降子程序，略）13 对文法 GS: S aSb | PP bPc | bQcQ Qa | a构造简单优先关系表。该文法是否是简单优先文法？解： 简单优先关系矩阵如下：S a b P Q c S = a = b = = = Q = = c 由于矩阵中有元素存在多种优先关系，故不是简单优先文法。14 考虑文法 G: SAS |b A SA |a （1）构造文法的可归前缀图（活前缀的DFA） ；（2）判断文法是否是LR(
16、0)文法，并说明理由。解： （1）可归前缀图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 12 页学而不思则惘，思而不学则殆I0:S.S S.AS S.b A.SA A.aI1:SS. AS.A A.SA A.a S.AS S.b I2:Aa. I3:Sb. I4:SA.S S.AS S.b A.SA A.a I5:AS.A A.SA A.a S.AS S.b I6:SAS. AS.A A.SA A.a S.AS S.b I7:ASA. SA.S S.AS S.b A.SA A.aSbSaAabAAabSabS AbaASSAba（2
17、）因为存在冲突，所以不是LR(0)文法。15 已知文法GS ： S Uta | Tb T S | Sc | d U US | e (1) 试判断 G是 LR(0)，SLR(1)，LALR(1)还是 LR(1)，说明理由。(2) 构造相应的分析表。解：(1) 首先拓广文法为G ，增加产生式S S( 0) S S (1)SUTa (2) STb (3) TS (4) T Sc (5) Td (6) UUS (7) U eG 的 LR(0)项目集族及识别活前缀的DFA 如下图所示：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 12 页学而不
18、思则惘，思而不学则殆（2）在 I1 中：S S. 为接受项目， T S. 为归约项目， T S.c 为移进项目，存在接受- 归约和移进- 归约冲突，因此所给文法不是LR(0)文法。在 I1中：Follow(S) Follow(T)= # a ，b=Follow(T) c= a ，b c=在 I8中：Follow(U) Follow(T) c=d,e a ，b c=所以在 I1 中的接受 - 归约和移进 - 归约冲突与I8 中的移进 - 归约和归约 - 归约冲突可以由 Follow集解决，所以G是 SLR(1)文法。构造的 SLR(1)分析表如下：状态（ State）ActionGotoabcd
19、e#SUT0 1 2 3 4 5 6 7 8 9 10 S5S4 r3r3S6Acc S5S4 S9.r7r7 r5r5.r4r4.S10S9.r3r3.S6r6r6.r2r2.r2r2r2r2 r1r1.r1r1r1r1123 .827 16 文法 G及其 LR 分析表如下，请给出对串dada# 的分析过程。G: S VdB V e V B a B Bda B 状态ACTION GOTO d e a # S B V 0 r3 S3 1 2 1 acc 2 S4 3 r2 4 r6 S5 r6 6 5 r4 r4 6 S7 r1 精选学习资料 - - - - - - - - - 名师归纳总结
20、- - - - - - -第 9 页，共 12 页学而不思则惘，思而不学则殆7 S8 8 r5 r5 解： 对输入串 dada# 的分析过程步骤状态栈符号栈剩余输入符号动作1 2 3 4 5 6 7 8 9 0 02 024 0245 0246 02467 024678 0246 01 # #V #Vd #Vda #VdB #VdBd #VdBda #VdB #S dada# dada# ada# da# da# a# # # # 用 V 归约移进移进用 B a归约移进移进用 B Bda 归约用 S VdB 归约接受17 对以下文法，请写出关于配对括号数目ps 的属性文法。文法规则语义规则S(
21、T) Si TT,S TS 解： h 表示配对括号数目（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： x2 翻译成四元式序列。解：略19 对传值、传地址和传名3 种参数传递方法分别写出下列程序的输出：void p( int x, int y, int z) y *= 3; z += x; void main() int a=5, b=2; p(a*b,a,a); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - -
22、 - - -第 10 页，共 12 页学而不思则惘，思而不学则殆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 if w =
23、 x goto L2 （1）e := b goto L2 （2）L1: goto L3 （3）L2: c := 3 b := 4 c := 6 （ 4）L3: if y = z goto L4 （5）halt （6）L4: g := g + 1 h := 8 goto L1 （7）21 对 PL/0语言 If ELSE 子句填空 : := IF THEN ELSE 注： FOR语句和 WHILE 语言的填空请在空缺处填空，完成条件语句的编译算法：switch (SYM) 1 4 2 3 7 6 5 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1
24、1 页，共 12 页学而不思则惘，思而不学则殆case IFSYM: ; CONDITION(SymSetUnion(SymSetNew(THENSYM),FSYS),LEV,TX); if (SYM=THENSYM) GetSym(); else Error(16); CX1=CX; GEN(JPC,0,0); STATEMENT(SymSetUnion(SymSetNew(ELSESYM),FSYS),LEV,TX); CX2=CX; GEN(JMP,0,0); ; If( ) GetSym(); STATEMENT(FSYS,LEV,TX); ; break; 解：(1) getSym() (2) CodeCX1.A=CX (3) SYM=ELSESYM (4) CodeCX2.A=CX 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 12 页