大连理工大学网络教育学院
2020年春《编译原理基础》
期末考试复习题
☆注意事项：本复习题满分共：200分。
一、单项选择题
1、以010结尾的二进制串的正规式为（）。
A．(1|0)*01 B．0*01*
C．(1|0)*010 D．0(1|0)*01
2、与(s|t)* (s|t)等价的正规式是（）。
A．s*| t* B．(st)*(s|t)
C．(s|t)(s|t)* D．(s|t)*
3、对正规式(a*|b*)+所描述的语言，下列说法准确的是（）。
A．连续个a再加连续个b所组成的串的集合
B．a和b个数相等的串的集合
C．a和b组成的所有串（不含空串）的集合
D．a和b组成的所有串（包含空串）的集合
4、对于DFA模型，说法错误的是（）。
A．DFA从任何状态出发，对于任何输入符号，可有多个转换
B．任何状态都没有ε转换
C．DFA有唯一的开始状态
D．DFA可以有多个接受状态
5、以下说法错误的是（）。
A. NFA的状态集合是无限的
B. NFA的输入符号可能有多个
C. DFA的状态集合是有限的
D. DFA的输入符号可能有多个
6、符号串ab1b2是文法G[A]：A→aB B→bB|b的句子，该句子的句柄是（）。A．b1B．b2
C．a D．b1b2
7、移进-归约分析为输入串构造分析树是从（）开始的。
A．根结点B．叶结点
C．中间结点D．任一结点
8、下列叙述正确的是（）。
A．任何LL(1)文法都是LR(1)文法
B．任何LL(1)文法都是SLR(1)文法
C．任何SLR(1)文法肯定是LR(1)文法
D．任何LR(1)文法肯定是LALR(1)文法
9、下列叙述正确的是（）。
A．S属性定义属于L属性定义
B．变量类型声明的语法制导定义不是一个L属性定义
C．L属性定义只包含综合属性
D．L属性定义只包含继承属性
10、中间代码生成时所依据的为（）。
A．语法规则B．语法规则
C．语义规则D．等价变换规则
单选题答案
1． C 2． B 3． D 4． A 5． A
6． B 7． B 8． C 9． A 10．C
二、填空题
1、对编译程序而言，输入数据是，输出结果是。
答案：源程序目标程序
2、对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同的那么该文法就称为是二义的。
答案：语法树
3、编译器常用的语法分析方法有和两种。
答案：自底向上、自顶向下
4、程序设计语言的发展带来日渐多变的运行时存储管理方案，主要分为两大类
即分配方案和分配方案。
答案：静态存储、动态存储
5、最右推导称为，由规范推导产生的句型称为规范句型。
答案：规范推导
三、判断题
1、L*表示零个或多个L连接的并集。（）
2、闭包运算有最高的优先级并且是右结合的运算。（）
3、不确定的有限自动机是指对于某个输入符号，它存在不止一种转换。（）
4、每一个正规集都可以由一个状态数最少的DFA识别，这个DFA是可以不唯一的。（）
5、对于S属性定义，分析树各结点属性的计算可以自下而上地完成。（）
6、编程语言的一些构造的属性依赖于它们所在的上下文，此时使用继承属性是方便的。（）
7、中间表示设计的选择随编译器不同而不同。（）
8、三地址代码每条指令通常包含三个地址，即两个运算对象的地址和一个结果的地址。（）
9、静态单赋值形式是一种便于某些代码优化的中间表示。（）
10、流图的结点是基本块。（）
11、解释器和编译器都需要对源程序进行词法分析、语法分析和语义分析等。（）
12、如果X和Y都是串，那么X和Y的连接是把Y加到X的后面形成的串。（）
13、LM表示L和M的并。（）
14、正规式a*表示由字母a构成的所有串的集合其中不包括空串。（）
15、有限自动机分成确定的和不确定的两种情况。（）
16、由上下文无关文法产生的语言叫做上下文无关语言。（）
17、分析树子结点由非终结符本次推导所用产生式的右部的各符号从右到左依次来标记。（）
18、在语法制导定义中，其中的文法被称为基础文法。（）
19、后缀表示的最大优点是便于计算机处理表达式。（）
20、三地址语句序列的一种图形表示叫做流图。（）
答案：
1．√ 2．× 3．√ 4．× 5．√
6．√ 7．√ 8．√ 9．√ 10．√
11．√ 12．√ 13．× 14．× 15．√
16．√ 17．× 18．√ 19．√ 20．√
四、名词解释
1、基本块
连续的语句序列，控制流从它的开始进入，并从它的末尾离开
2、词法单元
又称单元，是源程序中匹配一个记号模式的字符序列,它由词法分析器识别该记号的一个实例。
3、翻译器
把一种语言变换到另外一种语言的软件。这两种语言分别称为源语言和目标语言。
4、编译器
是一种翻译器，它的目标语言比源语言低级。
五、简答题
1、给出下列语言的正规表达式。
在{0,1}上不以0开头的，以11结尾的字符串集合。
最多只含2个a的{a,b}上的语言。
答：(1) 11 | 1(1|0)* 11
(2) b*(a| ε)b *(a| ε)b* 或者b*|b*ab*|b*ab*ab*
2、简述用综合属性代替继承属性的方法有哪几种。
答：
（1）删除翻译方案中嵌入的动作；
（2）分析栈上的继承属性，使用栈上的综合属性代替继承属性；
（3）模拟继承属性的计算
3、简述分析器的基本动作分类
答：
移进动作
归约动作
接受动作
报错动作
4、简述确定的有限自动机和不确定的有限自动机的区别。
答：确定和不确定的有限自动机都正好能识别正规集，它们之间存在着时空权衡问题:从确定的有限自动机得到识别器，比从等价的不确定的有限自动机得到识别器要快得多，但是，确定的有限自动机可能比等价的不确定有限自动机占用更多的空间，把正规式变成不确定的自动机更直接一些。
5、设∑={0, 1}，写出∑上所有以1开头，101结束的字符串的正规式，并构造其对应的NFA。
答：构造该正规式相应的不确定有限自动机NFA: 1(0|1)*101。
评分标准：画出DFA视为等同画出NFA。
6、简述编译器常用的语法分析方法
答：编译器常用的语法分析方法有自上而下和自下而上两种。自上而下分析器按从根结点到叶结点的次序来建立分析树，而自下而上分析器恰好相反，它们的共同点是从左向右地扫描输入，每次一个符号。
7、从软件工程的角度看，词法分析和语法分析的分离有什么好处？
答：
编译器的效率会改进。
编译器的可移植性加强。
把语言的语法结构分成词法和非词法两部分，为编译器前端的模块划分提供了方便的途径。
8、简述编程通常会出现的错误。
答：
词法错误
语法错误
语义错误
逻辑错误
9、试述为什么用正规式定义语言的词法？
答：
语言的词法规则非常简单，不必用功能更强的上下文无关文法描述它。
对于词法记号，正规式给出的描述比上下文无关文法给出的更简洁且易于理解。
从正规式自动构造出的词法分析器比从上下文无关文法构造出的更有效。
10、写出X:=(B-5)*A+(C+D)*T的三地址代码。
答：
t1=B-5
t2= t1*A
t3=C+D
t4=t3*T
X=t2+t4
11、简述分析器错误处理的基本目标。
答：
清楚而准确地报告错误的出现；
迅速地从每个错误中恢复过来，以便诊断剩余程序的错误；
它不应该使处理正确程序的速度降低太多。
六、分析题
1、设文法G[E]：
E→T | E + T | E - T
T→F | T * F | T / F
F→( E ) | i
1）给出该文法的终结符集合。
2）给出该文法的非终结符集合。
3）画出句子i*( i + i )的自上而下分析树。
4）该文法是LL(1)文法吗？请解释。
答：
1）给出该文法的终结符集合。
+ - * / ( ) i
2）给出该文法的非终结符集合。
E, T, F
3）画出句子i*( i + i )的的自上而下分析树。
最左推导
E?T?T*F?F*F ?i*F?i*(E) ? i*(E+T) ? i*(T+T) ? i*(F+T) ? i*(i+T) ? i*(i+F) ? i*( i + i )
F E F T E ()E T +
T F i
F i
T *
4）该文法是LL(1)文法吗？请解释。 不是。
因为存在左递归，因此不是LL(1)文法。 2、考虑如下的上下文无关文法G[L]：
（1）针对表达式id + id ; id ( id ( ) )给出最左推导。 （2）给出表达式id + id ; id ( id ( ) )的语法树。
L → E ; L | E E → E + T | T T → id | id ( ) | id ( L ) 答： （1）
L ? E ; L
? E+ T ; L ? T+ T ; L ? id + T ; L ? id + id ; L ? id + id ; E ? id + id ; T
? id + id ; id ( L ) ? id + id ; id ( E ) ? id + id ; id ( T ) ? id + id ; id ( id ( ) )
（2）
L ；L E E T L T T +
id E id
id (
)
T E id （）