编译原理知识点

编译原理复习编译原理复习⼀、基本概念（填空15分，选择10分，简答：15分）1、编译程序按扫描源程序的遍数分类可以分为哪两类？⼀遍扫描、多遍扫描2、⾼级语⾔的单词分类有哪些？基本字、运算符、标识符、常数、界符3、⼆义性⽂法，⼆义性语⾔的定义？⼆义性⽂法：⽂法G对某句型存在⾄少两种不同的语法树。

⼆义性语⾔：某语⾔对应的任意⼀种⽂法都是⼆义性⽂法4、DFA的定义及组成：确定的有穷⾃动机； M=(K,∑,f, S,Z)K是⼀个有穷集，它的每个元素称为⼀个状态；∑是⼀个有穷字母表，它的每个元素称为⼀个输⼊符号，所以也称∑为输⼊符号表； F是转换函数，是K×∑→K上的映像S∈K，是唯⼀的⼀个初态Z K，是⼀个终极态，终态也称为接收状态或结束状态5、最左推导、规范推导的定义：最左推导：若x和y是符号串α中有两个以上的⾮终结符号时，对推导的每⼀步坚持把α中的最左⾮终结符号进⾏替换，称为最左推导。

规范推导：通常，我们把能由最左(右)推导推出的句型称为左(右)句型。

另外，也常把最右推导称为规范推导，⽽把右句型称为规范句型。

6、确定的⾃顶向下分析⽅法通常有哪两种？采⽤确定的⾃顶向下分析的前提条件是什么？递归⼦程序法、预测分析法对每⼀个⾮终结符A的两个不同产⽣式，A→α，B→β，满⾜SELECT（A→α）∩SELECT（B→β）=?，其中αβ不同时能→ε7、词法分析的常⽤⽅法有哪两种？⾃顶向下；⾃底向上。

8、简单优先分析法、算符优先分析法属于、LR(0)分析法分别属于何种归约？规范规约、⾮规范规约、规范规约9、⾼级程序设计语⾔的翻译⽅式主要有哪两种，⼆者的根本区别在于哪⾥？⽅式：编译程序、解释程序区别：⽣不⽣成⽬标代码10、词法分析程序和语法分析程序的任务分别是什么？词法分析是编译的第⼀阶段，它的主要任务是按语⾔的词法规则，从左⾄右逐个字符地对源程序进⾏扫描，从源程序中识别出每个单词，并把每个单词转换成它们的内部表⽰，即所谓的token，同时进⾏词法检查。

期末复习总结《编译原理》第一章：绪论一、填空问题①由于计算机只能认识机器语言，所以需要翻译程序将高级语言翻译成计算机可以识别的机器语言。

②编译程序的工作过程一般主要划分为词法分析，语法分析，中间代码生成，代码优化，目标代码生成等几个基本阶段，同时还会伴有表格管理和出错处理。

③如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两个阶段：编译阶段和运行阶段。

如果编译程序生成的目标程序是汇编语言的程序，则源程序的执行分为三个阶段：编译阶段，汇编阶段和运行阶段。

1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序 ,则其翻译程序称为编译程序.1-03.编译方式与解释方式的根本区别在于是否生成目标代码 .1-05.对编译程序而言,输入数据是源程序,输出结果是目标程序 .1-10.一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括(1)c.其中, (2)b 和代码优化部分不是每个编译程序都必需的. 词法分析器用于识别 (3)c ,语法分析器则可以发现源程序中的 (4)d .(1) a.模拟执行器 b.解释器 c.表格处理和出错处理 d.符号执行器(2) a.语法分析 b.中间代码生成 c.词法分析 d.目标代码生成(3) a.字符串 b.语句 c.单词 d.标识符(4) a.语义错误 b.语法和语义错误 c.错误并校正 d.语法错误1-11.程序语言的语言处理程序是一种 (1)a . (2)b 是两类程序语言处理程序,他们的主要区别在于 (3)d .(1) a.系统软件 b.应用软件 c.实时系统 d.分布式系统(2) a.高级语言程序和低级语言程序 b.解释程序和编译程序c.编译程序和操作系统d.系统程序和应用程序(3) a.单用户与多用户的差别 b.对用户程序的查错能力c.机器执行效率d.是否生成目标代码1-12.汇编程序是将 a 翻译成 b ,编译程序是将 c 翻译成 d .a.汇编语言程序b.机器语言程序c.高级语言程序d. a 或者 be. a 或者 cf. b 或者 c1-13.下面关于解释程序的描述正确的是 b .(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于COBOL 和 FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的a. (1)(2)b. (1)c. (1)(2)(3)d.(2)(3)1-14.高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释程序通常缺少 (1)e 和 (1)b .其中， (1)e 的目的是使最后阶段产生的目标代码更为高效.与编译系统相比，解释系统 (2)d .解释程序处理语言时,大多数采用的是 (3)b 方法.(1): a. 中间代码生成 b.目标代码生成 c.词法分析 d.语法分析 e.代码优化(2): a.比较简单,可移植性好,执行速度快b.比较复杂,可移植性好,执行速度快c.比较简单,可移植性差,执行速度慢d.比较简单,可移植性好,执行速度慢(3): a.源程序命令被逐个直接解释执行 b.先将源程序转化为之间代码,再解释执行c.先将源程序解释转化为目标程序,在执行d.以上方法都可以1-15.用高级语言编写的程序经编译后产生的程序叫 b .用不同语言编写的程序产生 a 后,可用 g 连接在一起生成机器可执行的程序.在机器中真正执行的是 e .a. 源程序b. 目标程序c. 函数d. 过程e. 机器指令代码f. 模块g. 连接程序h.程序库1-16.要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容: c , d , f .a. 汇编语言b. 高级语言c. 源语言d. 目标语言e. 程序设计方法f. 编译方法g. 测试方法h. 机器语言1-17.由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成(1)d ,诸阶段的工作往往是 (2)d 进行的.(1) a. 过程 b. 程序 c. 批量 d.遍(2) a. 顺序 b. 并行 c. 成批 d.穿插1-18.编译程序与具体的机器 a , 与具体的语言 a .a. 有关b.无关1-19.使用解释程序时,在程序未执行完的情况下， a 重新执行已执行过的部分.a. 也能b.不可能1-20.编译过程中,语法分析器的任务就是 b .(1) 分析单词是怎样构成的(2)分析单词串是如何构成语句和说明的(3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构a. (2)(3)b. (2)(3)(4)c. (1)(2)(3)d.(1)(2)(3)(4)1-21.编译程序是一种常用的 b 软件.a. 应用b. 系统1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过 b 这几步.(1) 编辑 (2) 编译 (3) 连接 (4) 运行a. (1)(2)(3)(4)b. (1)(2)(3)c. (1)(3)d.(1)(4)1-23.编译程序必须完成的工作有 a .(1) 词法分析 (2) 语法分析 (3) 语义分析(4) 代码生成 (5) 之间代码生成 (6) 代码优化a. (1)(2)(3)(4)b. (1)(2)(3)(4)(5)c. (1)(2)(3)(4)(5)(6)d. (1)(2)(3)(4)(6)e. (1)(2)(3)(5)(6)1-24.“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法a .a. 不正确b.正确1-25.把汇编语言程序翻译成机器可执行的目标程序的工作是由 b 完成的.a. 编译器b. 汇编器c. 解释器d. 预处理器1-26.编译程序生成的目标程序 b 是机器语言的程序.a. 一定b. 不一定1-27.编译程序生成的目标程序 b 是可执行的程序.a. 一定b. 不一定1-28．编译程序是一种 B 。

编译原理面试知识点1. 什么是编译原理？编译原理是计算机科学中的一个重要领域，研究如何将高级语言（源语言）翻译成低级语言（目标语言），以便计算机能够理解和执行程序。

编译原理涉及的主要内容包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等。

2. 词法分析词法分析是编译过程的第一步，其主要任务是将源代码分解为一个个的词法单元，也称为记号。

词法单元可以是关键字、标识符、运算符、分隔符等。

3. 语法分析语法分析是将词法单元流转化为抽象语法树的过程。

抽象语法树是一种树形结构，用于表示程序的语法结构。

语法分析器根据给定的语法规则，对词法单元进行语法分析，检查程序是否符合语法规则。

4. 语义分析语义分析是编译过程中的重要环节，主要任务是对抽象语法树进行静态语义检查和语义动作的执行。

静态语义检查用于检查程序中是否有语法错误，如类型错误、未声明的变量等。

语义动作则是执行一些语义规则，如类型转换、变量赋值等。

5. 中间代码生成中间代码是一种抽象的低级语言，它介于源语言和目标语言之间。

中间代码生成将抽象语法树转化为中间代码，目的是简化目标代码生成的复杂度，并进行一些代码优化。

6. 代码优化代码优化是在保持程序功能不变的前提下，通过改变代码的结构和算法，使程序更加高效、节省资源。

常见的代码优化技术包括常量折叠、循环优化、内联函数等。

7. 目标代码生成目标代码生成将中间代码转化为机器语言或汇编语言，使计算机能够执行程序。

目标代码生成需要考虑目标机器的特性和限制，如寄存器分配、内存管理等。

8. 常见的编译器构建工具•Flex：用于生成词法分析器。

•Bison：用于生成语法分析器。

•LLVM：开源的编译器基础设施，提供了多种编译器相关工具和库。

•GCC：GNU编译器套件，包括编译器、调试器、性能分析器等。

9. 常见的编程语言特性和编译优化技术•静态类型检查：在编译期间检查变量的类型是否匹配，提前发现类型错误。

编译原理名词解释2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。

3.DISPLAY表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。

由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址，display表就是用于登记每个外层过程的最新活动记录起始地址。

9.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。

10.短语：令G是一个文法，S 划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。

14.超前搜索：在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。

15.句柄：一个句型的最左直接短语。

16.语法制导翻译：在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法叫做语法制导翻译。

17.规范句型：由规范推导所得到的句型。

18.素短语：素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。

19.语法：是组规则，用它可形成和产生一个合式的程序。

20.语义：定义程序的意义的一组规则。

21.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。

三种级别：局部优化、循环优化、全局优化21．词法分析词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。

22．LL(1)文法若文法的任何两个产生式A →α | β都满足下面两个条件：（1）FIRST(α) ⋂FIRST(β) = φ；（2）若β⇒* ε，那么FIRST(α)⋂ FOLLOW( A ) = φ。

我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。

编译原理和解释器的设计和实现方法近年来，编程语言的应用场景越来越广泛，但是不同的编程语言为了能够被计算机所理解，需要进行相应的编译或解释。

而编译原理和解释器的设计和实现方法就成了我们必须要掌握的知识点。

本文将从理论基础到实际操作，从编译器和解释器的设计到实现方法，一一探究编译原理和解释器的相关内容。

一、编译原理的基础知识编译原理是指根据程序设计语言的源代码，将其转换为目标语言，以实现计算机能够理解和执行的过程。

编译原理的基础知识包括词法分析、语法分析、语义分析和代码生成等部分。

1. 词法分析：词法分析的主要任务是将源代码中的字符序列转换成词法单元（Token）。

在此过程中，需要识别出不同的关键字、标识符、运算符和界符等。

2. 语法分析：语法分析的主要任务是识别符合语法规则的抽象语法树（AST）。

在此过程中，需要建立相应的语法分析树，以便更好地理解代码结构。

3. 语义分析：语义分析的主要任务是对词法和语法分析的结果进行加工，生成相应的中间代码。

在此过程中，需要解决相应的类型推断问题、属性计算问题等。

4. 代码生成：代码生成的主要任务是将中间代码转换成目标代码，生成可执行文件。

在此过程中，需要考虑不同目标机器的指令集和寄存器数量等问题。

以上四个部分都是编译原理的重要组成部分。

其中的实现方法和技巧，涉及到很多理论和实践经验的积淀。

二、解释器的设计和实现方法相对于编译器，解释器是一种特殊的翻译器，它在翻译之前并不需要生成目标代码，而是基于源代码进行动态解释。

解释器的设计和实现方法，也是十分重要的。

1. 解释器的工作原理解释器的的工作原理是将源代码进行词法分析和语法分析，并构建相应的语法树。

然后，通过执行语法树上的节点指令，实现相应的计算和操作。

由于解释中间结果不需要写入目标文件，因此解释器相比于编译器具有较高的灵活性和交互性。

2. 解释器的优缺点解释器的优点在于快速执行和易于调试。

由于解释器在执行过程中不需编译和链接阶段，因此可以将部分高层次的语义部分延迟到执行中逐步解析。

1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。

（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。

（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。

（4）优化器，对中间代码进行优化处理。

（5）目标代码生成器，把中间代码翻译成目标程序。

（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。

（7）出错管理，把错误信息报告给用户。

编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。

（2）。

语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。

（3）语义分析与中间代码产生。

任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

（4）优化。

任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

（5）目标代码生成。

任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。

2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。

b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。

复习汇总一、第一章概述1.文法与自动机的等价1)0型文法—图灵机2)1型文法—线性有界非确定图灵机3)2型文法—非确定下推自动机4)3型文法—有限状态自动机2.编译技术的应用1)语法制导的结构化编辑器2)程序格式化工具3)软件测试工具4)程序理解工具5)高级语言的翻译工具6)等等3.从面向机器的语言到面向人类的语言（结合第二章第9小点理解）1)面向机器的语言：机器指令，汇编语言2)面向人类的语言：通用程序设计语言，数据查询语言，形式化描述语言（正规式,产生式）等等。

4.各语言的分类（结合第二章第9小点理解）1)过程式语言，面向对象语言：通用程序设计语言。

2)函数语言：面向特点领域的，递归特性。

例如LISP语言3)说明性，非算法式语言：LEX/YACC,SQL。

4)脚本式语言：Shell语言5.语言之间的转换（李静PPT41）1)高级语言之间的转换一般称为预处理或转换。

2)高级语言翻译成汇编语言或机器语言称之为编译。

3)把汇编语言翻译成机器语言称之为汇编。

4)将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之为交叉汇编。

5)把机器语言翻译成汇编语言称之为反汇编。

6)把汇编语言翻译成高级语言称之为反编译。

6.编译器和解释器1)编译器●源程序的翻译和翻译后的程序的运行是两个不同的阶段。

◆编译阶段：用户输入源程序，经过编译器的处理，生成目标程序。

◆目标程序的运行阶段：根据要求输入数据，得出结果。

2)解释器（凡是可以采用编译器的地方均可以采用解释器）●解释器把翻译和运行结合到一起，编译一段源程序，紧接着就执行它。

这种方式称为解释。

7.解释器的优点（对比与编译器）1)具有较好的动态特性。

2)具有较好的移植特性。

8.解释器的缺点（对比于编译器）1)相比于编译器需花费大量的时间。

2)占用更多的内存空间。

9.编译器的工作阶段（结合第二章6小点红色部分理解）1)源程序->词法分析器->语法分析器->语义分析器->中间代码生成器->代码优化器->目标代码生成器->目标代码2)工作过程中的每个阶段均采用了符号表管理器，出错处理器。

编译原理复习《编译原理》第⼀章：绪论1.翻译器：把⼀种语⾔变换到另外⼀种语⾔的软件。

这两种语⾔分别称为源语⾔和⽬标语⾔。

2.编译器：⼀种翻译器，它的⽬标语⾔⽐源语⾔低级。

3.典型的编译器可以划分成6个逻辑阶段：词法分析，语法分析，语义分析，中间代码⽣成，代码优化，代码⽣成。

4.按照对⽬标机器的依赖性，把编译过程分成前端（依赖于源语⾔，独⽴于⽬标机器）和后端（依赖于⽬标机器，独⽴于源语⾔,只与中间语⾔有关（从中间代码⽣成⽬标代码））。

5.前端包括：词法分析，语法分析，语义分析，中间代码⽣成。

6.后端包括：代码优化，代码⽣成。

7.解释器：不同于编译器的另⼀类语⾔处理器，直接执⾏源程序所指定的运算。

解释器的执⾏效率⽐编译器低，因为解释器⽆法解开循环。

8.遍：编译的⼏个阶段常⽤⼀遍（pass）扫描实现，⼀遍扫描包括读⼀个输⼊⽂件和写⼀个输出⽂件。

《编译原理》第⼆章：词法分析⼀些概念：1.词法单元：⼜称单词，是编程语⾔中合法的字符串。

2.词法记号：满⾜某种规则的词法单元，采⽤同⼀种记法——词法记号。

该规则称为模式。

3.模式：描述词法单元与词法记号对应关系的规则。

是描述源程序中某个记号的词法单元集合的规则。

4.字母表：符号的有限集合，例：∑={0,1}串：符号的有穷序列，例：0110,ε语⾔：字母表上的⼀个串集{ε,0,00,000,…},{ε},?正规式（运算符的优先级：*>连接运算>|）N F A是这样⼀个数学模型，包括1)状态集合S2)输⼊字母表∑3)转换函数m o v e:S?(∑?{ε})→P(S)4)唯⼀的初态s∈S5)终态集合F?SD F A是这样⼀个数学模型，包括1)状态集合S2)输⼊字母表∑3)转换函数m o v e:S?∑→S4)唯⼀的初态s∈S5)终态集合F?S第三章语法分析3.1 上下⽂⽆关⽂法上下⽂⽆关⽂法是四元组（V T , V N, S , P ）1) V T: 终结符集合(⾮空有限集合，记号名是其同义词)2) V N: ⾮终结符集合（⾮空有限集合）3) S : 开始符号4) P : 产⽣式集合，产⽣式形式 : A →α上下⽂⽆关⽂法没有强制的顺序关系。

编译原理文字总结编译原理文字总结1.高级程序设计语言的翻译主要有两种方式：编译和解释。

2.编译过程概述：(1)词法分析：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或符号）如基本字，标识符，常数，算符和界符。

(2)语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如短语，子句，句子，程序段和程序等(3)语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

包括静态语义检查和中间代码的翻译。

(4)优化：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

(5)目标代码生成：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。

编译程序结构框图3．文法是表述语言的语法结构的形式规则。

4.所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。

一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。

5.形式上说，一个上下文无关文法G是一个四元式（VT,VN,S,＆）其中VT是一个非空有限集，它的每个元素称为终结符号；VN是一个非空有限集，它的每个元素称为非终结符号，VT∩VN=；S是一个非终结符号，称为开始符号；&是一个产生式集合，每个产生式的形式是P→a，其中P属于VN，a属于（VT∪VN）*。

开始符号S至少必须在某个产生式的左部出现一次。

6.推导每前进一步总是引用一条规则（产生式）。

7.假定G是一个文法，S是它的开始符号。

如果Sa，则称a是一个句型（0步或若干步）。

仅含终结符号的句型是一个句子。

文法G所产生的句子的全体是一个语言，将它记为L(G)。

L(G)=｛a|Sa&a∈VT*｝例如终结符号串（i*i+i）是文法（2.1）的一个句子。

编译原理复习《编译原理》复习README来源⽹络&书本&PPT整理截取了⽼师课上讲解or布置的题⽬⼀些题⽬懒得贴答案了，写了些注意事项第1 章引论运⾏编译程序的计算机：宿主机运⾏编译程序所产⽣的⽬标代码的计算机：⽬标机第1 题解释下列术语：（1）编译程序：如果源语⾔为⾼级语⾔，⽬标语⾔为某台计算机上的汇编语⾔或机器语⾔，则此翻译程序称为编译程序。

（2）源程序：源语⾔编写的程序称为源程序。

（3）⽬标程序：⽬标语⾔书写的程序称为⽬标程序。

（4）编译程序的前端：它由这样⼀些阶段组成：这些阶段的⼯作主要依赖于源语⾔⽽与⽬标机⽆关。

通常前端包括词法分析、语法分析、语义分析和中间代码⽣成这些阶段，某些优化⼯作也可在前端做，也包括与前端每个阶段相关的出错处理⼯作和符号表管理等⼯作。

（5）后端：指那些依赖于⽬标机⽽⼀般不依赖源语⾔，只与中间代码有关的那些阶段，即⽬标代码⽣成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语⾔程序从头到尾扫视并完成规定任务的过程。

第2 题⼀个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

(区别编译程序的六个阶段)答案：⼀个典型的编译程序通常包含8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码⽣成程序、中间代码优化程序、⽬标代码⽣成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输⼈源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进⾏语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码⽣成程序：按照语义规则，将语法分析程序分析出的语法单位转换成⼀定形式的中间语⾔代码，如三元式或四元式。

中间代码优化程序：为了产⽣⾼质量的⽬标代码，对中间代码进⾏等价变换处理。

第一章：编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执行目标程序。

解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。

编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。

解释程序和编译程序的根本区别：是否生成目标代码第三章：Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG）◊ 0型语言或短语结构语言文法Ｇ的每个产生式α→β中：若α∈Ｖ*ＶNＶ*, β∈(ＶN∪ＶT)* ，则Ｇ是0型文法，即短语结构文法。

1型文法（CSG）◊ 1型语言或上下文有关语言在0型文法的基础上：若产生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外，则Ｇ是１型文法,即：上下文有关文法另一种定义：文法G的每一个产生式具有下列形式：αAδ→αβδ，其中α、δ∈V*，A∈VN，β∈V+；2型文法（CFG）◊ 2型语言或上下文无关语言文法Ｇ的每个产生式A→α，若A∈ＶN ,α∈(ＶN∪ＶT)*，则Ｇ是２型法，即：上下文无关文法。

3型文法（RG）◊ 3型语言或正则(正规)语言若Ａ、Ｂ∈ＶN，ａ∈ＶT或ε，右线性文法：若产生式为Ａ→ａＢ或Ａ→ａ左线性文法：若产生式为Ａ→Ｂａ或Ａ→ａ都是３型文法（即：正规文法）最左（最右）推导在推导的任何一步α⇒β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换规范推导：即最右推导。

规范句型：由规范推导所得的句型。

句子的二义性（这里的二义性是指语法结构上的。

）文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。

文法的二义性一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。

第三章3.1 对于词法分析器的要求1．词法词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。

词法分析器(Lexical Analyzer) 又称扫描器(Scanner)：执行词法分析的程序。

2．程序语言的单词符号：关键字、标识符、常数、运算符、界符。

3．输出的单词符号的表示形式:(单词种别，单词自身的值)Eg：while (i>=j) i--;输出单词符号：< while, - >< (, - >< id, 指向i的符号表项的指针><>=, - >< id, 指向j的符号表项的指针>< ), - >< id, 指向i的符号表项的指针>< --, - >< ;, - >4．词法分析器作为一个独立子程序：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。

5．词法分析器3.2 词法分析器的设计1．词法分析器2．输入、预处理：输入串放在输入缓冲区中。

预处理子程序：剔除无用的空白、跳格、回车和换行等编辑性字符;区分标号区、捻接续行和给出句末符等扫描缓冲区（指向开始位置，向前搜索确定终点）3．单词符号的识别、超前搜索：(1)基本字识别Eg：DO99K=1，10 DO 99 K = 1，10IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能确定哪些是基本字(2)标识符(3)常数(4)算符和界符4．状态转换图(有限方向图)<1>结点代表状态<2>状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。

<3>一个状态转换图可用于识别(或接受)一定的字符串。

5．语法分析的状态转换图6．状态转换图的实现思想：每个状态结对应一小段程序。

1、编译程序：能够把用各种高级语言书写的源程序翻译成某种等价的目标程序的翻译程序。

2、遍：指编译程序对源程序或中间代码程序从头到尾扫描一次。

3、静态分配：在编译时就能够安排好目标程序运行时的全部数据空间。

4、编译程序包括词法分析、语法分析、中间代码生成、优化，目标代码产生五个阶段，上述各阶段中还要进行表格处理和出错处理的工作。

5、编译程序可分为五个阶段：词法分析、语法分析、中间代码生成、优化、目标代码生成。

上述五个阶段之间每个阶段输出为作下一阶段的输入，第一阶段的输入是源程序，最后阶段的输出是目标代码。

6、程序语言是由语法和语义两方面定义的。

语法指可以形成和产生一个合式的程序的一组规则，语义是定义一个程序的意义的一组规则。

7、一个名字的属性包括类型和作用域。

8、目标代码一般有三种形式：能够立即执行的机器语言代码，待装配的机器语言模块和汇编语言代码。

9、2型文法又称为（上下文无关文法），3型文法又为（正规文法）。

10、虽然名字都是用标识符表示的，但名字和标识符有着本质的区别。

11、词法分析器的任务是从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成单词符号串的中间程序。

12、执行词法分析的程序称为词法分析器或扫描器。

13、词法分析器所输出的单词符号常常表示成如下二元关系：（单词种别，单词自身值）。

14、词法分析器：是一种程序，它能将字符串形式的源程序改造成单词符号串形式的中间程序。

15、程序语言的单词符号包括：（标识符）、（运算符）、（常数）、（基本字）、界符等。

16、超前搜索：在词法分析过程中，有时为了确定词性，需要超前扫描若干个字符，这个动作为超前搜索。

17、状态转换图是一张有限方向图，其中结点代表状态，状态之间用箭弧连接，箭弧上的标记代表在射出结点状态下可能出现的输入字符或字符类，状态中有一个初态，至少有一个终态。

18、自上而下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一颗语法树。

1．与机器有关的代码优化有那些种类，请分别举例说明。

解答：与机器有关的优化有：寄存器优化，多处理优化，特殊的指令优化，无用的指令消除等四类。

冗余指令删除假设源程序指令序列a:=b+c; c:=a-d;编译程序为其生成的代码很可能是下列指令序列：MOV b, R0ADD c, R0MOV R0,aSUB d, R0MOV R0,c假如第四条指令没有标号，上述两个赋值语句在一个基本块内，则第四条指令是多余的，可删除。

特殊指令的使用例如，如果目标机器指令系统包含增1指令INC，对于i:=i+1的目标代码MOV i, R0ADD #1, R0MOV R0, i便可被代之以1条指令Inc i说明：优化的特点是每个改进可能会引发新的改进机会，为了得到最好的改进，一般可能需要对目标代码重复扫描进行优化。

2．设有语句序列a:=20b:=a*(a+10);c:=a*b;试写出合并常量后的三元式序列。

解答：该语句序列对应的三元式序列为：（1）（:=, 20,a）（2）(+, a, 10)（3）(*, a, (2) )（4）(:=, a, b)（5）(* a, b)（6）(:=, (5), c)合并常量后的三元式序列为：（1）（:=, 20，a）（2）(:=, 600, b)（3）(:=, 12000, c)3、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。

解答：该表达式的四元式序列为：（1）（*，b,c,T1）（2）(+,a,T1,T2)（3）(*,c,b,T3)（4）(+,T3,a,T4)（5）(-,T4,e,T5)（6）(*,b,c,T6)（7）(+,T6,d,T7)（8）(/,T5,T7,T8)（9）(-,T2,T8,T9)可对该表达式进行删除公共子表达式的优化。

优化后的四元式序列为：（1）（*，b,c,T1）（2）(+,a,T1,T2)（3）(-,T2,e,T5)（4）(+,T1,d,T7)（5）(/,T5,T7,T8)（6）(-,T2,T8,T9)4.设有算术表示式（a*b+c）/(a*b-c)+(c*b+a-d)/(a*b+c)试给出其优化后的三元式序列。

《编译原理》总复习-07级第一章编译程序的概述（一）内容本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。

（二）本章重点编译（程序），解释（程序），编译程序的逻辑结构。

（三）本章难点编译程序的生成。

（四）本章考点全部基本概念。

编译程序的逻辑结构。

（五）学习指导引论部分主要是解释什么是编译程序以及编译的总体过程。

因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。

第三章文法和语言课外训练（一）内容本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。

（二）本章重点上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。

（三）本章难点上下文无关文法，语法分析树，文法的分类。

（四）本章考点上下文无关文法的定义。

符号串的推导。

语法分析树的构造。

（五）学习指导要构造编译程序，就要把源语言用某种方式进行定义和描述。

学习高级语言的语法描述是学习编译原理的基础。

上下文无关文法及语法树是本章学习的重点。

语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。

编译原理什么是编译程序？编译程序也叫编译系统，是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序。

编译的各个阶段什么是文法？文法是以又穷的集合刻画无穷的集合的一个工具。

1、字母表:它是非空有穷集。

例如：∑={a,b,c}或∑={1,2,3}2、符号：字母表中的元素称为符号。

3、符号串：符号的有穷序列，符号串也称为字。

用ε来表示空符号串。

例如：a,ab,abc4、长度：符号串的长度是指该串所包含的符号个数。

用|x|表示符号串x的长度。

例如：|a|=1，|abn|=35、连结：设x和y为符号串，则称xy 为他们的连结。

例如：x=aa,y=bb,则xy=aabb6、空集：不含任何元素的集合,记为 。

7、乘积：设A和B是符号串集，则用AB表示A和B的乘积。

A={a,b},B={c,d},则AB={ac,ad,bc,bd}8、方幂：设A为符号串集，则定义A0={ε}A1=AA n=A n-1 A例如：A={a,b} 则有：A0={ε} A1={a,b}A2={aa,ab,ba,bb}9、正闭包：设A为符号串集，则用A+表示A的正闭包，其具体定义如下：A+=A1∪A2∪A3∪⋯…例如：A={a},A+={a,aa,aaa,……}10、星闭包：设A为一集合，则定义A的星闭包为A* ，其具体定义如下A*=A0∪A+例如：A={a},A*={ε,a,aa,aaa,……}文法G定义为四元组(V N，V T，P，S )其中V N为非终结符号(或语法实体，或变量)集；V T为终结符号集；P为产生式(也称规则)的集合；V N，V T和P是非空有穷集。

S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。

V N和V T不含公共的元素，即V N∩V T = φ用V表示V N ∪V T，称为文法G的字母表或字汇表例文法G=（V N，V T，P，S）V N = { S }, V T ={ 0, 1 }P={ S→0S1, S→01 }S为开始符号推导：用若干次产生式可从x串导出y串，则称y为x的推导，记为x y。

简答题1.什么是上、下文无关文法？它是由几部分组成的？答：上、下文无关文法所定义的语法范畴，是完全独立于这种范畴可能出现的环境的。

它由四部分组成：一组终结符号，一组非终结符号，一个开始符号和一组产生式。

2.简述正规式和有限自动机的关系。

答：上的非确定有限自动机M所能识别字的全体L（M）是上的一个正规集。

对于上的每个正规集V，存在一个上的确定有限自动机M，使得V=L（M）。

3.简述NFA和DFA的区别。

答：①DFA初态是唯一的，NFA可以有多个初态。

②DNF是单值函数，NFA是多值函数。

③DFA每个弧线用中一个不同输入字符做标记，而NFA每条弧用中的一个字做标记。

4.何为递归下降分析法。

答：在不含左递归和每个非终结符的所有的首符集都两两不想交的条件下。

我们就可以构造一个不带回溯的的自上而下的分析程序。

该程序是由一组递归过程组成的。

每个过程对应文法的一个非终结符。

这种语法分析的方法称为文法递归下降分析法。

5.什么叫做递归下降分析器？答：当一个文法满足 LL（1）条件时，我们就可以为它构造一个不带回溯的自上而下分析程序，这个分析程序是由一组递归过程组成的，每个过程对应文法的一个非终结符，这样的一个分析程序称为递归下降分析器。

6．语法分析方法如何分类，它们面对的主要问题是什么？答：语法分析方法分为自下而上的分析法和自上而下的分析法。

自上而下分析法的主要问题是：消除文法的左递归以及由文法开始符号出发推导句子的过程中如何避免回溯。

自下而上分析法的主要问题是：在由输入串出发向文法的开始符号规约的过程中。

如何确定可规约子串。

7.何为中间语言，简述它的作用。

答：中间语言是一种面向语法。

其复杂性介于用高级语言书写的源程序和用机器语言表示的目标程序之间。

是一种易于翻译成目标代码的代码形式。

它的作用在于利用它作为中间环节。

不仅可以较快的实现源程序的翻译过程而且可以在此基础上应用优化方法将源程序翻译成运行时间短，占用内存少的目标程序。

三种语言涉及的三类人：源语言（设计者），编译语言（实现者），目标语言（使用者）变量：对存储单元的抽象（变量是对一个(或若干个)存储单元的抽象，赋值语句则是修改存储单元内容的抽象。

）。

属性：变量的作用域，变量的生存期，值，类型静态绑定：凡是在编译时能确定的属性，称为静态属性；若绑定在编译时完成，运行时不改变，称为静态绑定。

动态绑定：凡是在运行时才能确定的属性称为动态的。

若绑定在运行时完成，称为动态绑定。

定义：虚拟机是由软件实现的机器。

（实际机器+程序）程序单元：1,程序单元: 程序执行过程中的独立调用单元；2.单元的表示在编译时，单元表示是该单元的源程序。

运行时，单元表示由一个代码段和一个活动记录组成，称为单元实例。

3.活动记录:执行单元所需要的信息,以及该单元的局部变量所绑定的数据对象的存储区。

4.非局部变量:一个程序单元可以引用未被本单元说明而被其它单元说明的变量。

5.引用环境:局部变量+非局部变量。

6.别名:同一单元的引用环境中有两个变量绑定于同一数据对象，称这些变量具有别名。

7.副作用:对绑定于一个非局部变量的对象进行修改时，将产生副作用。

8.程序单元可以递归激活,从而一个单元可以有很多个实例,但代码段相同。

不同的仅仅是活动记录（所以绑定必须是动态的）。

数据类型：数据类型实质上是对存储器中所存储的数据进行的抽象。

它包含了一组值的集合和一组操作。

数据类型的作用1.实现了数据抽象2.使程序员从机器的具体特征中解脱出来3.提高了编程效率聚合的六种方式：笛卡尔积，有限映像，序列，判定或，递归，幂集2.抽象数据类型的定义：满足下述特性的用户定义类型称为抽象数据类型:1.在实现该类型的程序单元中,建立与表示有关的基本操作;2.对使用该类型的程序单元来说,该类型的表示是隐蔽的。

类型等价：若T1和T2是两个类型，且T1的任何值都可以赋予T2类型的变量，T1类型的实参可以对应类型T2的形参，反之亦然，则称T1和T2是相容的，或等价的；有两种类型的相容性概念：①名字等价②结构等价两种相容性实现时的比较①名字等价的实现比较简单②结构等价的实现需要的模式匹配过程可能十分复杂编译时与类型相关的三个重要工作：1.类型检查12.类型转换3.类型等价语句级控制：顺序，选择，重复四种单元级控制结构：显式调用异常处理协同程序并发单元语言的定义：程序设计语言是用来描述计算机所执行的算法的形式表示；语言＝语法＋语义语法:用以构造程序及其成分的一组规则的集合语义:用以规定语法正确的程序或其成分的含义的一组规则的集合文法定义：文法是描述语言的语法结构的形式规则, 必须准确,易于理解,且描述能力强。