资源描述：
《编译原理2010-2011试卷---a(答案)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：华东交通大学2010—2011学年第二学期考试卷 试卷编号： （ A ）卷编译原理（E）课程课程类别：必修课闭卷（√）、开卷()（仅限带教材）： 考试日期：2011.6.14题号一二三四五六七八九十总分累分人签名题分100得分考生注意事项：1、本试卷共7页，总分 100 分，考试时间 12
2、0 分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。得分评阅人一、简答题(每题5分，共20分) 1．简述编译程序与解释程序的主要差异？【答】编译程序产生中间代码，且效率高；解释程序不产生中间代码，且效率低。2．文法的二义性与语言的二义性是两个相同的概念吗？请说明理由。【答】这两个概念是不相同的。文法的二义性指的是文法所描述的语言中至少存在一个句子，而该句子对应两棵不同的语法树（或最左（右）推导）；而语言的二义性是指描述该语言的全部文法都是二义性的。由于描述同一个语言的文法可以有多个，一个二义性文法也可能找
3、到一个等价的无二义性文法，所以一个文法是二义性的，其描述的语言不一定就是二义性的。3．简述在句型分析中的自上而下与自下而上两类分析方法的主要差异？【答】自上而下的分析方法是从文法的开始符号出发，反复使用推导技术，试图把要分析的句型推导出来；自下而上的分析方法是从要分析的句型出发，反复使用归约技术，试图最终归约出文法的开始符号。第7页共7页1．为什么说“素短语是包含有终结符的直接短语”的论断是错误的？并针对文法G[E]：(1)E→E+T
4、T(2)T→T*F
5、F(3)F→i中的句型T+T+F，举一个反例加以进一步说明。【答
6、】在一个文法的句型中，其素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。而不是说是一个直接短语。例如：文法G[E]中的句型T+T+F，其一个素短语为：T+T，而T+T是素短语，但不是直接短语。二、形式文法与自动机题(共20分) 得分评阅人1.请给出生成下述语言L的上下文无关文法：（5分）L={aibjajbi
7、i＞0，j≥1}【答】描述该语言的文法G[S]为：S→aAb
8、εA→bAa
9、ba2.对文法G[E]:E→A│E+A│E–AA→B│A*BB→(E)│a写出句型B-(E)*a的短语、直接短语
10、和句柄。（5分）【答】该句型的对应的语法树如下：故其短语、直接短语和句柄分别为：短语：B；(E)；a；(E)*a；B-(E)*a直接短语：B；(E)；a句柄：B第7页共7页1.设计一个最小状态数的DFA，其输入字母表是{0，1}，它能接受以以01结尾的所有由0和1组成的符号串。（10分）【答】该语言用正规式表示为：(0
11、1)*01或(1
12、0)*01识别该语言的FA为：001ABC1对该FA进行确定化：01{A}{A,B}{A}{A,B}{A,B}{A,C}{A,C}{A,B}{A}令，T1代表{A}，T2代表{A,B}
13、，T3代表{A,C}，则等价的DFA为：T1T2T3100101由于f(T1,1)=T1，f(T2,1)=T3，而T1是非终态，T3是终态，所以T1和T2不等价，故此，该DFA即为最小状态数的DFA。第7页共7页三、语法分析题(每题10分，共30分) 得分评阅人1.给定文法G[S]:S→AaAb│BbBaA→εB→ε证明该文法是LL(1)文法，但不是SLR(1)文法。【答】计算First集和Follow集First(AaAb)={a};First(BbBa)={b};Follow(S)={#};Follow(A)={
14、a，b};Follow(B)={a，b};计算各产生式的SELECT集：SELECT(S→AaAb)={a}│；SELECT(S→BbBa)={b}SELECT(A→ε)={a，b}SELECT(B→ε)={a，b}因为，SELECT(S→AaAb)∩SELECT(S→BbBa)=φ，所以该文法是LL(1)文法；因为该文法的LR(0)项目集规范族中有一个项目集I0，存在“移进-归约”冲突，I0={S→.S’,S→.AaAb，S→.BbBa，A→.，B→.}而，First(AaAb)∩Follow(A)={a}≠φ（Fi
15、rst(BbBa)∩Follow(B)={b}≠φ）用Follow集不能解决其冲突，所以该文法不是SLR(1)文法。2.给定文法G[S]：S→(A)│a│bA→AcS│S请在下面的算符优先关系表中标记为“？”的栏目内填写出正确的优先关系（<、>或=）：ab()c#a>>>b>>>(<<<=<)>>>c<<<>>#<<<=第7页共7
