大连理工编译原理基础2022年春期末考试复习题及答案.pdf

机 密启用前 大连理工大学网络教育学院 2022 年春编译原理基础 期末考试复习题 注意事项：本复习题满分共：200 分。一、单项选择题 1、以 010 结尾的二进制串的正规式为（）。A(1|0)*01 B0*01*C(1|0)*010 D0(1|0)*01 2、与(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 模型，说法错误的是（）。ADFA 从任何状态出发，对于任何输入符号，可有多个转换 B任何状态都没有 转换 CDFA 有唯一的开始状态 DDFA 可以有多个接受状态 5、以下说法错误的是（）。A.NFA 的状态集合是无限的 B.NFA 的输入符号可能有多个 C.DFA 的状态集合是有限的 D.DFA 的输入符号可能有多个 6、符号串 ab1b2是文法 GA：AaB BbB|b 的句子，该句子的句柄是（）。Ab1 Bb2 Ca Db1b2 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、下列叙述正确的是（）。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提高机器的执行效率 D增加对内存容量的要求 14、词法分析器的输出是（）。A源程序 B词法记号流 CNFA DDFA 15、下列（）不是正规式 a(a|b)*b 所描述的串。Aaabb Babb Caab DAabbabba 单选题答案 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、最右推导称为 ，由规范推导产生的句型称为规范句型。答案：规范推导 三、判断题 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、编译器 是一种翻译器，它的目标语言比源语言低级。5、符号表 是为每个变量名字保存一个记录的数据结构，记录的域是该名字的属性。6、属性文法 是指语义规则函数无副作用的语法制导定义。7、S 属性定义 仅仅使用综合属性的语法制导定义称为 S 属性定义。8、注释分析树 每个结点的属性值都标注出来的分析树叫做注释分析树。9、LR 文法 一个文法，如果能为它构造出所有条目都唯一的 LR 分析表，就说它是 LR 文法。10、悬空引用 引用某个已被回收的存储单元就称为悬空引用。11、形参 出现在过程定义中的某些名字是特殊的，它们被称为该过程的形式参数，简称形参。12、过程 是一个声明，它的最简单形式是将一个名字和一个语句联系起来。该名字是过程名，而这个语句是过程体。五、简答题 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、设=0,1，写出上所有以 1 开头，101 结束的字符串的正规式，并构造其对应的 NFA。答：构造该正规式相应的不确定有限自动机 NFA:1(0|1)*101。评分标准：画出 DFA 视为等同画出 NFA。六、分析题 1、设文法 GE：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)的的自上而下分析树。最左推导 ETT*FF*F i*Fi*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T)i*(i+F)i*(i+i)FEiFTE()ET+TFiFiT*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 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；LEETLTT+idEidid()TEid（）