大连理工大学编译原理复习(共65页)

精选优质文档-倾情为你奉上编译技术命题指导意见教学内容知识点及题型第一章 编译器概述A（1）编译的阶段划分 选择题 2分1 编译程序绝大多数时间花在( )上。 A. 出错处理 B. 词法分析C. 目标代码生成 D. 符号表管理答案：D2 ( ) 和代码优化部分不是每个编译程序都必需的。A. 语法分析B. 中间代码生成C. 词法分析D. 代码生成答案：B3 编译程序前三个阶段完成的工作是( )。A. 词法分析、语法分析和代码优化 B. 代码生成、代码优化和词法分析C. 词法分析、语法分析和语义分析 D. 词法分析、语法分析和代码生成答案：C（2）遍的概念 填空题 2分1 编译阶段的活动常用一遍扫描来实现，一遍扫描包括 和 。答案：读一个输入文件 写一个输出文件2 将编译程序分成若干个“遍”是为了_。答案：使程序的结构更加清晰3 编译器从逻辑上可以分为7个阶段，其中，可以作为一个后端遍的是_阶段。答案：代码生成（3）前端和后端的划分 简答题 5分1 什么是前端？ 5分答案：编译器分成分析和综合两大部分。分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。2 什么是后端？ 5分答案：编译器分成分析和综合两大部分。综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。3 什么是前端？什么是后端？ 5分答案：编译器分成分析和综合两大部分。分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。第二章2.1 2.2 词法记号的定义及描述B（1）词法分析器的功能 选择题 2分1 词法分析程序的输出结果是（ ）。A. 单词的种别编码B. 单词在符号表中的位置 C. 单词的种别编码和单词属性值D. 单词的单词属性值答案：C2 词法分析器用于识别_。 A. 字符串 B语句C单词D标识符答案：C3 扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即（ ）。A 字符 B单词 C句子 D句型答案：B（2）词法记号概念及属性 填空题2分1 词法记号是由 和 构成的二元组。答案：记号名 属性值2 词法单元是源程序中匹配一个 的字符序列。答案：记号模式3 影响语法分析的决策， 影响记号的翻译。答案：记号名 属性（3）正规式与语言的对应关系 选择题 2分1 下面文法（ ）和正规表达式a*b描述的语言相同。A. Sab | aSbB. Sb | aSC. Sa | aSbD. Sa | Sb答案：B2 最多包含两个a的a,b上的语言（ ）。A. (a|)b*(a|)B. b*ab*ab*|b*ab*C. b*(a|b*)(a|b*)b*D. b*(a|)b*(a|b*)b*答案：D3 与(a|b)*等价的正规式是（ ）。A. (a*|b*)*B. (a|b)+C. (ab)*D. a*|b*答案：A第二章2.3.1,2.3.2 NFA,DFAC（1）NFA与DFA的概念 选择题 2分1 有如图所示的有穷自动机，与之等价的正规式为（ ）。A. (0|1)*(000|111)(0|1)B. (0|1) (000|111)(0|1)C. (0|1)*(000|111)(0|1) *D. ，B ，C选项都不正确答案：C2 对于NFA和DFA模型说法错误的是（ ）。A. DFA是NFA的特殊形式B. DFA与NFA的状态转换完全相同C. 都有唯一的开始状态D. 都可以有多个接受状态答案：B3 对于DFA模型，说法错误的是（ ）。A. DFA从任何状态出发，对于任何输入符号，可有多个转换B. 任何状态都没有转换C. DFA有唯一的开始状态D. DFA可以有多个接受状态答案：A（2）NFA 的构造 简答题 10分1 设有非确定的有自限动机NFA M=(A，B，C，0，1，d，A，C)，其中：d (A，0)=C d (A，1)=A，B d (B，1)=C d (C，1)=C。请画出状态转换距阵和状态转换图。答案：状态转换距阵为：d01ACA，BBÆCCÆC11011状态转换图为：2 构造正规式相应的 NFA : 1(0|1)*101。答案： 3 为（|a）b*）* 构造非确定的有限自动机，给出它们处理输入串ababbab的转换序列。答案：输入串ababbab的转换序列： 0 789 10 或者 0 10（3）NFA转化为 DFA 简答题 10分1 设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。答案：构造相应的正规式：(0|1)*1(0|1) NFA: 确定化：I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4、2 构造正规式 1(0|1)*101 相应的DFA。答案：先构造NFA：确定化： 重新命名，令AB为B、AC为C、ABY为D得： 所以，可得DFA为： 3 对于下图所示NFA，回答下列问题：（1）用正规式描述该有限自动机所表示的语言。（2）由NFA转为DFA。（3）构造最简DFA。答案：（1）(a|b)*a(a|b)*（2）（3）（4）DFA的化简 简答题 10分1 已知 NFA= （ x,y,z,0,1,M,x,z ），其中：M(x,0)=z, M(y,0)=x,y, M(z,0)=x,z, M(x,1)=x, M(y,1)= ,M(z,1)=y, 构造相应的DFA并最小化。答案：根据题意有NFA图:下表由子集法将NFA转换为DFA：面将该DFA最小化： (1) 首先将它的状态集分成两个子集：P1=A,D,E,P2=B,C,F (2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21=C,F,P22=B。 (3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11=A,E,P12=D。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。 (5) 综上所述，DFA可以区分为P=A，B，D，E，C，F。所以最小化的DFA如下：2 给定下列自动机：把此自动机转换为确定自动机DFA。答案：有状态矩阵如图：从而可得DFA如图：3 （1）将下图中的NFA M确定化为DFA M。 （2）将DFA M化简。答案：确定化: ab00,1110-0，10,11状态编号 ab01220-11210 a ->a a2 b b 未简化的DFA最小化： 分为：终态集0,1 非终态集2 0,1a =1 0,1b = 2 所以：0,1 = 0 2 = 110 a -> b a第二章2.4,2.5 词法分析器的生成器; 第二章习题D（1）直接从语言构造DFA 简答题5分1 写出能产生字母表x,y上的不含两个相邻的x,且不含两个相邻的的全体符号串的有限状态自动机。答案：2 处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。答案：124start52othersothers/*/3 有语言 L=w|w (0,1)+，并且 w 中至少有两个1 ，又在任何两个1之间有偶数个 0 ，试构造接受该语言的确定有限状态自动机。答案：（2）Lex 的功能 填空题 2分1 Lex是从基于正规式的描述来构造 。答案：词法分析器2 Lex程序包含三部分： 、 和辅助函数。答案：声明 翻译规则3 由Lex建立的 分析器通常作为 分析器的一个子程序。答案：词法 语法第三章 3.1上下文无关文法E（1）上下文无关文法定义选择题2分；1 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组（ ）。 A. 句子 B. 句型 C. 单词 D. 产生式答案：D2 文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（ ）。A. 短语文法     B. 正则文法     C. 上下文有关文法D. 上下文无关文法答案：D3 文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_。A. 短语文法B. 正则文法C. 上下文有关文法D. 上下文无关文法答案：A（2）最左推导、最右推导简答题5分；1 文法 S->a|