《编译原理期末试题及答案》由会员分享，可在线阅读，更多相关《编译原理期末试题及答案（13页珍藏版）》请在金锄头文库上搜索。
1、第 1 页共 6 页1、 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 2、写出表达式 ab*(c-d)/e 的逆波兰式和三元序列。 3、写出表达式 a:=(b+c)*e+(b+c)/f 的逆波兰式和三元序列。 4、已知文法 G(S)及相应翻译方案SaAb print “1” Sa print “2” AAS print “3” Ac print “4” 输入 acab, 输出是什么？ 5、 已知文法 G(S)SbAa A(B | a BAa)写出句子 b(aa)b 的规范归约过程。 6、已知文法 GSSS*aF | aF | *aF F+aF | +a 消
2、除文法左递归。 1 1、设文法 G(S):S | a | (T)TT,S | S 消除左递归； 构造相应的 FIRST 和 FOLLOW 集合； 构造预测分析表 2.语句 if E then S(1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 4.设某语言的 for 语句的形式为 for i:E(1) to E(2) do S 其语义解释为 i:E(1) LIMIT:E(2) again: if iLIMIT thenBegin S; i:i1goto again End; （1）写出适合语法制导翻译的产生式； （2）写出每个产生式对应的语义动作。 7.已知文法
3、G(S)Sa | | (T) TT,S | S (1) 给出句子(a,(a,a)的最左推导； (2) 给出句型(T,S),a)的短语, 直接短语，句柄。 8.对于 C 语言 do S while E 语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。第 2 页共 6 页9.已知文法 G(S)SaAcBeAAb| bBd(1)给出句子 abbcde 的最左推导及画出语法树；(2)给出句型 aAbcde 的短语、素短语。 10.设文法 G(S): S(T) | aS | aTT,S | S消除左递归和提公共左因子；构造相应的 FIRST 和 FOLLOW 集合；构造预测分
4、析表。 12.已知文法 G(S)EE+T | TTT*F| FF(E)| i(1) 给出句型 (i+i)*i+i 的最左推导及画出语法树；(2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。 答案： (1)消除左递，文法变为 GS：S | a | (T) TST | S T,ST | 此文法无左公共左因子。 (2)构造相应的 FIRST 和 FOLLOW 集合： FIRST(S)=a, , (， FOLLOW(S)=#, , ) FIRST(T)=a, , ( ，FOLLOW(T)= FIRST(T)=, ，FOLLOW(F)=) (3)构造预测分析表：a(),#SSaSS(T)
5、TTSTTSTTSTTTT,ST2. (1) Cif E then SCS(1)(2)Cif E then BACK(E.TC, NXQ); C.chain:=E.FCSCS(1) S.chain:=MERG(C.Chain, S(1). Chain) 4. (1) Ffor i:=E(1) to E(2) doSFS(1) (2) Ffor i:=E(1) to E(2) do GEN(:=, E(1).place, _, entry(i); F.place:=entry(i); LIMIT:=Newtemp; GEN(:=, E(2).place, _, LIMIT); Q:=NXQ;第
6、3 页共 6 页F.QUAD:=q; GEN(j, entry(i), LIMIT, q+2) F.chain:=NXQ; GEN(j, _, _, 0) SFS(1) BACKPATCH(S(1).chain, NXQ);GEN(+, F.place, 1, F.place);GEN(j, _, _, F.QUAD);S.chain:=F.chain 7. 最左推导S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a) 短语(T,S),a)(T,S),a(T,S)T,Sa 直接短语T,Sa 句柄T,S 9.(1)
7、S=aAcBe=AAbcBe=abbcBe=abbcde (2) 短语: aAbcde, Ab, d素短语: Ab, d10.(1) S (L) | aSSS |LSLL,SL | (2) FIRST(S)=a, ( FIRST(S)=a, (, FIRST(L)=a, ( FIRST(L)=, FOLLOW(S)=, ), # FOLLOW(S)=, ), # FOLLOW(L)= ) FOLLOW(L)= ) (3)( ) a , #SS (L)S aS SSSSSSSS LLSLLSLL,SLLL12.(1) E=E+T=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T
8、=(T+T)*F+T =(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T=(i+i)*i+F=(i+i)*i+i (2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F素短语 i, E+T 最左素短语 E+T第 4 页共 6 页编译原理期末试题（二）对于函数 f2，由于局部变量 x 的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。 6、正规式 ba(bba) b体现的特点是，每个 a 的左边都有若干 b，除非 a 是第一个字母。该正规式定义的语言是：至少含一个 a，但不含子串 aa 的所有 a 和
9、 b 的串集。最简 DFA 如下：7、 消除左递归后的文法：B 1 B B 0 B | 1 B | 相应的翻译方案如下：B 1 B.i := 1 BB.val := B.val B 0 B1.i := B.i 2 B1 B.val := B1.val | 1 B1.i := B.i 2 +1 B1 B.val := B1.val | B.val := B.i编译原理期末试题（三）2、写出表达式 a=b*c+b*d 对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:= 3、对于文法 G(S): ）Ma La|(L MbMb S答：1） bMabLbbbMbS)(2） 短
10、语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma)三、设有字母表a，b上的正规式 R=(ab|a)*。 解：（1）0123baa-+（2）将（1）所得的非确定有限自动机确定化ab-01131221+3start2abb10abSbM(TMabL)第 5 页共 6 页012aaba-+（3）对（2）得到的 DFA 化简，合并状态 0 和 2 为状态 2：12aab-+（4）令状态 1 和 2 分别对应非终结符 B 和 A G: AaB|a|； BaB|bA|a|b|；可化简为：G: AaB|；BaB|bA|四、设将文法 G 改写成等价的 LL(1)文法，并构造预测分析表
11、。 G：SS*aT|aT|*aT； T+aT|+a解：消除左递归后的文法 G: SaTS|*aTSS*aTS| T+aT|+a 提取左公因子得文法 G :SaTS|*aTS S*aTS| T+aT TT| Select(SaTS)=a Select(S*aTS)=* Select(SaTS)Select(S*aTS)= Select(S*aTS)=* Select(S)=Follow(s)=# Select(S*aTS)Select(S)= Select(T+aT)=+ Select(TT)=First(T) =+ Select(T )=Follow(T)=*,# Select(TT)Sele
12、ct(T)= 所以该文法是 LL(1)文法。 预测分析表： *+a#S*aTSaTS S*aTS T+aT T T ab-+013123+12312313+13123第 6 页共 6 页6 6 设文法 G 为： SA；ABA|；BaB|b 解：（1）拓广文法 G：(0) SS (1) SA (2) ABA(3) A(4) BaB (5) Bb ； FIRST(A) = , a, b；FIRST(B) = a, b 构造的DFA 如下:项目集规范族看出，不存在冲突动作。该文法是LR(1)文法。 （2）LR(1)分析表如下：(3)输入串 abab 的分析过程为：五、对文法 G(S)：S a | |
13、 (T)；T T，S | S答：答：(1) ),)(),)(,)(,)(aTLASTVTaSLASTVTaTFIRSTVTaSFIRSTVT第 7 页共 6 页(2) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。 （2 分） (3) 给出输入串(a,a)#的算符优先分析过程。步骤 栈当前输入字符 剩余输入串动作1#(a,a#, 归约4#(N,a)#() 归约7#(N,N）#,) 归约8#(N)#(=) 移进9#(N)# )# 归约10#N#接受五、设有文法 GA：ABCc | gDB BbCDE | CDaB | ca DdD | EgAf | c (1) 计算该文法的每一个非
14、终结符的 FIRST 集和 FOLLOW 集； (2) 试判断该文法是否为 LL（1）文法。 （15）FIRSTFOLLOWA B C D EA,b,c,d,g b A,c,d D C,gA,c,d C,d,g A,b,c,g是 LL（1）文法。 2对于文法 GS：SAB，AAa|bB，Ba|Sb 求句型 baSb 的全部短语、直接短语和句柄？ 句型 baSb 的语法树如图五(2)所示。解：baSb 为句型 baSb 的相对于 S 的短语，ba 为句型 baSb 的相对于 A 的短语，Sb 为句型 baSb 的相对于 B 的短语， 且为直接短语，a 为句型 baSb 的相对于 B 的短语，且为直接短语和句柄。3设有非确定的有自限动机 NFA M=(A，B，C，0，1，A，C)，其中：a(),#a(,#
