张淑艳+编译原理试题及答案.doc

《张淑艳+编译原理试题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、郑州大学软件技术学院《编译原理》课程2010-2011学年第二学期期末试题（A）卷题号一二三四总分分数（适用专业：08级所有专业考试时间：120分钟）合分人：复查人：一、选择题：（每空2分，共20分）（说明：将答案写在试卷后面的答题纸上）分数评卷人1、乔母斯基将文法分为四种类型，即0型、1型、2型和3型，上下文无关文法是_________。(A)0型文法(B)1型文法(C)2型文法(D)3型文法2、在上下文无关文法中，语言是__________的集合。(A)产生式(B)字符串(C)句子(D)句型3、一个确定有限自动机M是一个五元式M=(S,∑,δ,s0,F)，其中，S

2、表示状态集，∑表示______，δ表示_______，s0表示唯一的初态，F表示________。(A)字符串(B)从S×∑至S的映射(C)开始符号(D)有穷字母表(E)终态集(F)产生式集合4、下列表示含奇数个1的二进制串的正规式为_________。(A)10*(10*10*)*(B)0*10*(10*10*)*(C)1(10*10*)*0*(D)0*(10*10*)*15、不能被如下状态转换图识别的句子是__________。(A)ab(B)b0b(C)a01b(D)a10b20110ba6、由EàE+T,TàT*F,则可推断终结符对(+,*)的优先关系为___

3、____。(A)+>*(B)*>+(C)+<*(D)*<+第8页共8页7、若存在项目Aàa.bS(其中a和b是终结符，A和S是非终结符),则它是___________。(A)移进项目(B)归约项目(C)接受项目(D)待约项目8、编译过程中，以下不是常见的中间语言有___________。(A)后缀式(B)抽象语法树(C)三元式(D)语法树二、填空题：（每空2分，共20分）（说明：将答案写在试卷后面的答题纸上）分数评卷人1、编译程序是将_____________翻译成____________的程序。2、有文法G:SàaSb,Sàab,它确定的语言是___________

4、_____。3、有如下的状态转换图，与其等价的正规式为______________。201baa4、对于文法SàSa

5、Sbc

6、b,取消左递归后为SàbS’，S’à___________。5、在对文法G构造识别活前缀的DFA时，若有一个项目集有两个项目S→rD×和D→D×i（其中r和i为终结符，S和D为非终结符），则此时存在__________冲突。6、对于文法G：S’àS,SàBB,BàaB,Bàb，现在构造了两个规范LR的项目集I0和I1，请在I1中填出第一个项目的搜索符。I0S’à×S,#Sà×BB,#Bà×aB,a/bBà×b,a/bI1SàB×B,____Bà

7、×aB,#Bà×b,#B7、b*(c+d/e)的后缀式为_______________________。8、把ifa

8、10分，共50分）（说明：将答案写在试卷后面的答题纸上）分数评卷人1、考虑文法SàA

9、SAAà0

10、1(1)给出1101的最左推导。(2)画出1101的语法分析树。2、考虑下面的表达式文法，它包括加和赋值：EàE+E

11、E=E

12、i(1)它是二义的吗？(2)如果是二义的，用某个句型的两个不同的最右推导来说明。3、(1)把下面的NFA确定化；(2)将确定后的DFA化简。142aaabbb35第8页共8页4、就下面文法SàA

13、SAAà0

14、1给出一个翻译方案，打印0和1的串的值（如110的值为6，010的值为2）。5、有拓广文法G:(0)S’àS(1)SàAa(2)SàbAc(3

15、)Sàdc(4)Sàbda(5)Aàd活前缀的DFA见下图。(其中，first(S)={b,d},first(A)={d},follow(S)={#},follow(A)={a,c})(1)请根据这个DFA来构造该文法的SLR(1)分析表(2)说明该文法为什么不是SLR(1)文法。I0:S’®.SS®.AaS®.bAcS®.dcS®.bdaA®.dI4:S®d.cA®d.I1:S’®S.I2:S®A.aI3:S®b.AcS®b.daA®.dI8:S®dc.I5:S®Aa.I6:S®bA.cI7:S®bd.aA®d.I10:S®bda.I9:S®bAc