编译原理复习材料
选择题
1. 文法S→0S | S1 | 0的语言是( )。
A. { 0 m1m| m >=0 }
B. { 0 m1m| m >=1 }
C. { 0 m1n | m>=1,n>=0 }
D. { 0 m1n | m>=0,n>=1 }
2. 描述程序语言所采用的Ⅲ型文法是( )。
A. 短语文法
B.正规文法
C.上下文无关文法
D.上下文有关文法
3. 状态转换图实现的简单方法是使每个状态结对应( )。
A.一个终结符
B.一个非终结符
C.一段小程序
D.一个函数
4. 规范归约的关键问题是寻找( )。
A. 最左素短语
B.句柄
C.直接短语
D.短语
5. 一个算符文法的任何产生式的右部都不含有两个相继的( )。
A.终结符
B.非终结符
C.终结符和非终结符
D.空字
6. 算符优先分析法的关键在于规定( )。
A.算符优先顺序和结合性质
B.算符优先顺序
C.结合性质
D.终结符和非终结符之间关系
7. 优先函数的优点是( )。
A.形象直观
B.便于进行比较运算
C.语法分析速度快
D.语法分析方法简单
8. 文法符号的属性通常分为( )两类。
A. 共用属性和私有属性
B.固有属性和可变属性
C.语法属性和语义属性
D.综合属性和继承属性
9. 在程序流图中，组成循环的结点序列应满足( )
A. 它们是强连通的
B.它们中间有唯一的入口结点
C.它们中间有一条回边
D.它们是强连通的且有唯一的入
口结点
10. 在利用寄存器R生成T1:=C/B的目标代码同时,还应记录信息( )。
A. C/B在T1中
B. T1在C/B中
C. R含有T1, T1在R中
D. R含有C/B, C/B在R中
1.D
2.B
3.C
4.B
5.B
6.A
7.B
8.D
9.D 10.C
1. 编译方式与解释方式的根本区别在于( )
A.是否生成目标代码
B.是否生成中间代码
C.是否生成汇编代码
D.是否生成优化代码
2. 编译程序生成的目标程序( )
A.一定是机器语言的程序
B.不一定是机器语言的程序
C.一定不是机器语言的程序
D.一定是汇编语言的程序
3. 设字母表∑={0,1,x,y}, 则∑上的正规式ε所对应的正规集为( )
A.ε
B. {ε0,1,x,y }
C. {ε}
D.Φ
4. *
假设G是一个文法，S是文法的开始符号，如果S===> x,则称x是( )
A.短语
B.句柄
C.句子
D.句型
5. 一个算符文法的任何产生式的右部都不含有两个相继的( )
A.终结符
B.非终结符
C.终结符和非终结符
D.ε字
6. 设有文法G[A]：A →Ax|Ay|Aa|Ac|a|b|c，
下列哪些是该文法的句子( )
(1) aby (2) aycyx (3) aaa (4) bcxy
A.(1) (2) (3)
B. (1) (2) (4)
C.(2) (3) (4)
D.全部
7. ＬＲ分析器的核心部分是( )
A.带先进后出存贮器的DFA
B.一张动作表
C.一张GOTO表
D.一张分析表
8. 在程序流图中，组成循环的结点序列应满足( )
A.它们是强连通的且有唯一的入
B.它们中间有唯一的入口结点
口结点
C.它们中间有一条回边
D.它们是强连通的
9. 表达式a≤b＋c∧a＞d∨a＋b≠e的后缀式式为( )。
A.abc≤ad＋＞∧ab＋e≠∨
B.ab≤c＋∧da＞ab＋e≠∨
C.abc＋≤ad＞∧ab＋e≠∨
D.abc＋≤ad＞ab＋∧e≠∨
10. 程序基本块是指( )
A.一个子程序
B.一个仅有一个入口和一个出口的语句
C. 一个没有嵌套的程序段
D.一组顺序执行的程序段，仅有一个入口和一个出口
1.A
2.B
3.C
4.D
5.B
6.C
7.D
8.A
9.C 10.D
1. BNF是一种用于( )的工具。
A. 描述句型
B.描述句子
C.描述语言
D.描述文法
2. 设字母表∑={0,1,x,y}, 则∑上的正规式ε所对应的正规集为( )
A.ε
B. {ε}
C. {ε0,1,x,y }
D.Φ
3. 规范推导也称为( )
A. 最右推导
B.最左推导
C.一般推导
D.自左向右推导
4. 在规范归约中, 任何可归约串的出现必在( )
A.栈的内部
B.栈顶
C.剩余的输入串中
D.在先进后出栈中
5. 一个算符文法的任何产生式的右部都不含有两个相继的( )
A.终结符
B.非终结符
C.终结符和非终结符
D.ε字
6. ＬＲ分析器的核心部分是( )
A.一张分析表
B.一张动作表
C.一张GOTO表
D.带先进后出存贮器的DFA
7. 算符优先分析的关键问题是寻找( )。
A.句柄
B.最左素短语
C.短语
D.直接短语
8. 四元式之间的联系是通过( )
A.指示器
B.临时变量
C.四元式的编号
D.中间运算结果
9. 表达式a≤b＋c∧a＞d∨a＋b≠e的逆波兰式为( )。
A.abc＋≤ad＞∧ab＋e≠∨
B.ab≤c＋∧da＞ab＋e≠∨
C.abc≤ad＋＞∧ab＋e≠∨
D.abc＋≤ad＞ab＋∧e≠∨
10. 代码外提时要求该不变运算所在的结点是循环的( )。
A.某个出口的必经结点
B.至少是一个入口的必经结点
C.入口的必经结点
D.所有出口的必经结点
1.D
2.B
3.A
4.B
5.B
6.A
7.B
8.B
9.A 10.D
填空题
1. 一个状态转换图可用于一定的字符串。
2. 设∑＝｛a , b , c｝，则∑*中最短的符号串为。
3. 若由文法的开始符号可以推导出串α ，且，则α为原文法的一个句
子。
4. 若文法的某非终结符P满足，称文法含有左递归。
5. 表达式-(a+b)/(c*d)-e的逆波兰式为
______________________________。
6. 后序遍历一棵表达式树，可得到它的。
7. 中间代码是一种面向语法，易于翻译成的代码。
8. 四元式序列中各四元式出现的顺序与是一致的。
9. 若每个程序对应一个流图，则流图中的结点对应一个。
10.
若从流图首结点出发, 到达n j的任一通路必须经过n i，则
称的必经结点。
1. 识别或接受
2. ε
3. α ? VT*
4. Ｐ==＋＞Ｐα
5. ab+cd*/e-
6. 逆波兰式
7. 目标代码
8. 运算顺序
9. 基本块
10. ni为nj
1. 一个非确定的有限自动机可以表示为一个元式。
2. 若文法的某非终结符P满足，称文法含有左递归。
3. 设∑＝｛1 , 2, 3｝，则∑*中最短的符号串为。
4. 用∑+表示∑上所有的集合。
5. 三地址代码的一般形式为。
6. 递归下降法对每个构造一个相应的子程序。
7. 在算符优先分析中，用作为可归约串。
8. 在形式语言中，最推导被称为规范推导。
9. 语法树中，一个结点的属性由此结点的父结点和/或兄弟结点的属性
确定。
10. 如果循环中对变量I只有唯一的形如I=I±C的赋值，则称I为循环中
的变量。
1.
2. 五
Ｐ==＋＞Ｐα
3. ε
4. 长度不为0的串
5. x:=y op z
6. 非终结符
7. 最左素短语
8. 右
9. 继承
10. 基本归纳
1. 终态与非终态的区别在于。
2. 用∑+表示∑上所有的集合。
3. 一个状态转换图可用于一定的字符串。
4. 用于词法分析的扫描缓冲区可将两个半区使用。
5. 一个句型的称为该句型的句柄。
6. 递归下降法对每个构造一个相应的子程序。
7. 算符优先法尤其适用于的分析。
8. 规范归约的关键在于如何确定。
9. 文法符号的属性值可自底向上应用语义规则计算出来。
10. DAG代表。
1. 终态可接受空串
2. 长度不为0的串
3. 识别
4. 互补
5. 最左简单短语
6. 非终结符
7. 表达式
8. 句柄
9. 综合
10. 有向无环图
判断题
1. 若一个文法是递归的，则由它产生的语言的句子个数是有
（）限的。
2. 用于词法分析的扫描缓冲区可将两个半区重叠使用。（）
3. 一个LR分析器实质上是一个带有后进先出存储器的DFA。（）
4. 符号表的每一项一般包含入口栏和信息栏两大部分。（）
5. DAG是对循环进行优化的有效工具。（）
6. 代码外提时要求该不变运算所在的结点是循环的某个出口
（）的必经结点。
1. ×无限
2. ×互补
3. √
4. ×名字
5. ×基本块
6. ×所有
1. 描述程序语言所采用的Ⅲ型文法是上下文无关文法。（）
2. 状态转换图实现的简单方法是使每个状态结点对应一个非
（）终结符
3. 欲构造行之有效的自下而上分析器，则必须清除文法中含（）
有的左递归。
4. 在规范归约中, 任何可归约串的出现必在栈的内部。（）
5. 循环优化中的强度削弱主要是指将循环中的乘法变成加
（）法。
6. 符号表的信息栏中的内容称为关键字。（）
1. ×正规文法
2. ×一段小程序
3. ×自上而下
4. ×栈顶
5. ×递归加法
6. ×名字
1. 设α是某句型的一个子串，若它能被一次直接归约为一个
（）非终结符，则α是该句型的一个直接短语。
2. 语法分析过程可用一棵树表示出来,这棵树叫做语法树。（）
3. 欲构造行之有效的自下而上分析器，则必须清除文法中含
（）有的左递归。
4. 四元式作为中间语言，用于翻译除表达式外的其他语句代
（）码。
5. 循环优化中的强度削弱主要是指将循环中的乘法变成加
（）法。
6. 流图中有向边a→b为回边的条件是a DOM b。（）
1. ×
2. ×分析树
3. ×自上而下
4. ×各种
5. ×递归加法
6. ×b DOM a
简答题
1. 简述正规式与有限自动机的关系。
2. 已知文法G: S → iSeS | iS | i
该文法是否具有二义性？请根据句子iiiei构造语法树予以说明。
3.
4
1. 正规式用来描述正规集，而有限自动机用来识别正规集，在正规
集的意义上它们存在等价关系。
即：
对每一个正规式所代表的正规文法G，都存在一个有限自动机M，
使得L(M)=L(G)，M所能识别的字的全体恰为这个正规文法G的
语言集合；
对每一个有限自动机M，都存在一个可以用正规式表示的正规文
法G，使得L(G)=L(M)，这个正规文法G的语言集合中的任一个
字可以由M识别。
2. 对于句子iiiei，该文法具有两棵不同的语法树与之对应，故为二义性文
法。
S S
/ / \ \ / \
i S e S i S
/ \ | / / \ \
i S ii S e S
| | |
Iii
3. 当文法满足LL(1)条件时，可以为它构造一个不带回溯的自上而
下分析程序。
它由一组递归过程（函数）组成，每个过程（函数）对应文法的
一个非终极符，这样的分析程序称为递归下降分析器。