编译原理基础

1、机 密启用前大连理工大学网络教育学院2021年秋编译原理基础期末考试复习题 注意事项：本复习题满分共：200分。一、单项选择题 1、以010结尾的二进制串的正规式为（ ）。A(1|0)*01 B0*01*C(1|0)*010 D0(1|0)*012、与(s|t)* (s|t)等价的正规式是（ ）。As*| t* B(st)*(s|t)C(s|t)(s|t)* D(s|t)*3、对正规式(a*|b*)*所描述的语言，下列说法准确的是（ ）。A连续个a再加连续个b所组成的串的集合Ba和b个数相等的串的集合Ca和b组成的所有串（不含空串）的集合Da和b组成的所有串（包含空串）的集合4、对于DFA模型

2、，说法错误的是（ ）。ADFA从任何状态出发，对于任何输入符号，可有多个转换B任何状态都没有转换CDFA有唯一的开始状态DDFA可以有多个接受状态5、以下说法错误的是（ ）。A. NFA的状态集合是无限的B. NFA的输入符号可能有多个C. DFA的状态集合是有限的D. DFA的输入符号可能有多个6、符号串ab1b2是文法GA：AaB BbB|b的句子，该句子的句柄是（ ）。Ab1 Bb2Ca Db1b27、移进-归约分析为输入串构造分析树是从（ ）开始的。A根结点 B叶结点C中间结点 D任一结点8、下列叙述正确的是（ ）。A任何LL(1)文法都是LR(1)文法B任何LL(1)文法都是SLR(

3、1)文法C任何SLR(1)文法肯定是LR(1)文法D任何LR(1)文法肯定是LALR(1)文法9、下列叙述正确的是（ ）。AS属性定义属于L属性定义B变量类型声明的语法制导定义不是一个L属性定义CL属性定义只包含综合属性DL属性定义只包含继承属性10、中间代码生成时所依据的为（ ）。A词法规则 B语法规则C语义规则 D等价变换规则11、（ ）不是编译程序的组成部分。A词法分析程序B代码生成程序C设备管理程序D语法分析程序12、编译的各阶段工作都涉及（ ）。A符号表管理B词法分析C语法分析D语义分析13、下面对编译程序分为“遍”描述正确的是（ ）。A使编译程序结构清晰B提高程序的执行效率C提高机

4、器的执行效率D增加对内存容量的要求14、词法分析器的输出是（ ）。A源程序B词法记号流CNFADDFA15、下列（ ）不是正规式a(a|b)*b所描述的串。AaabbBabbCaabDAabbabba单选题答案1 C 2 B 3 D 4 A 5 A 6 B 7 B 8 C 9 A 10C 11C 12A 13A 14B 15D二、填空题1、对编译程序而言，输入数据是 ，输出结果是 。答案：源程序 目标程序2、对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同的 那么该文法就称为是二义的。答案：语法树3、编译器常用的语法分析方法有 和 两种。答案：自底向上、自顶向下4、程序设计语言的发展

5、带来日渐多变的运行时存储管理方案，主要分为两大类即 分配方案和 分配方案。答案：静态存储、动态存储5、最右推导称为 ，由规范推导产生的句型称为规范句型。 答案：规范推导三、判断题1、L*表示零个或多个L连接的并集。（ ）2、闭包运算有最高的优先级并且是右结合的运算。（ ）3、不确定的有限自动机是指对于某个输入符号，它存在不止一种转换。（ ）4、每一个正规集都可以由一个状态数最少的DFA识别，这个DFA可以是不唯一的。（ ）5、对于S属性定义，分析树各结点属性的计算可以自下而上地完成。（ ）6、编程语言的一些构造的属性依赖于它们所在的上下文，此时使用继承属性是方便的。（ ）7、中间表示设计的选择

6、随编译器不同而不同。（ ）8、三地址代码每条指令通常包含三个地址，即两个运算对象的地址和一个结果的地址。（ ）9、静态单赋值形式是一种便于某些代码优化的中间表示。（ ）10、流图的结点是基本块。（ ）11、解释器和编译器都需要对源程序进行词法分析、语法分析和语义分析等。（ ）12、如果X和Y都是串，那么X和Y的连接是把Y加到X的后面形成的串。（ ）13、LM表示L和M的并。（ ）14、正规式a*表示由字母a构成的所有串的集合其中不包括空串。（ ）15、有限自动机分成确定的和不确定的两种情况。（ ）16、由上下文无关文法产生的语言叫做上下文无关语言。（ ）17、分析树子结点由非终结符本次推导所用

7、产生式的右部的各符号从右到左依次来标记。（ ）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、翻译器把一种语言变换到另外一种语言的软

8、件。这两种语言分别称为源语言和目标语言。4、编译器是一种翻译器，它的目标语言比源语言低级。5、符号表是为每个变量名字保存一个记录的数据结构，记录的域是该名字的属性。6、属性文法是指语义规则函数无副作用的语法制导定义。7、S属性定义仅仅使用综合属性的语法制导定义称为S属性定义。8、注释分析树每个结点的属性值都标注出来的分析树叫做注释分析树。9、LR文法一个文法，如果能为它构造出所有条目都唯一的LR分析表，就说它是LR文法。10、悬空引用引用某个已被回收的存储单元就称为悬空引用。11、形参出现在过程定义中的某些名字是特殊的，它们被称为该过程的形式参数，简称形参。12、过程是一个声明，它的最简单形式

9、是将一个名字和一个语句联系起来。该名字是过程名，而这个语句是过程体。五、简答题1、给出下列语言的正规表达式。在0,1上不以0开头的，以11结尾的字符串集合。最多只含2个a的a,b上的语言。 答：(1) 11 | 1(1|0)* 11 (2) b*(a| e)b *(a| e)b* 或者b*|b*ab*|b*ab*ab*2、设=0, 1，写出上所有以1开头，101结束的字符串的正规式，并构造其对应的NFA。答：构造该正规式相应的不确定有限自动机NFA: 1(0|1)*101。评分标准：画出DFA视为等同画出NFA。六、分析题1、设文法GE：E T | E + T | E - TT F | T *

10、 F | T / FF ( E ) | i1）给出该文法的终结符集合。2）给出该文法的非终结符集合。3）画出句子i*( i + i )的自上而下分析树。4）该文法是LL(1)文法吗？请解释。答：1）给出该文法的终结符集合。+ - * / ( ) i2）给出该文法的非终结符集合。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 )4）该文法是LL(1)文法吗？请解释。不是。因为存在左递归，因此不是LL(1)文法。2、考虑如下的上下文无关文法GL：（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Þ