编译原理期末总结

编译是计算机系统软件的最重要组成部分之一，也是用户最直接关心的工具之一。编译原理的整个知识体系是数十年中无数学术精英在形式语义学、计算数学、计算机科学等相关领域探索、积累的结果。整个编译程序,也是一个完整的系统算法,将数据结构的理论进一步专一化。

编译原理的主要内容概括了开发一个编译程序所需要的基本理论、方法和技术,如词法分析、语法分析、语义分析、中间代码生成、符号表、存储空间组织、优化和目标代码生成等。随着编译技术的发展,加入了属性文法、语法制导翻译、面向对象语言的编译、并行编译等知识。在程序设计和数据结构等课程学习后,学生对较为孤立的算法有了一定的了解,再学习编译原理,可以较系统地认识程序算法,培养分析问题和解决问题的能力。

作为授课教师，如何在有限的学时内，使学生理解编译的基本原理、掌握编译的基本方法，提高学生的动手能力，使课程的教学效果得到较大改观，是一个迫切需要解决的课题。课程组以现代教育教学理论为指导，在教学过程中，针对教材选择、课堂教学、习题指导、答疑讨论、网络辅助、教学互动等环节进行综合探索和创造性的改革与实践，积累经验。为学生创造一个全方位立体化的教学环境，满足各层次学生的需要。

在教学过程中，学生理解和掌握这门课有一定难度，出现这种情况的原因存在以下几个方面：

(1)编译程序规模大。由于编译原理是一个极其复杂的系统，程序规模大，导致不可能在一节课或一段时间讲述完，只好将它分解开一部分一部分地研究， 但是这样容易造成知识体系断裂。不可能在短时间让学生对整个编译系统各部分融会贯通，理清各部分逻辑关系的顺序。

(2)理论知识抽象。要完整地构造一个编译系统并不是一件容易的事情，它不仅需要具有较完备的软件知识，并需要掌握现有的软件工具的使用，而且更重要的是要有丰富的实践经验，了解硬件系统结构和操作系统的功能。这些对于刚学完基础知识的学生来讲，理解难度系数相当大。

(3)算法的理解和实现。编译原理这门课包含许多理论知识和算法，这些理论的学习和理解都存在着一定的难度。其中理论知识包括：词法分析器的构造，语法中各种分析器（LR, LL,SLR,LALR 等）实现与完成。

针对这些问题，分别采取各种不同的策略，策略包括传统教学方法和现代教学理论两方面， 已经应用这些方法于实际教学中，已取得良好的教学效果。

第一、传统的教学方法是教学成果的精华，如何在现今的教学中灵活应用，

也值得我们讨论，我们常用的方法为：比喻式教学方法、问题式教学方法、反思式教学方法。

(1)比喻式教学方法就是用接近我们生活中的例子来近似地表示问题， 使问题更容易理解和解决。一般来说大学生的想象能力，逻辑能力比较强，但由于计算机处理问题的过程与日常处理问题有些不同， 而且计算机领域中涉及到一些概念比较抽象， 所以在讲解时打比方，转换问题的难度， 是常采用的方法。

(2)问题式教学方法可以更好地扩展学生的思维，发挥学生学习的迁移。问题式教学一般分四步： 提出问题、引导问题、解决问题、扩充问题。 在分析语法分析器时，首先提出：语法分析的解决问题？常用的语法分析的方法？引导语法分析构造的步骤和过程， 在引导过程中，解决语法构造过程的难点，并且扩充问题到，对于同一种语法在用不同的语法分析器中，将产生的结果和基理。语法分析器，让学生在分解问题的过程中得到了理解和应用。

(3)反思式教学方法要求教师从学生的角度来考虑问题，讲解问题。这种方式可以加强学生和老师之间的互动， 降低学生学习焦虑的情绪，提高教学的效果。

第二、构建多媒体环境下的教学环境，利用现代的教学手段，多媒体设施，电子教案等多种途径，实现课堂时间的有效化，在传统的教学模式下，推导理论需要大量的板书，老师忙于讲，而学生忙于记笔记，一堂课下来，学生累，老师累， 结果学生不知道具体内容。借助多媒体，各种算法的推导一目了然，老师的重点放在讲解算法的原理， 理顺原理之间的逻辑关系上，学生则侧重于理解。具体的做法为向学生提供各类资源库的网上教学系统，帮助学生理解课堂教学内容。

编译原理期末总结 [篇2]

1编译程序： 从高级语言到汇编语言或机器语言的翻译程序

2.源程序：用汇编语言或高级语言编写的程序

3. 目标程序:用目标语言所表示的程序。 目标语言：介于源语言和机器语言之间的 “中间语言”，也可以是某种机器的机器语言,也可以是 某机器的汇编语言。

4 翻译程序:将源程序转换为目标程序的程序称为翻译程序。

5 赋值语句的语法规则： A::=V=E E::=T|E+T T::=F|T*F F::=V|(E)|C V::=标识符 C::=常数

6 遍：对源程序（包括源程序中间形式）从头到尾扫描一次，并做有关的加工处理，生成新的源程序中间形式或目标程序，通常称之为一遍。

优点：节省内存空间，提高目标代码质量，逻辑机构清晰

缺点：编译时间较长，会增加输入输出所消耗的时间，在内存许可下少用为妙

7前端：通常将与源程序有关的编译部分称为前端。 包括词法分析，语法分析，语义分析，等分析部分

后端：与目标机有关的部分称为后端。包括中间代码生成，代码优化，目标程序生成等综合部分

8编译程序构成部分以及功能： （1）词法分析（扫描器）：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词及其有关属性，并转换成属性字。（2）语法分析(分析器)：在词法分析的基础上，根据语言的语法规则，逐一分析词法分析时得到的属性字，检查语法错误，若没有错误，则给出正确的语法结构（如短语、子句、句子、程序段、程序等）。（3）语义分析(语义处理)：语法分析识别出的各类语法范畴，分析其含义,进行和初步翻译，产生介于源代码和目标代码之间的一种代码“中间代码”。或者直接生成目标代码。（4）优化：依据程序的等价变换规则，尽量压缩

目标程序运行时所需的时间和所占的存储空间，以提高目标程序的质量（5）目标代码生成：把经过优化的中间代码转化成特定机器上的低级语言代码。

9计算机执行用高级语言编写的程序途径有两种：解释方式和编译方式。 根本区别：是否生成了目标代码。 解释方式下，翻译程序事先并不对高级语言程序进行彻底翻译以得到机器代码，而是读入一条语句，就解释其含义并执行，然后再读入下一条语句，再解释执行，即按，源程序中语句的动态顺序逐句地进行分析解释，并立即予以执行。 编译方式下，翻译程序先对高级语言程序进行彻底翻译并生成目标代码，然后再对目标代码进行执行，即对源程序的处理是先翻译后执行。简单来说解释方式不生成目标代码，编译方式生成目标代码

10编译程序采用多遍扫描还是单编扫描需要考虑哪些因素 不一定，多遍编译器结构清晰，构造时间短，运行时需要内存少，产生的目标代码质量高，但时间效率低，

应该根据具体情况决（1）语句的大小与结构，（2）机器规模（3）设计目的（4）设计人员的素质及数量。 11 比较LR（0）,SLR（1）,LR（1）和LALR（1）

分析表的优缺点

（1）LR（0）分析表局限性大，但其构造方法是其他构造方法的基础

（2）SLR分析表虽然不是对所有文法都存在，但这种分析表状态少，存储空间占用少，较易实现又极有实用价值。

（3）规范LR分析表，即LR（1）分析表，它的，它的分析能力最强，能适用于一大类文法，但是实现代价过高，主要是体积过大 （4）LALR分析表的能力介于SLR分析表和规范LR分析表之间，稍加努力，就可以高效的实现。

12比较LL（K）分析表与LR（K）分析法 共同点：（1）两者多借助于可能句柄左部的全部符号及向右看K个符号来确定所应执

行的唯一动作，识别过程严格地从左到右扫描，无回溯，效率高。（2）都能及时察觉错误2。（3）识别程序都能自动生成。 区别：（1）两者都是严格地从左到右扫描，名称中第一个L隐指这点，但LR分析技术利用的是最右推导（最左归约），由R隐指，LL（K）分析利用的是最左推导，由第二个L隐指。（2）LL（K）要求文法无左递归，满足无回溯的条件，而LR分析法则无此限制。（3）LL（K）是自上而下构造推导的，而LR（K）是自下而上构造归约的。 13语法制导翻译过程：对单词符号串进行语法分析，构造语法分析树，构造属性依赖图，遍历语法树并在语法树各结点处按语义规则计算顺序。

14静态语义检查：类型检查，控制流检查，一致性检查，相关名字检查，名字的作用域分析。

15引入中间代码的好处：

（1）便于进行与机器无关的代码优化工作 （2）使编译程序更容易改变目标机

（3）使编译程序的结构在逻辑上更为简单明确，以中间语言为界限，编译前端和后端的接口更清晰。 16编译程序分类 （1）诊断编译程序 （2）优化编译程序 （3）交叉编译程序 （4）可变目标编译程序

17编译程序工作过程5个阶段及其任务： （1）词法分析：任务是从左到右逐个字符的读入源程序，对构成源程序的字符流进行扫描和分解，进而识别一个个单词。

（2）语法分析：任务是根据语法规则，分析并识别出各种语法成分，并经行语法正确性检查。

（3）语义分析与中间代码生成：任务是对识别出的各种语法成分进行语义分析，并产生相应的中间代码。

（4）目标代码生成：任务是把中间代码转换成特定机器上的`低级语言代码。 18编译程序和解释程序

（1）编译程序需要在运行前将源代码译成目标代码，解释程序接受某个语言的程序并立即运行这个源程序

（2）二者存储组织有着很大不同，编译程序处理时存储区要存储编译用时需要的各种表格；解释程序将分析结果存放在源程序区

（3）编译程序动态性很差，可形成永久性可执行文件，解释程序动态性较好。

19程序性合计语言范型：

（1）强制（命令）式语言：c,fortron,pasal （2）函数式语言：ML,Lisp

（3）基于规则（逻辑）的语言：prolog （4）面向对象语言：Ada,c++,java

1.推导：

—自上而下的语法分析过程

—预测分析程序，递归下降分析法（最左推导）

—注：要求文法是LL(1)文法

2.归约：

—自下而上的语法分析过程

—简单优先分析法，算符优先分析法、LR分析法3

3.自下而上的语法分析过程思想

—自下而上的语法分析过程是一个最左归约的过程，从输入串开始。朝着文法的开始符号进行归约，直到到达文法的开始符号为止的过程 注意：输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列 。 即：自左至右把输入串的符号一个一个移进栈，在移进过程中不断查看栈顶符号串，一旦形成某个句型的句柄时，就将此句柄用相应的产生式左部替换（归约），若再形成句柄，就继续替换，直到栈顶不再形成句柄为止，然后继续移进符号，重复上面的过程直到栈顶只剩下文法的开始符号，输入串读完为止，这样就认为识别了一个句子。

1）初态时栈内仅有栈底符“#”，读头指在最左边的单词符号上 .

2）语法分析程序执行的动作：

a)移进：读入一个单词并压入栈内，读头后移；

b)归约：检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号.

c)识别成功：移进—归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符.

d)识别失败.

令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有 S αAδ且A β

则称β是句型αβδ相对于非终结符A的短语。

特别是，如果有 A β

则称β是句型αβδ相对于规则A→β的直接短语，一个句型的最左直接短语称为该句型的句柄。

注： 一个句型的语法树中任一子树叶节点所组成的符号串就是该句型的短语，当子树中不包含其他更小的子树时，该子树结点所组成的字符串就是该句型的直接（简单）短语。

素短语： 一个递归的定义，至少含有一个终结符，并且除它自身之外不在含有任何更小的素短语，（所谓最左素短语就是处于句型最左边的素短语）。

简单优先分析法：1.确定相邻文法符号之间的优先关系 在句型中，句柄内各相邻符号之间具有相同的优先级，相同优先级用“ ”

由于句柄要先归约,所以规定句柄两端符号的优先级要比位于句柄之外的相邻符号的优先级高,优先级低于表示为“﹤”,优先级高于表示为“ ＞”

某句型中:N1…-1< Ni …… Nj ＞ Nj+1…

定义：一个文法G，如果它不含e产生式，也不含任何右部相

同的不同产生式，并且它的任何符号对（X，Y）

X，Y是终结符或非终结符 ——或者没有关系，

——或者存在优先级相同或低于、高于等关系之一，

则这是一个简单优先文法。

1LR(0) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突状态。

2 SLR(1) 文法：该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态，冲突可用 FOLLOW 集解决。

该文法不是 SLR(1) 文法。

因为 FOLLOW(S)={a,b,#} ，所以无法解决冲突

3算符优先：（T） (<firstvt（T） lastvt（T）>) （6章）

1.静态语义检查包括： （1）类型检查 （2）控制流检查 （3）一致性检查 （4）相关名字检查 （5）名字的作用域分析

2.引入中间代码的好处：

（1）便于进行与机器无关的代码优化工作 （2）使编译程序更容易改变目标机

（3）使编译程序的结构在逻辑上更为简单

明确，以中间语言为界限，编译前端和后端的接口更清晰。

（1章） 1.源程序： 用编译语言或高级语言编写的程序

目标程序：用目标语言表示的程序

翻译程序： 将源程序转换为目标程序的程序。

2.编译程序分类 （1）诊断编译程序 （2）优化编译程序 （3）交叉编译程序 （4）可变目标编译程序

3.编译程序工作过程5个阶段及其任务： （1）词法分析：任务是从左到右逐个字符的读入源程序，对构成源程序的字符流进行扫描和分解，进而识别一个个单词。

（2）语法分析：任务是根据语法规则，分析并识别出各种语法成分，并经行语法正确性检查。

（3）语义分析与中间代码生成：任务是对识别出的各种语法成分进行语义分析，并产生相应的中间代码。

（4）目标代码生成：任务是把中间代码转换成特定机器上的低级语言代码。

4.编译程序和解释程序

（1）编译程序需要在运行前将源代码译成目标代码，解释程序接受某个语言的程序并立即运行这个源程序

（2）二者存储组织有着很大不同，编译程序处理时存储区要存储编译用时需要的各种表格；解释程序将分析结果存放在源程序区

（3）编译程序动态性很差，可形成永久性可执行文件，解释程序动态性较好。

5.程序性合计语言范型：

（1）强制（命令）式语言：c,fortron,pasal （2）函数式语言：ML,Lisp

（3）基于规则（逻辑）的语言：prolog

（4）面向对象语言：Ada,c++,java

6.构造编译程序必须掌握的三方面内容： （1）源程序 （2）目标语言 （3）编译方法

7.编译前端和后端

前端：通常指与源程序有关的编译部分，包括词法分析，语法分析，语义分析，特点是与源程序有关。

后端：与目标机有关的部分，包括中间代码生成，代码优化，目标程序生成，特点是与目标机有关。

1.推导：

—自上而下的语法分析过程

—预测分析程序，递归下降分析法（最左推导）

—注：要求文法是LL(1)文法

2.归约：

—自下而上的语法分析过程

—简单优先分析法，算符优先分析法、LR分析法3

3.自下而上的语法分析过程思想

—自下而上的语法分析过程是一个最左归约的过程，从输入串开始。朝着文法的开始符号进行归约，直到到达文法的开始符号为止的过程 注意：输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列 。 即：自左至右把输入串的符号一个一个移进栈，在移进过程中不断查看栈顶符号串，一旦形成某个句型的句柄时，就将此句柄用相应的产生式左部替换（归约），若再形成句柄，就继续替换，直到栈顶不再形成句柄为止，然后继续移进符号，重复上面的过程直到栈顶只剩下文法的开始符号，输入串读完为止，这样就认为识别了一个句子。

1）初态时栈内仅有栈底符“#”，读头指在最左边的单词符号上 .

2）语法分析程序执行的动作：

a)移进：读入一个单词并压入栈内，读头后移；

b)归约：检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号.

c)识别成功：移进—归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符.

d)识别失败.

令G是一个文法，S是文法的开始符号，假定αβδ是文法G的一个句型，如果有 S αAδ且A β

则称β是句型αβδ相对于非终结符A的短语。

特别是，如果有 A β

则称β是句型αβδ相对于规则A→β

的直接短语，一个句型的最左直接短语称为该句型的句柄。

注： 一个句型的语法树中任一子树叶节点所组成的符号串就是该句型的短语，当子树中不包含其他更小的子树时，该子树结点所组成的字符串就是该句型的直接（简单）短语。

素短语： 一个递归的定义，至少含有一个终结符，并且除它自身之外不在含有任何更小的素短语，（所谓最左素短语就是处于句型最左边的素短语）。

简单优先分析法：1.确定相邻文法符号之间的优先关系 在句型中，句柄内各相邻符号之间具有相同的优先级，相同优先级用“ ”

由于句柄要先归约,所以规定句柄两端符号的优先级要比位于句柄之外的相邻符号的优先级高,优先级低于表示为“﹤”,优先级高于表示为“ ＞”

某句型中:-1< Ni Nj ＞ Nj+

定义：一个文法G，如果它不含e产生式，也不含任何右部相

同的不同产生式，并且它的任何符号对（X，Y）

X，Y是终结符或非终结符 ——或者没有关系，

——或者存在优先级相同或低于、高于等关系之一，

则这是一个简单优先文法。

编译原理期末总结 [篇3]

1.简要说明语义分析的基本功能。

答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。

1.编译方式和解释方式的根本区别是什么？

编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。

2．编译程序有哪些主要构成成分？各自的主要功能是什么？ 编译程序的主要构成成分有：词法分析程序、语法分析程序、语义分析程序、中间代码 生成程序、代码优化程序、目标代码生成程序、表格管理程序及出错处理程序。 （1）词法分析程序：从左到右扫描源程序，识别单词及其有关属性； （2）语法分析程序：分析源程序的结构, 判别它是否为相应程序设计语言中的一个合法 程序； （3）语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息； （4）中间代码生成程序：将源程序变成一种内部表示形式；

3什么是解释程序？它与编译程序的主要不同是什么？ 解释程序接受某个语言的程序并立即运行这个源程序。它的工作模式是一个个的获取、 分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特 别适合程序员交互方式的工作情况。 而编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进 制代码程序，这个二进制代码程序再机器上运行以生成结果。 它们的主要不同在于：解释程序是边解释边执行，解释程序运行结束即可得到该程序的 运行结果， 而编译程序只是把源程序翻译成汇编或者二进制程序， 这个程序再执行才能得到 程序的运行结果。 （当然还有其他不同，比如存储组织方式不同）

什么是句柄？什么是素短语？

一个句型的最左直接短语称为该句型的句柄。

词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，

并转换成统一的内部表示(token)，送给语法分析程序。

编译程序的工作分为那几个阶段?

词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端)， 而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为

编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。

简述自下而上的分析方法。

开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。

4．简述代码优化的目的和意义。

一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目 标程序运行时所需要的时间短，同时所占用的存储空间少。

LR(0)分析器

每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再

向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否

已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是 移进还是按某一产生式进行归约等)。

第四章

1. 设有如下文法G[S]:

SaABbcd |

AASd |

BSAh | eC |

CSf | Cg |

(1) 求每个产生式的Predict集。

(2) 该文法是否为LL(1)文法？为什么？

答：(1)

Predict(SaABbcd)={a}

Predict(S )={#,d,f,a,h } Predict(AASd)={a,d} Predict(A )={h,a,d,b,e} Predict(BSAh)={a,d,h} Predict(B eC)={e} Predict(B )={b} Predict(CSf)={a,f} Predict(C Cg)={a,f,g} Predict(C )={g,b} (2)由于Predict(AASd) Predict(A )，所以该文法不是LL(1)文法。

三、 给定文法G[S]：

S→aA|bQ； A→aA|bB|b；B→bD|aQ ；Q→aQ|bD|b；D→bB|aA ；E→aB|bF F→bD|aE|b

构造相应的最小的DFA 。

解：先构造其NFA： 用子集法将NFA确定化：

将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。

令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b进行分割：

P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再用b进行分割： P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再用a、b 进行分割，仍不变。 再令｛０｝为A，｛1，2｝为B，｛3，4｝为C，｛5，6｝为D。 最小化为右上图。

四、对下面的文法G：

S→a | b | （T） T→T，S | S

(1) 消去文法的左递归，得到等价的文法G2；

(2) 判断文法G2是否LL（1）文法，如果是，给出其预测分析表。（15） G2：

S→a | b | （T）

T→ ST’

T’→，S T’ | ε

A→BCc | gDB

B→bCDE |ε C→DaB | ca D→dD |ε E→gAf | c

(1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集； (2)

是

二、设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)

答：

构造相应的正规式：(0|1)*1(0|1) (3分) NFA: (2分)

1

编译原理期末总结 [篇4]

第一章 引论

为什么要用编译器

与编译器相关的程序

翻译步骤

编译器中的主要数据结构

1、语言处理器

1、简单的说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成一个等价的、用另一种语言（目标语言）编写的程序。

2、编译器的重要任务之一就是报告它在翻译过程中发现的源程序中的错误。

3、使用编译器是为了提高编程的速度和准确度。

4、与编译器相关的程序：解释程序（interpreter）、汇编程序（assembler）、连接程序（linker）、装入程序（loader）、预处理器（preprocessor）、编辑器（editor）、调试程序（debugger）、描述器（profiler）、项目管理程序（project manager）。

5、解释器是另一种常见的语言处理器。它并不通过翻译的方法生成目标程序。从用户的角度来看，解释器直接利用用户提供的输入执行源程序中指定的操作。

Object Source

Program

Output

6、一个源程序可能被分割成多个模块，并存放于独立的文件中。把源程序聚合在一起的任务有时会由一个被称为预处理器（preprocessor）的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。

7、连接器（linker）能够解决外部内存地址的问题。

8、加载器（loader）把所有的可执行目标文件放到内存中执行。

2、一个编译器的结构

Front end Back end

1、将编译器看成黑盒，则源程序映射为在语义上等价的目标程序，而这个映射由两部分组成：分析部分和综合部分。

2、分析部分把源程序分解成多个组成要素，并在这些要素之上加上语法结构。

3、综合部分根据中间表示和符号表中的信息来构造用户期待的目标程序。

4、编译器的第一个步骤：词法分析（lexical）或扫描（scanning）。词法分析器读入组成源程序的字符流，并且将它们组成有意义的词素（lexeme）的序列。词法分析器产生词法单元（token）。

5、分隔词素的空格会被词法分析器忽略掉。

6、编译器的第二个步骤：语法分析（syntax）或解析（parsing）。语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。

7、语义分析（static semantic analysis）：语义分析器使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用。语义分析的一个重要部分是类型检查（type checking）。编译器检查每个运算符是否具有匹配的运算分量。

8、总的说，编译器的翻译步骤是：扫描程序----语法分析程序----语义分析程序----源代码优化程序----代码生成器----目标代码优化程序。

3、编译器结构中的主要数据结构

1、记号（token）

2、语法树（syntax tree）

3、符号表（symbol table）

4、常数表（literal table）

5、中间代码（intermediate code）

6、临时文件（temporary file）

4、将编译器分成了只依赖于源语言（前端（ front end））的操作和只依赖于目 标语言（后端（ back end））的操作两部分。

第二章 词法分析

扫描处理

正则表达式

有穷自动机

从正则表达式到D FA

利用L e x自动生成扫描程序

1、 Tokens记号标记：identifiers、keywords、integers、floating-point、symbols、strings、comments

1、 使用正则表达式去描述程序语言tokens

2、 一个正则表达式是归纳确定

3、 一个正则表达式R描述一组字符串集合L(R)

4、 L(R) = the language defined by R

5、 所有的token都能用正则表达式表示

2、 正则表达式：

1、 基本正则表达式：他们是字母比哦啊中的单个字符且自身匹配

2、 正则表达式运算：

1、 从各选择对象中选择，用元字符“|”表示

2、 连结，由并置表示（不用元字符）

3、 重复或“闭包”，由元字符“*”表示

3、从各选择对象中选择：

4、连结：正则表达式r和正则表达式s的连接可写作rs

5、重复：正则表达式的重复有时称为Kleene闭包（（Kleene）closure），写作r*

6、运算的优先和括号的使用：前面的内容忽略了选择、连接和重复的优先问题。

7、正则表达式的名字：为较长的正则表达式提供一个简化了的名字很有用处，这样就不再需要在每次使用正则表达式时书写常常的表达式本身了。

3、有穷自动机（有穷状态机）：是描述（或“机器”）特定类型算法的数学方法。

1、确定性有穷自动机：下一个状态由当前状态和当前输入字符惟一给出的自动机。

2、非确定性有穷自动机：由它产生的。

4、从正则表达式到DFA

1、构造一个个扫描程序的自动过程可分为3步

2、从正则表达式到

NFA

3、从NFA到

DFA

4、将DFA中的状态最小化

第三章 上下文无关文法及分析

分析过程

上下文无关文法

上下文无关语言的形式特性

分析树与抽象语法树

二义性

1、分析过程：

2、上下文无关文法：

3、分析树与抽象语法树：

4、二义性：

可生成带有两个不同分析树的串的文法称作二义性文法（ ambiguous grammar） 有两个解决二义性的基本方法。

其一是：设置一个规则，该规则可在每个二义性情况下指出哪一个分析树（或语法树）是正确的。

另一种方法是将文法改变成一个强制正确分析树的构造的格式，这样就可以解决二义性了。

第四章 自顶向下的分析

使用递归下降分析算法进行自顶向下的分析

LL(1)分析

First 集合和F o l l o w集合

1、使用递归下降分析算法进行自顶向下的分析

2、LL(1) 分析方法是这样得名的：第1个“L”指的是由左向右地处理输入（一些旧式的分析程序惯于自右向左地处理输入，但现在已不常用了）。第2个“L”指的是它为输入串描绘出一个最左推导。括号中的数字1意味着它仅使用输入中的一个符号来预测分析的方向。

3、定义：如果文法G相关的L L ( 1 )分析表的每个项目中至多只有一个产生式，则该文法 就是L L ( 1 )文法(LL(1) grammar)。