编译原理知识点整理

编译原理知识点
1.1 翻译程序的三种方式
1.编译：将高级语言编写的源程序翻译成等价的机器语言或汇编语言。

2.解释：将高级语言编写的源程序翻译一句执行一句，不生成目标文件，直接执行源代码文件。

3.汇编：用汇编语言编写的源程序翻译成与之等价的机器语言。

1.2 编译程序的五个阶段
1.词法分析：对源程序的字符串进行扫描和分解，识别出每个单词符号。

2.语法分析：根据语言的语法规则，把单词符号分解成各类语法单位。

3.语义分析与中间代码生成：对各种语法范畴进行静态语义检查，若正确则进行中间代码翻译。

4.代码优化：遵循程序的等价变换规则。

5.目标代码生成：将中间代码变换成特定机器上的低级语言代码。

2.1.1 字母表
1.定义：字母表是有穷非空的符号集合。

2.表示：通常用字母表大写字母A，B，…Z和希腊字母Σ表示。

eg：A={0,1}，Σ={a,b,c,d}
3.说明
1）字母表包含了语言中所允许出现的一切符号。

2）字母表中的符号也称字符。

2.1.2 符号串
1.定义：由字母表中的符号组成的有穷序列。

2.表示：通常由t，u，v，w，x，y，z等小写英文字母来表示。

3.说明
1）符号串由构成的符号的种类、数量、顺序共同决定。

2）不包含任何符号的符号串称为空符号串，简称空串，用ε表示。

4.对于给定的字母表Σ，符号串的递归定义如下：
1）ε是Σ上的一个符号串。

2）若x是Σ上的符号串，a是Σ的符号，则xa是Σ上的符号串。

并规定。

编译原理部分知识点①编译程序的工作过程一般划分为5个阶段：词法分析，语法分析，语义分析与中间代码生成，优化，目标代码生成【还有表格管理还有出错管理】②编译器常用的语法分析方法两种。

自顶向下，自下而上分析方法。

LR方法（自下而上），LL（1）属于什么方法（自上而下）、算符优先分析法（自下而上）③概念：句子（仅含终结符号的句型是一个句子）、最左素短语（语法树中最左边的素短语为最左素短语）、句柄、（一个句型的最左直接短语）二义：（如果一个文法存在某个句子对应两颗不同的语法树，则称这个文法是二义的）正规文法（左线性文法和右线性文法统称为正规文法）④程序语言的单词符号分为5种（关键字、标识符、常数、运算符、界符）⑤属性通常分为两类（综合属性）（继承属性）⑥LR分析器的实质是一个后进先出确定有限状态自动机。

⑦常用的参数传递方式(传地址),（传值),(传名）（传结果）⑧一个LL(1)文法一定是无二义的。

⑨解释程序、编译处理语言时的特点（源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。

①边解释边执行②有利于程序的调试③ 1次运算）⑩语法分析器作用（按文法的产生式，识别输入符号串是否为一个句子）⑪任何算符优先文法与优先函数的关系（任何算符优先文法可能有若干个优先函数，不一定存在优先函数）⑫确定有限自动机的化简是要实现目的(寻找一个状态数比M少的DFA M’,使得L(M)=L(M’))⑬间接三元式表示法的优点为(采用间接码表,节省三元式空间,便于优化处理)⑭词法分析器任务（从左到右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序）2、设文法G（S）S→(T)|aT→T+S | S计算FIRSTVT和LASTVT;构造优先关系表。

(1) FIRSTVT(S)={a, ( }FIRSTVT(T)={+, a a, (}LASTVT(S)={a, ) }LASTVT(T)={+, a, )}(2)a + ( )a .> .>+ <. .> <. .>( <. <. <. =.) .> .> >.3、设文法G(S):S→( T ) | aS | aT→T, S | S消除左递归和提取公因子；构造相应的FIRST和FOLLOW集合；构造预测分析表。

第1章：1、名词：解释器/解释程序 interpreter；编译器/编译程序 compiler；翻译器/翻译程序translator。

三者的区别与联系。

虚拟机（如JAVA虚拟机JVM、Tiny语言虚拟机）是哪种程序？（1）解释器（也称为解析程序）则是只在执行程序时,才一条一条的解释成机器语言给计算机来执行,所以运行速度是不如编译后的程序运行的快的.（2）编译器（也称为编译程序）是把源程序的每一条语句都编译成机器语言,并保存成二进制文件,这样运行时计算机可以直接以机器语言来运行此程序,速度很快;（3）翻译器（也称为翻译程序）是一种系统程序，它将计算机编程语言编写的程序翻译成另外一种计算机语言的一般来说等价的程序，主要包括编译程序和解释程序，汇编程序也被认为是翻译程序。

程序的最初形式称为源程序或者源代码，翻译后的形式被称为目标程序或者目标代码。

大多数翻译程序是将高级语言编写的程序翻译为机器语言形式的可执行程序。

但是也有些翻译程序将源程序翻译成其他高级语言或者字节码等中间形式。

（4）解释器翻译源程序时不生成独立的目标程序，而编译器则将源程序翻译成独立的目标程序。

解释器是另外种形式的语言处理器，它相当于不生成上面的目标程序，直接将输入“放到”源程序中，然后经过解释器，就得到了输出。

通常情况下，编译过程比解释过程更快，但解释器能够有更好的错误诊断，因为解释器是逐句进行解释的。

编.0译器和解释器可以结合起来进行处理，Java语言处理器就是其中的代表，其过程是源程序经过翻译器处理后得到中间程序，也被称作字节码（bytecode），然后和输入共同加入到虚拟机（virtual machine）的前端，得到输出，其前一部分用到编译器，后一部分用到解释器，这样做的好处是一个机器解释的代码可以应用在另外的机器上，甚至可以延伸到网络上。

2、编译过程图示 P5 图1-1第3章：1、Chomsky语言文法分类，程序语言的语法是哪一类，词法是哪一类，其产生式有什么特点。

编译原理重点第一章1.编译程序是计算机系统经典、核心的系统软件2.计算机需要把高级编程语言的程序翻译成机器语言代码或汇编语言才能运行3.如果源语言是高级编程语言，目标语言是机器代码和汇编语言这样的低级语言，这类翻译程序就叫做编译程序或编译器4.运行高级语言程序的另一种方式是解释执行，它需要的翻译程序不是编译程序，而是解释程序5.解释程序不产生源程序的目标代码，而是对源程序逐条语句进行分析6.Basic和多数脚本语言都是按照解释方式运行的7.解释方式的主要优点是便于对源程序进行调试和修改，但是其加工过程降低了程序的运行效率8.Java语言同时具有编译执行方式和解释执行方式9.9．计算机程序的编译过程类似，一般分为五个阶段：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成10.词法分析的任务是逐步地扫描和分解构成源程序的字符串，识别出一个一个的单词符号或符号11.语法分析的任务是在词法分析的基础上12.语法分析不考虑语义，形式上构成13.语义分析的任务是检查程序语义的正确性，解释程序结构的含义14.语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。

15.语义分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。

所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序16.代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码17.编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序18.编译程序结构包括五个基本功能模块和两个辅助模块19.编译划分成前端和后端。

20.编译前端只依赖于源程序，独立于目标计算机。

编译前端的工作包括词法分析、语法分析、语义分析、中间代码生成、及其优化，文法错误的处理和符号表的组织也在编译前端完成。

编译原理知识点总结编译原理是计算机科学中的一个重要领域，它研究的是将高级程序语言转化为可执行目标代码的原理和方法。

在软件开发过程中，编译器起着至关重要的作用，因此了解编译原理的知识点对于理解和优化程序的性能至关重要。

1. 词法分析：词法分析是编译器的第一步，它将源代码划分为一个个的词法单元，如关键字、标识符、运算符等。

词法分析器通过正则表达式和有限自动机来实现，可以有效地将源代码转化为词法单元流。

2. 语法分析：语法分析是编译器的第二步，它通过语法规则将词法单元流转化为抽象语法树（AST）。

语法分析器使用上下文无关文法来描述语言的语法结构，并通过LL（1）分析、LR（1）分析等算法来构建抽象语法树。

3. 语义分析：语义分析是编译器的第三步，它对抽象语法树进行语义检查和类型推断。

语义分析器会检查变量的作用域、类型是否匹配等语义错误，并生成中间代码或目标代码。

4. 中间代码生成：中间代码生成是编译器的一项重要任务，它将抽象语法树转化为中间表示形式，如三地址码、四地址码等。

中间代码是一种抽象的低级语言，便于后续的优化和目标代码生成。

5. 代码优化：代码优化是编译器的关键环节，它通过对中间代码进行分析和优化，提高程序的执行效率和资源利用率。

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

6. 目标代码生成：目标代码生成是编译器的最后一步，它将中间代码转化为目标机器代码。

目标代码生成器根据目标机器的特性和指令集，生成可执行的目标代码。

7. 符号表管理：符号表是编译器中用于管理变量、函数等符号信息的数据结构。

符号表包含了符号的名称、类型、作用域等信息，编译器在词法分析、语法分析和语义分析阶段使用符号表进行符号的查找和管理。

8. 错误处理：错误处理是编译器中一个重要的组成部分，它负责检测和报告源代码中的错误。

编译器需要能够准确地定位错误的位置，并给出有意义的错误信息，帮助程序员快速定位和修复错误。

编译原理涉及的知识点非常广泛，上述仅是其中的一部分。

编译原理要点整理//红色字体标注的是重点中的重点，大题的归宿第一章引论1.翻译器，编译器的定义2.编译器工作步骤和流程3.编译器前端后端的概念，理解为什么要有前端后端4.“遍”的概念第二章词法分析1.词法分析器的定义2.词法分析器所要完成的任务3.记号，模式，词法单元概念区分4.串的运算（和，连接，指数，闭包，正闭包）5.正规定义6.转换图（注意开始状态和结束状态以及需要将指针回退的状态）7.不确定的有限自动机（NFA）定义8.确定的有限自动机（DFA）定义9.从正规式到NFA（明确通过正规式如何构造连接运算，和运算，闭包运算的NFA）10.此方法产生的NFA的性质11.从NFA到DFA（子集构造法）12.DFA的化简（合并不可区别状态）13.从语言描述直接到DFA14.了解Lex学完本章：能语言描述改写成正规定义，能将正规定义转化为语言描述，给出一个正规式，能转换成相应的NFA，DFA并化简。

第三章语法分析1.上下文无关文法定义2.区分句子和句型3.最左推导&& 最右推导4.分析树5.文法二义性6.消除左递归&& 提左因子7.了解语言鸟瞰（0型文法：短语文法；1型文法：上下文有关文法；2型文法：上下文无关文法；3型文法：正规式）8.FIRST集合&& FOLLOW集合定义及计算方法9.LL（1）文法定义10.了解自上而下的递归下降的预测分析11.自上而下非递归的预测分析（详细明确预测分析器接受某一输入串时的具体过程，明确栈如何变化，输入输出如何变化）12.预测分析表的构造13.句柄的概念14.自下而上的分析方法：用栈实现移近-归约分析（详细明确预测分析器接受某一输入串时的具体过程，明确栈如何变化，输入输出如何变化）15.LR文法和LR分析算法16.构造SLR分析表（从文法构造识别活前缀的DFA（LR（0）项目集规范族），从DFA构造SLR分析表）17.构造规范的LR分析表（从文法构造识别活前缀的DFA（LR（1）项目集规范族），从DFA构造规范的LR分析表）18.构造LALR分析表（从文法构造识别活前缀的DFA（合并同心的LR（1）项目集），从DFA构造规范的LR分析表）（合并同心项目集可能会引起归约-归约冲突，不会引起新的移进-归约冲突）学完本章：能计算FIRST集合和FOLLOW集合；给定一个文法，能判断是否是LL(1)文法，并为其构造分析表；能构造LR(1)文法的三种预测分析表；明确移近归约分析中的每一个步骤，明确栈如何变化。

《编译原理》知识点总结目录第一章引论第二章高级语言及其语法描述第三章语法分析——自上而下分析第四章属性文法和语法制导翻译第五章语义分析和中间代码产生第六章优化第一章引论一．编译程序(compiler):把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序二．编译程序的工作的五个阶段:词法分析、语法分析、中间代码产生、优化、目标代码产生1.词法分析任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。

依循的原则：构词规则描述工具：有限自动机FOR I := 1 TO 100 DO保留字标识符等符整常数保留字整常数保留字2.语法分析任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。

依循的原则：语法规则述工具：上下文无关文法3.语义分析与中间代码产生任务:对各类不同语法范畴按语言的语义进行初步翻译。

（变量是否定义、类型是否正确等）依循的原则：语义规则中间代码:三元式，四元式，逆波兰记号，树形结构等。

是一种独立于具体硬件的记号系统。

例：将Z:=X + 0.618 * Y 翻译成四元式为(1) * 0.618 Y T1(2) + X T1 T2(3) := T2 _ Z4. 优化任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。

依循的原则：程序的等价变换规则FOR K:=1 TO 100 DOBEGINM := I + 10 * K;N := J + 10 * K;END4.目标代码产生任务: 把中间代码变换成特定机器上的目标代码。

依赖于硬件系统结构和机器指令的含义目标代码三种形式:a)绝对指令代码: 可直接运行b)可重新定位指令代码: 需要连接装配c)汇编指令代码: 需要进行汇编第二章高级语言及其语法描述2.1.1语法词法规则：单词符号的形成规则。

a)单词符号是语言中具有独立意义的最基本结构。

编译原理中重点整理1.翻译程序：将某一种语言（源语言）程序转换为与其逻辑上等价的另一种语言（目标语言）程序。

编译程序：源语言为高级语言，目标语言为汇编语言或机器语言的翻译程序。

汇编程序：源语言为汇编语言，目标语言为机器语言的翻译程序。

解释程序：源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。

2.解释器与编译器的主要区别在于：运行目标程序时的控制权在解释器而不在目标程序。

3.编译程序的工作过程可划分五个阶段：①词法分析：从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而识别出一个个单词（也称单词符号或简称符号）②语法分析：在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等③语义分析和中间代码生成：语义分析是在语法分析程序确定出语法短语后，审查有无语义错误，并为代码生成阶段收集类型信息。

完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记号系统。

④代码优化：为了使生成的目标代码更为高效，可以对产生的中间代码进行变换或进行改造，这就是代码的优化。

⑤目标代码生成：目标代码生成阶段的任务就是是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。

4.前端(Front-End)——与目标机无关的部分后端(Back-End )——与目标机有关的部分5.编译系统：编译程序与运行系统合称编译系统6.遍：对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标程序。

7.文法是一个四元组：G[S]=(VN, VT, P, S)VN：非终结符集合；VT ：终结符集合；P ：产生式集合（α→β或α∷=β）；S ：开始符号(或称根符号，识别符号)。

若S ->α,α∈V*，则称α为文法G的句型若S ->α,α,α∈VT*，则称α为文法G的句子语言是所有句子构成的集合，它是所有终结符号串所组成的集合VT*的子集，即L(G) VT* 8.0型文法又叫短语文法，它所确定的语言称为0型语言。

编译原理编译原理编译器是什么？知识树基本过程词法分析语言正则语言正则定义如何让计算机识别用正则表达式定义的语言NFA 非确定有限自动机DFA 确定有限自动机正则表达式转 NFA直接用 NFA 识别语言直接从正则表达式转 DFA最小化 DFA 的算法语法分析语法的形式化：上下文无关文法推导推导 derivation字符串符号文法语法分析树文法的二义性文法二义性的消除消除左递归消除直接的左递归消除间接的左递归计算 first() 集合计算 follow(A) 集合LL(1) 文法的分析表自底向上的文法分析SLR 文法LR(0) 项扩充文法自动机的过程Closure of Item SetsSLR 分析表的构建（重点）LR(1) 文法构造 LR(1) 分析表缺点LALR 文法语法制导定义基本思想举例语法制导定义继承属性翻译模式再次举例：中缀转后缀扩展文法扩展语法树通过自顶向下的分析来实现先序遍历实现先序遍历Evaluation Order and Dependency Graphs 显式的语法分析树S-属性制导定义L-属性制导定义需要满足三条规则：语义分析和中间代码生成Introduction3 地址代码1. 类型和声明举例来说明翻译过程2. 赋值和表达式类型检查3. 布尔表达式和流控制流控制的语法制导定义布尔表达式的语法制导定义运行时环境内存管理stack 和活动记录活动树活动记录（帧）进程内通信堆管理多线程垃圾回收代码生成指令选择寄存器分配和赋值指令调度抽象目标状态机指令集基本块流图生存期和后续使用信息简单代码生成器代码优化窥孔优化局部优化控制流分析和循环优化消除共同子表达式✔编译器是什么？编译器是一个程序，主要是用来把源程序转换成另外一种计算机语言的程序。

语言编译的全过程：✔知识树编译原理正则语言识别 T oken上下文无关文法CFG 构建语法分析树语法制导翻译生成中间代码代码优化代码生成编译原理是一种语言处理器，它完成了很多工作。

编译原理知识点(总7页) -本页仅作为预览文档封面，使用时请删除本页-1.解释程序：不生成目标代码编译程序：生成目标代码2.编译程序组成：8个分析< 前端 >：(词法分析程序、语法分析程序、语义分析程序、中间代码生成程序)综合< 后端 >：（代码优化程序、目标代码生成程序）贯穿始末：表格管理程序、出错处理程序3.文法四元组：终结符号集合Vt 、非终结符号集合Vn、产生式集合P、识别符号(开始符号)SV T∩V N＝Φ文法 -> 语言（推导、规约）唯一；语言 -> 文法（凑规则）不唯一。

4.文法分类：0型文法(短语结构文法)：左侧至少含有一个非终结符1型文法(上下文有关文法)：左侧长度 <= 右侧长度 S->ε除外， S不能出现在右侧2型文法(上下文无关文法)：左侧只能有一个非终结符 ( 语法分析 )3型文法(正规文法)：A-> aB A->a 右线性； ( 词法分析 )A->Ba 或A->a 左线性（看非终结符位置）5.A*＝ A0 ∪A+ A0 ＝{ε} != { } ＝Φ空集A+ ＝ AA* ＝ A*A6.句型：符号串x是从识别符号S推导出来的，x称为一个句型句子：x仅由终结符号组成，仅含终结符号的句型是一个句子短语：子树的末端（叶子）从左至右连成的串（包括整棵语法树）简单子树：只含有单层分枝的子树直接短语( 简单短语 )：由简单子树的叶子组成句柄：最左边的直接短语（不一定含终结符）素短语：至少含有一个终结符的短语，并且除它自身之外不再含任何更小的素短语最左素短语：最左边的素短语短语：P（相对于T、E）、 P+T（相对于E）、i（相对于P、F）、P+T+i（相对于E）直接短语：P、i 句柄：P (最左边的直接短语)素短语：P+T 、i （至少含有一个终结符的短语）最左素短语：P+T7.二义性文法：有两个不同的最左推导或有两个不同的最右推导或能产生两棵语法树8.文法产生式正规式规则1 A xB B y A = xy规则2 A xA|y A = x*y 右线性A Ax|y A = yx* 左线性规则3 A x A y A = x|y9.DFA 初态唯一，转换函数为单值映射表示方式：转移矩阵、状态转换图状态转换图上若存在一条从初态到某一终态的道路，且这条路上所有弧的标记符连成的字符串为t，则称t被DFA接受。