编译原理知识点整理

编译原理知识点
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接受。

编译原理期末总结编译原理是计算机科学中的一门重要课程，它涵盖了从程序的源代码到可执行代码的整个过程。

在本学期的学习中，我通过理论学习和实践项目的方式，深入了解了编译原理的重要概念和实践技术，对编译器的原理和设计有了更深入的了解。

在本文中，我将对编译原理的重要内容进行总结并分享我的学习收获。

一、编译原理的基础知识在学习编译原理之前，我们需要了解计算机的基础知识和概念，例如计算机的组成原理、计算机体系结构和计算机操作系统等。

这些基础知识对我们理解编译原理起到了重要的辅助作用。

1. 计算机的组成原理计算机由硬件和软件两部分组成，硬件指的是计算机的物理部分，包括CPU、内存、硬盘等。

而软件指的是运行在计算机上的程序。

2. 计算机体系结构计算机体系结构是计算机硬件和软件之间的接口，包括指令集体系结构和系统结构。

指令集体系结构定义了计算机的机器语言和指令集编码规范，系统结构定义了计算机的组成和连接方式。

3. 计算机操作系统计算机操作系统是一个管理和控制计算机硬件资源的软件，它提供了基本的功能，如进程管理、内存管理和文件管理。

二、编译原理的基本概念编译原理是关于将高级语言编写的程序转化为机器语言的过程，它包括了词法分析、语法分析、语义分析、中间代码生成和代码优化等阶段。

1. 词法分析词法分析是将源代码中的字符流转化为词法单元流的过程。

在词法分析阶段，编译器会识别出关键字、标识符、常量等词法单元，并对它们进行标记和分类。

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

在语法分析阶段，编译器会检查源代码是否符合语法规则，并将它们组织成一个由语法规则决定了语法结构的树状结构。

3. 语义分析语义分析是对语法树进行语义检查和语义修正的过程。

在语义分析阶段，编译器会检查类型一致性、变量声明和作用域等语义规则，并生成符号表来存储变量和函数的信息。

4. 中间代码生成中间代码生成是将源代码转换为一种中间表示形式的过程。

第一章引言1.从面向机器的语言到面向人类的语言汇编指令：用符号表示的指令被称为汇编指令汇编语言：汇编指令的集合称为汇编语言2.语言之间的翻译转换(也被称为预处理)：高级语言之间的翻译，如FORTRAN到ADA 的转换编译：高级语言可以直接翻译成机器语言，也可以翻译成汇编语言，这两个翻译过程称为编译汇编：从汇编语言到机器语言的翻译被称为汇编交叉汇编：将一个汇编语言程序汇编成为可在另一机器上运行的机器指令成为交叉汇编反汇编：把机器语言翻译成汇编语言反编译：把汇编语言翻译成高级语言3. 编译器与解释器（1）语言翻译的两种基本形态解释器与编译器的主要区别:运行目标程序时的控制权在解释器而不在目标程序.（2）各自特点•编译器:工作效率高,即时间快、空间省；交互性与动态性差,可移植性差.•解释器:工作效率低,,即时间慢、空间费；交互性与动态性好,可移植性好.共同点:均完成对源程序的翻译.差异:编译器采用先翻译后执行,解释器采用边翻译边执行.4. 编译器的工作原理与基本组成（0）通用程序设计语言的主要成份声明＋操作＝完整定义（1）以过程为基本结构的程序设计语言的组成•声明性语句：提供操作对象的性质，如数据类型、值、作用域等；•操作性语句：确定操作的计算次序，完成实际操作。

•过程定义= 过程头＋过程体（2）以阶段划分编译器注：符号表管理器和出错处理贯穿编译器工作的各个阶段.（3）编译器各阶段工作1> 词法分析：词法分析的输入是源程序,输出是识别出的记号流.目的是识别单词. 至少分以下几类：关键字(保留字)、标识符、字面量、特殊符号2> 语法分析：输入是词法分析器返回的记号流,输出是语法树.目的是得到语言结构并以树的形式表示.对于声明性语句,进行符号表的查填,对于可执行语句,检查结构合理的表达式运算是否有意义.3> 语义分析：根据语义规则对语法树中的语法单元进行静态语义检查,如类型检查和转换等,目的在于保证语法正确的结构在语义分析上也是合法的.4> 中间代码生成(可选)：生成一种既接近目标语言,又与具体机器无关的表示,便于代码优化与代码生成.(到目前为止，编译器与解释器可以一致)5> 中间代码优化(可选)：局部优化、循环优化、全局优化等；优化实际上是一个等价变换，变换前后的指令序列完成同样的功能，但在占用的空间上和程序执行的时间上都更省、更有效6> 目标代码生成：不同形式的目标代码—汇编语言形式、可重定位二进制代码形式、内存形式(Load-and-Go)7> 符号表管理：合理组织符号,便于各阶段查找\填写等.8> 出错处理：动态错误：源程序中的逻辑错误，发生在程序运行的时候。

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

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

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

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

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

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

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

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

2.1 符号串和语言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是Σ上的符号串。

并规定εa=a，aε=a3）y是Σ上的符号串，当且仅当y由1）和2）导出。

5.子符号串：一个非空符号串中若干连续符号组成的部分。

6.字符串的前缀和后缀若z=abd是字母表Σ={a,b,c,d}上的符号串，则ε，a，ab，abd都是z的前缀；ε，d，bd，abd都是z的后缀。

（正序逆序排序即可，前缀为正序排序的所有子串，后缀为逆序排序的所有子串）7.符号串之间的运算1）连接：符号串x，y的连接xy就是把符号串y写在x后面得到的字符串。

名词解释编译：编译程序的翻译过程。

词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成.语言：由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)={x|S =>* x，其中S为文法的开始符号，且x ∈VT*}二义文法：若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。

或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。

二义语言：如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。

属性文法：属性文法(attribute grammar)是一个三元组： A=(G,V,F),其中G:是一个上下文无关文法,V:有穷的属性集,F:关于属性的属性断言或一组属性的计算规则(称为语义规则) 。

活动记录：一个过程的一次执行所需要的信息，使用一个连续的存储区来管理这个区（块），叫做一个活动记录AR。

词法：规定什么是正确的单词，boy 不能写成byo等等。

语法（文法）：是指一组规则，用它可以形成和产生一个合适的程序。

（定义什么样的符号序列是合法的）语义：自然语言中词语的意义，逻辑形式系统中符号的解释。

（定义什么样的符号序列是有含义的）句子：有文法G[s]，若S =>* x，且x∈VT*，则称x是文法G的句子。

句型：有文法G[s]，若S =>* x，则称x是文法G的句型。

语法树：设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树。

最左/最右推导：在推导的任何一步α β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换。

自上而下分析：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。

自下而上分析：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。

短语：存在文法G[s],S =>* αAδ且 A =>+ β，则称β是句型αβδ相对于非终结符A的短语。

第一、二章引论、高级语言及其描述1、用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程叫做编译），才能由计算机执行。

执行转换过程的程序叫做编译程序。

汇编程序是指没有编译过的汇编语言源文件。

编译程序转换过的叫做目标程序，也就是机器语言。

2、编译程序是一种翻译程序3、通常一个编译程序中，不仅包含词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理，其中中间代码生成和代码优化不是每个编译程序都必须的。

4、产生式是用于定义语法成分的一种书写规则。

5、四种类型的文法的主要特点：6、解释程序和编译程序的区别在于是否生成目标程序。

7、中间代码有：逆波兰记号、树形表示、三元式、四元式等形式8、语法制导翻译即可用来产生中间代码，也可以用来产生目标指令，甚至可用来对输入串进行解释执行。

第三章词法分析3.1 确定的有限自动机DFA M是一个五元组M =（S，∑，δ ，S0 ，F )(1) S 是一个非空有限集，它的每个元素称为一个状态(2)∑是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表(3)δ是状态转换函数，是在S×å→S上的单值映射(4) s0 s0∈S，是唯一的一个初态(5) F F含于S，可空,是一个终态集,终态也称可接受状态或结束状态3.2 一个NFA M是五元式M=(S,S,δ,S0,F)（1）S 有穷非空状态集合（2）∑ 有穷的输入字母表集合（3）δ 从S´∑*到S的子集的映射（4）S0Í 是S的非空子集，称为初始状态集合（5）F Í 是S的子集(可空),称为终止状态集合3.3 DFA与NFA特点比较DFA特点：1. 初态唯一2. 输入字符不包括空符号串3. 有向边上只有一个字符4. 一个状态对某个字符最多只有一条出边NFA特点：1. 初态不唯一2. 输入字符包括空符号串3. 有向边上可以为字符串4. 一个状态对某个字符可能有多条输出边，即状态的后继不唯一3.4 词法分析是基于正则文法进行，即识别的单词是该文法的句子；语法分析基于上下文无关文法进行，即识别的是该类文法的句子。

编译原理概念汇总一、编译原理概述编译原理是计算机科学中的一个重要分支，主要研究如何将高级语言编写的源代码转换成计算机能够执行的机器码。

这个过程涉及到多个阶段，包括词法分析、语法分析、中间代码生成、优化和目标代码生成等。

二、源代码到目标代码的转换编译过程的核心是将源代码转换成目标代码。

这个过程通常包括词法分析、语法分析、语义分析和生成目标代码等阶段。

词法分析是将源代码分解成一系列的记号，语法分析是将记号组合成语法结构，语义分析是检查这些结构是否有意义，最后生成目标代码是将这些结构转换成机器码。

三、词法分析词法分析是编译过程中的第一个阶段，主要任务是将源代码分解成一个个的记号。

这个过程通常使用词法扫描器或词法器完成，它按照一定的规则将源代码分解成一个个的记号，每个记号代表一个单词或符号。

四、语法分析语法分析是编译过程中的第二个阶段，主要任务是将记号组合成语法结构。

这个过程通常使用语法分析器完成，它按照一定的语法规则将记号组合成语法结构，这些结构代表了源代码的语义。

五、中间代码生成在完成语法分析后，通常会生成中间代码，也称为抽象语法树或中间表示。

这个过程是将语法结构转换成一种更易于处理的表示形式，以便进行后续的优化和目标代码生成。

中间代码生成是编译器设计中一个非常重要的技术，它可以提高编译器的灵活性和可扩展性。

六、优化优化是编译过程中的一个重要阶段，主要任务是对中间代码进行优化，以提高生成的目标代码的执行效率。

这个过程通常包括消除无用代码、简化计算、优化循环结构等操作，以减小目标代码的大小和提高程序的运行效率。

编译器优化技术可以显著提高程序的性能和效率。

七、目标代码生成目标代码生成是编译过程中的最后一个阶段，主要任务是将中间代码转换成机器码或可执行文件。

这个过程通常使用代码生成器完成，它根据中间代码和目标机器的指令集，生成可在特定硬件平台上运行的机器码或可执行文件。

目标代码生成的目标是生成高效、低耗的机器码，同时保证程序的正确性和可维护性。