编译原理试卷1

《编译原理试卷1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、广东商学院试题纸2007—2008学年第_二_学期考试时间共120分钟042511021课程名称编译原理（A卷）课程代码110164课程班号042511022共4页一、判断题（30分）1、乔姆斯基把文法分成4种类型：0型也叫短语文法；1型也叫上下文有关文法；2型也叫上下文无关文法；3型也叫正则文法。2、自上而下分析方法一般需要消除左递归）和回溯）。3、一般而言，编译器的分析部分包括词法分析，语法分析，语义分析而综合部分包扌舌中间代码生成，代码优化，代码生成o以上六个阶段都涉及到（符号表管理和出错管理。4、任何NFA都存在一个与之等价的DFA。二、简答题（2

2、0分）三、设计题（20分）1、解释器和编译器有哪些区别？编译器将高级语言源程序翻译为与之等价的目标程序而后就隐退，在随后的任意时刻，用户都可以通过操作系统运行该目标程序。编译器完全控制编译过程，而目标程序在执行中完全控制自己的活动。解释器是在应用程序整个执行期间，解释器都控制着程序的运行过程。从效果上看，解释器实现了一台虚拟机的功能，一次对入或多多少的语句，然后，按照它们规定的方式执行相关的动作。现代语言的实现多采用这二者的混合方式。2、下而的文法是否是左递归的？如果是，该如何消除?E->E+T

3、TT-*T*F

4、FF-(E)

5、id解答：ET存在左递归，可以

6、用以下等价文法消除左递归E—TE'E'f+TE'

7、eT—FT，T'f*FT'

8、eF->（E）

9、id3、设有文法G[S]：S->S*S

10、S+S

11、（S）

12、a,该文法是否有二义性？为什么？2（30）解答：有.该文法存在句子a*a+a该句子存在两颗不同的语法树，如图:四、设计题(20分)1、构造一个DFA,它接受E={0,l}上0和1的个数都是偶数的字符串。五、综合题(30分)1、构造下面文法的LL(1)分析表。S-^aBcIbABA—^aAb

13、bB-b

14、£构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子。解：First(S)={a,b}Firs

15、t(A)=(a,b}First(B)={b,£}Follow(B)={c,$}abc$sS—aBcS—bABAA-^aAbA—bBB—b分析符号串baabbb的过程步骤符号栈输入串规则1$Sbaabbb$S—bAB2$BAbbaabbb$3$BAaabbb$A-^aAb4$BbAaaabbb$5$BbAabbb$A-^aAb6$BbbAaabbb$7$BbbAbbb$A—b8$Bbbbbbb$9$Bbbbb$10$Bbb$11$B$B—e12$$Acc2、设有文法G（S）：S-CCC-cCC-*d求1）拓广文法，2）文法的转移图，3）构造规范LR语法分析表

16、,4）构造LALR语法分析表。解答:1）拓广文法S，一SSfcc(1)CfcC⑵C-*d⑶3)文法的规范LR语法分析表状态ACTIONGOTOCd$Sc0s3s4121acc2s6s753s3s484r3r35rl6s6s797r38r2r29r24)LALR语法分析表状态ACTIONGOTOcd$SC0s36s47121acc2s36s47536s36s478947r3r3r35rl89r2r2r2