学院计算机科学与技术学院专业 班 年级 学号 姓名 共 5 页 第 1 页
2010～2011学年第1学期期末考试试卷
《编译原理》（共5页）
（考试时间：2010年12月21日）
| 题号 | 一 | 二 | 三 | 成绩 | 核分人签字 |
| 得分 |
1．汇编程序是将 翻译成 ；编译程序是将 翻译成 。
A．高级语言程序；机器语言程序；汇编语言程序；汇编语言或机器语言程序
B．汇编语言程序；机器语言程序；高级语言程序；汇编语言或机器语言程序
C．汇编语言程序；汇编语言或机器语言程序；高级语言程序；机器语言程序
D．高级语言程序；汇编语言或机器语言程序；汇编语言程序；机器语言程序
2．生成非0开头的正偶数集的文法是( )
A．Z→ABC B．Z→ABC|2|4|6|8
C→0|2|4|6|8 C→0|2|4|6|8
B→BA|B0|ε B→BA|B0|0
A→1|2|3|4|5|6|7|8|9 A→1|2|3|4|5|6|7|8|9
C．Z→ABC D．Z→ABC|2|4|6|8
C→0|2|4|6|8 C→0|2|4|6|8
B→BA|B0|0 B→BA|B0|ε
A→1|2|3|4|5|6|7|8|9 A→1|2|3|4|5|6|7|8|9
3．设有文法G[I]：
I→I0|I1|Ia|Ic|a|b|c
下列符号串中是该文法的句子的有 。
①ab0 ②a0c01 ③aaa ④bc10
可选项有
A．① B．②③④ C．③④ D．①②③④
4．语法分析的常用方法是
①自顶向下 ②自底向上 ③自左向右 ④自右向左
可选项有：
A．①②③④ B．①② C．③④ D．①②③
5．两个有穷自动机等价是指它们的( )。
| A．状态数相等 B．有向弧数相等 C．所识别的语言相等 D．状态数和有向弧数相等 | 6．LR(K)文法是（ ）。 A．从左到右分析，共经过K步的一种编译方法 B．从左到右分析，每次向前预测K步的一种编译方法 C．从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法 D．从左到右分析，每次走K步的一种编译方法。 7．在编译中产生语法树是为了进行 ( )。 A．语法分析 B．语义分析 C．词法分析 D．产生目标代码 8．文法的二义性和语言的二义性是两个 概念。 A．不同 B．相同 C．无法判断 9． 这样的语言，它们能被确定的有限自动机识别，但不能用正规表达时表示。 A．存在 B．不存在 C．无法判定是否存在 10．文法G[S]的产生式是：S→aB B→Aa B→b；那么G[S]是( ) A．正则文法 B．上下文无关文法 C．二义性文法 二、简答题（每题5分，共20分） 1．何谓二义性文法？试举一例说明。 2．通过合并LR(1)文法中的同心状态得到的LALR(1)文法可能会产生哪些冲突？一定不会产生哪些冲突？为什么？ |
学院 计算机科学与技术专业 专业 班 年级 学号 姓名 A卷 共 5 页 第 2 页
3．编译程序在逻辑上由哪几部分组成？编译程序和解释程序有哪些区别？
| 4．设G=（VN，VT，P， | 三、推导题（共70分） 1．对于文法G[S]： S→AB A→Aa|bB B→a|Sb 求句型baSb的全部短语、直接短语和句柄。（10分） |
学院 计算机科学与技术专业 专业 班 年级 学号 姓名 A卷 共 5 页 第 3 页
2. 构造一个NFA，
(1) 接受字母表{a,b}上的正规式(ab|a)*bb*描述的集合。(4分)
(2) 将(1)中的NFA转换为等价的DFA (3分)
| (3) 将(2)中的DFA转换为最小状态DFA（写出步骤）(3分) | 3. 为文法G[S] S→(L) | a L→L,S | S (a)写出一个语法制导定义，计算括号的对数（5分） (b)写出一个语法制导定义，计算括号嵌套的最大深度（5分） |
学院 计算机科学与技术专业 专业 班 年级 学号 姓名 A卷 共 5 页 第 4 页
4. 用自底向上的语法分析方法分析数学公式编排预处理器EQN中的文法G[E]：
E→E sub E sup E
E→E sub E
E→E sup E
E→{E}
E→c
对于上述二义性文法G[E]，给出如下规则
(1) E→E sub E sup E是特例产生式。
(2) sub和sup具有相同的优先级
(3) sub和sup的结合顺序都是右结合的。
| 给出上述文法的语法分析表。（30分） |
学院 计算机科学与技术专业 专业 班 年级 学号 姓名 A卷 共 5 页 第 5 页
5.已知语言写出相应的文法：（10分）
(1)已知语言L={WaWr | W 属于(0 | a)*，Wr表示W的逆}，试构造相应的上下文无关文法。
(2)已知语言L={1n0m1m0n | m>0, n>=0}，试构造相应的上下文无关文法。
| (3)已知语言L={ anbnambm | m>=0, n>0}，试构造相应的上下文无关文法 |
