DOC《编译原理试题》

编译原理试题 计算机学院2001级班学号 姓名 题号 一二三四五六七八九十十一 十二 总分 满分

12 6

8 7

8 8

12 12

7 6

6 8

100 得分 一 选择题(12分) 【 】1.

词法分析器的输入是 . A.符号串 B.源程序 C.语法单位 D.目标程序 【 】2.两个有穷自动机等价是指它们的 . A.状态数相等 B.有向弧数相等 C.所识别的语言相等 D.状态数和有向弧数相等 【 】3.文法G:S → xSx | y 所识别的语言是 . A.xy*x B.(xyx)C.xx*yxx* D.x*yx* 【 】4.设a,b,c为文法的终结符,且有优先关系a(b和b(c,则.A.必有a(c B.必有c(a C.必有b(a D.选项A、B和C都不一定成立 【 】5.若状态k含有项目"A→α.",且仅当输入符号a∈FOLLOW(A)时,才用规则"A →α"归约的语法分析方法是 . A.LALR分析法 B.LR(0)分析法 C.LR(1)分析法 D.SLR(1)分析法 【 】6.生成中间代码时所依据的是 . A.语法规则 B.词法规则 C.语义规则 D.等价变换规则 【 】7.表达式(a∨b)∧(c∨d)的逆波兰表示为 . A.ab∨∧cd∨ B.ab∨cd∨∧ C.ab∨cd∨D.ab∨∧cd∨ 【 】8.基本块 . A.只有一个入口语句和一个出口语句 B.有一个入口语句和多个出口语句 C.有多个入口语句和一个出口语句 D.有多个入口语句和多个出口语句 二 判断题(6分.认为正确的填"T",错的填"F") 【 】1.同心集的合并有可能产生"归约/归约"冲突. 【 】2.一个文法所有句子的集合构成该文法定义的语言. 【 】3.非终结符可以有综合属性,但不能有继承属性. 【 】4.逆波兰表示法表示表达式时无需使用括号. 【 】5.一个有穷自动机有且只有一个终态. 【 】6.若过程p第k次被调用,则p的DISPLAY表中就有k+1个元素. 三 填空题(8分) 1.最常用的两类语法分析方法是 和 分析法. 2.对于文法G[E]:E→T|E+T T→F|T*F F→P↑F|P P→(E)|i,句型T+T*F+i的直接短语为 ,句柄为 . 3.在LR(0)分析法中,若(,β(V*且a(则称"A ((."为 项目,称"S ((.aβ"为 项目. 4.在PL/0的目标代码解释执行时,寄存器B总是指向当前执行过程活动记录的 ,而寄存器T总是指向 . 四(7分)有穷自动机M接受字母表(={0,1}上所有满足下述条件的串:串中至少包含两个连续的0或两个连续的1.请写出与M等价的正规式. 五(8分)构造下列文法相应的有穷自动机. G[S]: S → aA | bQ A → aA | bB | b B → bD | aQ Q → aQ | bD | b D → bB | aA E → aB | bF F → bD | aE | b 六(8分)写一个文法,使其语言是: L = { ambmanbn | m,n≥0 } 七(12分)已知文法 G[A]: A → aAB | a B → Bb | d (1)构造与G[A]等价的LL(1)文法;

(2)构造G'[A]的预测分析表. 八(12分)考虑文法 G[S]: S → AS | b A → SA | a (1)构造文法的可归前缀图(活前缀的DFA);

(2)判断文法是否是LR(0)文法,并说明理由. 九(7分)将下面程序段翻译成四元式序列. while A