编译原理(模拟试卷-更新中)1

1、编译原理（模拟试卷更新中）四川理工学院试卷(2015至2016学年第2学期) 系 专业 级 班 学号 姓名 密 封 线 密 封 线 内 不 要 答 题 课程名称：编译原理（模拟试卷更新中）命题教师：黎远松适用班级：软件2013级1-5班考试 2016年5月17日（12周二下午3:00-5:00） 共6页题号一二三四五六七八评阅(统分)教师得分202018868128黎远松注意事项：1、 满分100分。要求卷面整洁、字迹工整、无错别字。2、 考生必须将姓名、班级、学号完整、准确、清楚地填写在试卷规定的地方，否则视为废卷。3、 考生必须在签到单上签到，若出现遗漏，后果自负。4、 如有答题纸，答案请

2、全部写在答题纸上，否则不给分；考完请将试卷和答题卷分别一同交回，否则不给分。 试 题（模拟更新中）得分评阅教师一、 选择题（共10个小题，每个小题2分，共20分）1词法分析器的输入是_。A符号串B源程序C语法单位D目标程序2语言是_。A句子的集合B产生式的集合C符号串的集合D句型的集合3一个句型中称为句柄的是该句型的最左_。A非终结符号B短语C句子D直接短语4扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即_。A字符B单词C句子D句型5构造编译程序应掌握_。A源程序B目标语言C编译方法D以上三项都是6 正规式M1和M2等价是指_。AM1和M2的状态数相等BM1

3、和M2的有向边条数相等CM1和M2所识别的语言集相等DM1和M2状态数和有向边条数相等7代码优化的目的是_。A节省时间B节省空间C节省时间和空间D把编译程序进行等价交换8生成中间代码时所依据的是_。A语法规则B词法规则C语义规则D等价变换规则9下推自动机识别的语言是_。A0型语言B1型语言C2型语言D3型语言10对应Chomsky四种文法的四种语言之间的关系是_。AL0ÌL1ÌL2ÌL3BL3ÌL2ÌL1ÌL0CL3=L2ÌL1ÌL0DL0ÌL1ÌL2=L3得分评阅教师二、 是非题（共10个小题

4、，每个小题2分，共20分。下列各题，你认为正确的，请在题干的括号内打“”，错的打“×”)1. 一个上下文无关文法的开始符， 可以是终结符或非终结符。 (×) 2. 一个句型的直接短语是唯一的。 (×) 3. 已经证明文法的二义性是可判定的。 （ ×） 4. 每个基本块可用一个 DAG 表示。 （ ） 5. 每个过程的活动记录的体积在编译时可静态确定。 （） 6. 2 型文法一定是 3 型文法。 （ ×） 7. 一个句型一定句子。 () 8. 算符优先分析法每次都是对句柄进行归约。 (×) 9. 采用三元式实现三地址代码时， 不利于对中

5、间代码进行优化。 （ ） 10. 编译过程中， 语法分析器的任务是分析单词是怎样构成的。 ()得分评阅教师三、 回答下列问题：（共3个小题，每个小题6分，共18分）1. 对于下面程序段program test (input, output)var i, j: integer;procedure CAL(x, y: integer); begin y:=y*y; x:=x-y; y:=y-x end; begin i:=2; j:=3; CAL(i, j) writeln(j)end. 若参数传递的方法分别为(1)传值、(2)传地址，(3)传名，请写出程序执行的输出结果。答： (1) 3 (2)

6、 16(3) 16 (每个值2分)2. 计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。G(M)：MTBTBa | eBDb | eT | eDd | e解答：计算文法的FIRST和FOLLOW集合：(4分)FIRST(M) = a，b，e，d，e FIRST(T) = a，b，e，d，e FIRST(B) = b，e，d，e FIRST(D) = d，eFOLLOW (M) = #FOLLOW (T) = a，b，e，d，#FOLLOW (B) = a，# FOLLOW (D) = b检查文法的所有产生式，我们可以得到：1. 该文法不

7、含左递归，2. 该文法中每一个非终结符M，T，B，D的各个产生式的候选首符集两两不相交。3. 该文法的非终结符T、B和D，它们都有e候选式，而且FIRST(T)FOLLOW(T)= a，b，e，d f所以该文法不是LL(1)文法。(2分)3. 考虑下面的属性文法 产 生 式 语 义 规 则 SABC Aa Bb Cc B.u := S.u A.u := B.v + C.v S.v := A.v A.v :=3*A.u B.v := B.u C.v := 1 (1) 画出字符串abc的语法树;(2) 对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少?SABCabc答：(1)

8、 (2分)（2） S.v的值为18 (2分)得分评阅教师四、 (8分)构造一个DFA，它接受S=a，b上所有包含ab的字符串。答案： (2分)构造相应的正规式：(a|b)*ab(a|b)*(3分)0123645 a a e e a b e e b b(3分)确定化：I0,1,21,2,31,21,2,31,2,31,2,4,5,61,21,2,31,21,2,4,5,61,2,3,5,61,2,5,61,2,3,5,61,2,3,5,61,2,4,5,61,2,5,61,2,3,5,61,2,5,6 b b b a543210 a a a a a b b b 最小化：0，1，2 3，4，50，

9、 2，1， 3，4，5baa01b3ba得分评阅教师五、 (6分)写一个文法使其语言为L(G)=anbncm| m,n1，n为奇数，m为偶数。文法G(S):得分评阅教师六、 (8分)对于文法G(S):1. 写出句型b(Ma)b的最右推导并画出语法树。2. 写出上述句型的短语，直接短语和句柄。SbM(TMabL)答：1. (4分) 2. (4分)短语: Ma)， (Ma)， b(Ma)b直接短语: Ma)句柄: Ma)得分评阅教师七、 (12分)对文法G(S)：Sa | | (T)TT，S | S(1) 构造各非终结符的FIRSTVT和LASTVT集合;(2) 构造算符优先表;(3) 是算符优先

10、文法吗?(4) 构造优先函数。答：(1) (4分) (2) (4分)a(),a>>>>(<<<=<)>>,<<<>>(3) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。 (1分)(4) 优先函数(3分)a(),F44244G55523得分评阅教师八、 (8分)文法G(S)及其LR分析表如下，请给出串baba#的分析过程。(1) SDbB(2) Dd(3) D(4) Ba(5) BBba(6) BLR分析表ACTIONGOTObda#SBD0r3s3121acc2s43r24r6S5r665r4r46s