编译原理试卷A(含答案).doc

仲编译原理（A）卷 学号 一、是非题 （正确填T，错误填F,每题2分，共16分）(1) 一个上下文无关文法包括四个组成部分：一组终结符号、一组非终结符号、一个开始符号和一组产生式。 （T）(2) 乔姆斯基文法分为四类，其中能力最强的是3型文法。0最强（F）(3) 正规式中的运算符“*”读作“连接”。闭包（F）(4) 若正规表达式r等价于有限自动机M，则它们描述(接受)的语言L(r)、L(M)满足L(M)=L(r)。（T）(5) 编译过程通常为词法分析、语法分析、词法分析、语义分析与中间代码生成、优化、目标代码生成几个阶段。词法分析不用了（F）(6) 如要依据文法G构造一个不带回溯的自上而下的语法分析器，文法G不能含有左递归，但允许文法G的部分产生式的右部候选式有公共左因子。（F）(7) a*(b+c)的后缀表达式为abc+*。（T）(8) 三地址代码的间接三元式表示法的优点是采用间接码表，便于优化处理。（T）二、选择题 （每小题选出一个最合适的答案，每题2分，共16分）(1) 编译程序是对（D） a) 汇编程序的翻译 b) 高级语言程序的解释执行 c) 机器语言程序的执行 d)高级语言程序的翻译(2) 编译语法分析阶段的主要任务是(B)。a) 扫描源程序，识别单词 b) 根据语法规则把单词流分解成各类语法单位 c) 按语言语义进行初步翻译，生成中间代码 d) 将中间代码变换成目标机器代码或汇编代码(3) 词法分析程序的输出结果是（C） a)单词的种别编码 b) 单词在符号表中的位置 c) 单词的种别编码和单词属性值 d) 单词的单词属性值(4) 语法分析的常用方法类型可分为（B ）。自上而下 自下而上 自左而右 自右而左 ，可选项有：a) b) c)d) (5) 一个句型的（ C）称为该句型的句柄。a) 短语 b) 直接短语 c)最左直接短语 d) 最右直接短语(6) 下面文法（B）和正规表达式a*b描述的语言相同。 a)Sab | aSb b) Sb | aS c) Sa | aSb d) Sa | Sb(7) 文法G(S):SAcAa|b|e，FIRST(S)等于（A） a) a,b b) a,b,c c) c d) a,b,e(8) 某翻译器依如下翻译模式设计，其基础文法可由开始符号S产生一个二进制数。SL print(L.val); /* print函数以10进制方式打印数值*/LL1B L.val = L1.val*2 + B.val; LB L.val = B.val; B0 B.val = 0; B1 B.val = 1; ,当输入101时，翻译器的输出为（c）a) 2 b) 1 c)5 d)9二、简答题：(每题10分，共20分)(1) 什么是自下而上语法分析方法，简述“移入-规约”法的基本原理。自下而上分析法：从输入串开始,逐步进行归约,直到文法的开始符号.即从树末端开始,构造语法树.所谓归约,是指根据文法的产生式规则,把产生式的右部替换成左部符基本思想:设计一个堆栈,把符号串从左至右压入栈中,判别栈顶符号是否为某一个产生式的右部,若是则把栈顶的这一部分替换成(归约为)该产生式的左部符号.号.(2) 什么是属性文法，文法符号的属性分为哪两类，基于属性文法的语法制导翻译法的处理过程通常是怎样的？答：是在上下文无关的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（成为属性）文法符号的属性分为综合属性和继承属性对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。处理过程如下：输入串语法树依赖图语义规则计算次序四、计算分析题：(48分)(1) 令文法GS为： SABAaAb | abBb,问：（1）GS定义的语言L(G)是什么？（2）给出句子aabbb的最左推导，并给出其语法分析树。（10分）(1)答： SabBabb SaAbBaabbBaabbb SaAbBaaAbbBaaabbbBaaabbbb Sanbm(n=0,m=1)(2)答： s ABaAbBaabbBaabbbb S A B a A b b a b 语法分析树(2) (1)将下图中的NFA M确定化为DFA M。 (2)将DFA M化简。 确定化: ab00,1110-0，10,11 状态编号 ab01220-11210 a a a12 b b 未简化的DFA最小化： 分为：终态集0,1 非终态集2 0,1a =1 0,1b = 2 所以：0,1 = 0 2 = 10 a b a（11分）(3) 考虑以下表结构文法G S：Sa|(T)TT,S|S(1) 改写GS，消去GS的左递归。(2) 改写后的文法是否LL(1)文法？给出它的预测分析表。（12分）答：(1) Sa|(T)TSTT,ST|e(2) 该文法不含左递归First(S) = a, ,( First(T) = a, ,( First(T) = , , eFollow(S) = , ,), #Follow(T) = )Follow(T) = )LL(1)预测分析表a(),#SSaSS(T)TTSTTSTTSTTTeT,ST(4) 考虑以下表结构文法G S：Sa|(T)TT,S|S(1) 给出句子(a,(a,a)的最右推导和句柄。解：S(T) (T, (T) (T,(T,S) (T,(T,a) (T,(S,a)(T,(a,a) (S,(a,a) (a,(a,a)语法树： S ( T ) T , S S ( T ) a T , S S a a短语：a 、 a,a 、 （a,a） 、a,(a,a) 、(a,(a,a)直接短语：a最左直接短语（句柄）：a(2)给出GS的SLR分析表，该文法是否SLR文法。（15分） 解：拓广文法为S 1. S S 2. S a 3. S 4. S (T) 5. T ST6. T ,ST7. T e构造SLR所有项目：1. S S2. S S3. S a4. S a 5. S 6. S 7. S (T)8. S (T)9. S (T)10. S (T)11. T ST12. T ST13. T ST14. T 15. T ,ST16. T, ST17. T, ST18. T, ST构造SLR项目集规范族：I0: S I1: I3: S S S S S S aS a I2: I4:S (T) （ S a a S (T)T STS aS S (T) TI5: ） I6:S (T) S (T) ( I7: S I8: I9:T ST T,ST T, ST T ,ST , S a S T STS S a | S S (T) S S (T)I10:T T, ST TI11: T ST不存在项目冲突： Follow(S) = #Follow(S) =