机密★启用前大连理工大学网络教育学院2019年秋《编译原理基础》期末考试复习题☆注意事项：本复习题满分共：200分。
一、单项选择题1、以010结尾的二进制串的正规式为（）。
A．(1|0)*01 B．0*01*C．(1|0)*010 D．0(1|0)*012、与(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．b2C．a D．b1b27、移进-归约分析为输入串构造分析树是从（）开始的。
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． A 2． B 3． D 4． A 5． A6． 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-5t2= t1*At3=C+Dt4=t3*TX=t2+t411、简述分析器错误处理的基本目标。
答：清楚而准确地报告错误的出现；迅速地从每个错误中恢复过来，以便诊断剩余程序的错误；它不应该使处理正确程序的速度降低太多。
六、分析题1、设文法G[E]：E→T | E + T | E - TT→F | T * F | T / FF→( E ) | i1）给出该文法的终结符集合。
2）给出该文法的非终结符集合。
3）画出句子i*( i + i )的自上而下分析树。
4）该文法是LL(1)文法吗？请解释。
答：1）给出该文法的终结符集合。
+ - * / ( ) i2）给出该文法的非终结符集合。
E, T, F3）画出句子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 iF 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 idid ()T E id （）。