机器语言（1940s）→ 汇编语言（1950s早期）→ 高级程序设计语言（1950s后期）
按描述方式：
按类型检查：
按应用领域：
按实现方式：编译型/解释型
编译（翻译）程序：把用某一种程序设计语言写的源程序翻译成等价的另一种语言程序（目标语言）的程序，是沟通计算机硬件与用户之间的渠道。
源程序：被编译的程序，一般由汇编语言/高级程序设计语言的源语言编写。
目标程序：经过编译程序翻译后生成的程序，可以用机器语言、汇编语言甚至高级语言或用户自定义的某类中间语言来描述。
宿主机（目标机）：运行编译程序的计算机。
宿主语言（实现语言）：编译程序实现的语言。
T型图：左上角表示源语言，右上角表示目标语言，底部表示实现语言。
例如：对一个用Z语言实现的，从源语言X到目标语言Y的编译程序，可用下图的T型图表示，记作CZXY。
交叉编译：由于目标机B的指令系统与宿主机A的指令系统不用，要用运行在宿主机A上的某编译程序为另一台机器B生成目标代码。
例如：设机器B上已有源语言S的编译器CBSB，现要利用已实现的语言S为另一个源语言L编写一个交叉编译器，并生成机器A的目标代码，即创建CSLA。若CSLA通过CBSB来运行得到编译器CBLA，那么这就是一个运行于机器B上将源语言L翻译成机器A的目标代码的编译器，可用下图的叠放在一起的T型图表示。
叠放的T型图的结合规则需要满足以下条件：
从源语言类型或实现机制不同的角度：
从对源程序执行途径不同的角度：
从编译程序的用途、实现技术等侧重面：
编译程序的工作过程是，从输人源程序开始到输出目标程序为止，经过词法分析、语法分析、语义分析与中间代码生成、代码优化及目标代码生成5个阶段。表格管理和出错处理是编译程序的辅助模块，可在编译的任何阶段被调用，辅助完成编译功能，称为公共辅助程序。
词法分析阶段的任务是对输人的符号串形式的源程序进行最初的加工处理。它依次扫描读入的源程序中的每个字符，识别出源程序中有独立意义的源语言单词，用某种特定的数据结构对它的属性予以表示和标注。词法分析实际上是一种线性分析，词法分析阶段工作依循的是源语言的词法规则。
语法分析阶段的任务是在词法分析基础上，依据源语言的语法规则，对词法分析的结果进行语法检查，并识别出单词符号串所对应的语法范畴，类似于自然语言中对短语、句子的识别和分析。通常将语法分析的结果表示为抽象的分析树(parser tree)或称语法树(syntax tree),它是一种层次结构的形式。
语义分析阶段的任务是，依据源语言限定的语义规则对语法分析所识别的语法范畴进行语义检查并分析其含义，初步翻译成与其等价的中间代码。语义分析是整个编译程序完成的最实质性的翻译任务。
代码优化是为了改进目标代码的质量而在编译过程中进行的工作。代码优化可以在中间代码或目标代码级上进行，其实质是在不改变源程序语义的基础上对其进行加工变换，以期获得更高效的目标代码。而高效一般是对所产生的目标程序在运行时间的缩短和存储空间的节省而言。
在前述的例子中，C语句“a[index]=123”的中间代码经常量合并这类优化后，不生成“123”的中间代码，仅产生将“12*3”的结果值“36”赋给标识符“a[index]”的中间代码，即“a[index]=36”,这是在中间代码上的代码优化。
目标代码生成作为编译程序的最后阶段，该阶段的任务是，根据中间代码及编译过程中产生的各种表格的有关信息，最终生成所期望的目标代码程序。一般为特定机器的机器语言代码或汇编语言代码，需要充分考虑计算机硬件和软件所提供的资源，以生成较高质量的目标程序。
编译程序在对源程序的分析过程中，需要保留和管理一系列表格，以登记源程序中的数据实体的有关信息和编译各阶段所产生的信息，以便于完成从源程序到目标程序的等价变换。随着编译过程的进行需要不断建表、查表和填表，或修改表中某些数据，或从表中获取有关信息，支持编译的全过程。
对源程序中可能存在的错误进行自动检查、分析（定位、定性）和报告，并将错误限制在尽可能小的范围内，保障恢复编译。
遍设置的考虑因素：
通常以语法分析为主控程序，在语法分析过程中随时调用词法分析程序以得到语法分析所需的字符串（单词符号），一旦语法分析程序分析、识别了一个语法范畴，即去调用语义处理程序（与代码生成程序合为一体）生成相应语法范畴的目标程序。
源语言：编译程序处理的对象
目标语言与目标机：编译程序处理的结果和运行环境
编译方法与工具：生成编译程序的关键
巴科斯-诺尔范式表示法，简称BNF，各符号含义如下：
字母表是元素的非空有穷集合。字母表中的元素称为该字母表的一个字母，也可叫做符号/字符，因此字母表也称为符号/字符集。
字母表包含了语言中允许出现的全部符号，不同语言可以有不同的字母表。
已知 ∑ 是字母表，∑上的字符串的集合 ∑* 可递归定义如下：
∑* 中的元素称为字符串，也可叫做符号串、串或句子，它总是建立在某个特定的字母表上，且仅由字母表上的有穷多个符号组成。
如果某符号串 ω 中有 m 个字母表中的符号，则称其长度为 m，表示为 |ω| = m，定义空串 ε 的长度为 0 。
设有符号串 ω，把从 ω 的尾部（首部）删去 0 个或若干个符号之后剩余的部分称为 ω 的前缀（后缀）。若 ω 的前缀（后缀）不是 ω 自身，则称其为 ω 的真前缀（真后缀）。
从一个符号串中删去它的一个前缀和一个后缀之后剩余的部分称为该符号串的子符号串/子串。
ω = abcd，则 ε，a，b，c，d，ab，bc，cd，abc，bcd，abcd 都是 ω 的子串。
设有符号串 ω 和 ν，如果将符号串 ν 直接拼接在符号串 ω 后，则称此操作位符号串 ω 和 ν 的连接，记做 ων。显然，连接运算是有序的。
设有符号串 ω，把 ω 自身连接 n 次得到符号串 ν，即 ν = ωω…ω（n 个 ω），称 ν 是符号串 ω 的 n 次幂，记做 ν = ωn。特别地， ω0 = ε。
设 AB 是两个符号串集合，AB 表示 A 与 B 的乘积，其定义为
特别地，{ε} A = A {ε} = A，∅ A = A ∅ = ∅，其中 ∅ 为空集。
设有符号串集合 A，A与自身的乘积可以用方幂表示。
设 ∑ 为字母表，显然有 ∑* = ∑0 ∪ ∑ ∪ ∑2 ∪ … ∪ ∑n ∪ …
设 A 为一集合，A 的正闭包记做 A+，定义 A+ = A1 ∪ A2 ∪ … ∪ An ∪ …
A 的自反闭包记做 A = A0 ∪ A+ = {ε*} ∪ A+。
由定义知 A+ = AA*。
一部文法 G 是一个四元组 G = ( VN, VT, S, P )
VN：为非空有限的非终结符号集，其中的元素称为非终结符，或称为语法变量，代表了一个语法范畴，表示一类具有某种性质的符号。
VT：为非空有限的终结符号集，其中的元素称为终结符，其代表了组成语言的不可再分的基本符号集。VT 即字母表 ∑。
V：文法的符号集，V = VT ∪ VN，且 VT ∩ VN = ∅。
S：文法的开始符号或识别符号，亦称公理，S ∈ VN，代表语言最终要得到的语法范畴。S至少在文法某个产生式的左部出现一次。
P：产生式集，产生式是按一定格式书写的定义语法范畴的文法规则。产生式的形式如下
其中 α 称为产生式的左部，β 称为产生式的右部或称为 α 的候选式。
描述另一种语言的语言称为元语言，元语言中的符号称为元语言符号。
文法规则描述中的符号→|<>均为元语言符号。
文法用来产生规定字母表上的语言，语言是字符串（句子）的集合，分析出语言中的字符串就可分析出语言，而文法中的规则可以构造字符串：从文法的开始符号出发，对当前符号串中的非终结符替换为相应产生式右部的符号串，如此反复，直至最终符号串全由终结符号组成。
设有文法 G = ( VN, VT, S, P ) , δ, γ ∈ ( VT ∪ VN )* , 若 α→β ∈ P，则称 δαγ 直接推导出 δβγ，记做 δαγ ⇒ δβγ。
在推导过程中，总是对字符串中最左（右）边的非终结符进行替换，称为最左（右）推导。最右推导也称为规范推导，其逆序成为规范规约。
*符号集
*终结符号集
仅用规范推导得到的句型。
设有文法 G = ( VN, VT, S, P ) ，若存在形如 A ⇒+αAβ 的递归推导，则称文法 G(S) 是递归文法。其中，若 α=ε，则称为左递归文法；若 β=ε，则称为右递归文法。（注：+表示至少经过一次推导）
存在形如 A → αAβ的递归产生式的文法，称为直接递归文法；否则，称为间接递归文法。
设有文法 G = ( VN, VT, S, P ) ，其所产生的语言定义为 L(G)
给定文法G，能从结构上唯一确定相应语言；给定一种语言，能构造其文法，但不唯一。（注：*表示经过0/多次推导）
若 L(G1) = L(G2)，则称文法 G1 和 G2 是等价的。
两个文法尽管它们的规则不尽相同，只要所产生的语言相同，则认为这两个文法是等价的。
见文法和语言部分的BNF
分析树的根结点是文法的开始符号，结点间的父子关系为产生式规则，即若父结点标识为 A，子结点从左到右依次标识为 a1, a2, …, an, 则在文法中存在一产生式 A→a1a2…an。一棵分析树的从左到右的叶结点，就形成了由该分析树表示的推导出的句型。若叶结点都由终结符组成，则这些结点组成的符号串为句子。
对句子25，推导过程不同，则分析树的生长过程也不同，但最终生成的分析树是完全相同的。
对一部文法G，如果至少存在一个句子，对应两棵（或以上）不同的分析树 / 有两个不同的最左（规范）推导，则称该句子是二义性的。包含二义性句子的文法称为二义（性）文法，否则文法无二义性。
文法是对语言的有穷描述，但由文法产生的语言一般是无穷的，因此文法的二义性问题是不可判定的。但是可以寻找一组充分条件，使得满足这些条件的文法必定无二义性。
如果对文法 G = ( VN, VT, S, P ) ，P 中的每个产生式 α → β 不加任何限制，则称 G 为0型文法（短语结构文法）。
由0型文法所确定的语言为0型语言L0，0型语言可由图灵机识别。
设文法 G = ( VN, VT, S, P ) ，对 P 中的每个产生式限制为形如 αAβ → αγβ。其中，A∈VN，α,β∈( VT ∪ VN )*，γ ∈( VT ∪ VN )+（S→ε除外，但此时S不能出现在任何产生式的右部），则称 G 为1型文法（上下文有关文法）。
文法规则中规定了非终结符 A 在出现上下文 α,β 的情况下才能由 A 推导出 γ，显示了上下文有关的特点。
由1型文法所确定的语言为1型语言L1，1型语言可由线性有界自动机识别。
设文法 G = ( VN, VT, S, P ) ，对 P 中的每个产生式限制为形如 A → α。其中，A∈VN，α∈( VT ∪ VN )*，则称 G 为2型文法（上下文无关文法）。
文法规则中每条规则左部只出现一个非终结符，因此不需要顾及上下文，就可由 A 推导出 α。
对1型文法，若限制 α,β 为空串，则得到2型文法。
由2型文法所确定的语言为2型语言L2，2型语言可由非确定的下推自动机识别。
设文法 G = ( VN, VT, S, P ) ，对 P 中的每个产生式限制为形如 A → αB 或 A → α（A → Bα 或 A → α）。其中，A,B∈VN，α∈VT*，则称 G 为3型文法（正则文法、线性文法）。
文法规则为 A → αB 或 A → α 的文法为右线性文法；文法规则为A → Bα 或 A → α的文法为左线性文法。
由3型文法所确定的语言为3型语言L3，3型语言可由确定的有限自动机识别。
从 0 型到 3 型，后一类都是前一类的子集。限制是逐步增强的，而描述语言的功能是逐步减弱的。
与4类文法中的 3 型文法等价，能识别正则文法所定义的语言。
一个确定的有限自动机 M(DFA M) 是一个五元组 M = (Q，Σ，f，q0，Z)。其中，Q为状态的有限集合，每个元素称为一个状态；Σ为输入字符的有限集合（或有穷字母表），每个元素是一个输入字符；f为状态转换函数；q0为M的唯一初态（开始状态)，q0∈Q；Z为M的终态集（接受状态集)，Z⊆Q。
DFA M可以用一个有向赋权图来表示，称为状态（转换）图。图的顶点集为Q，弧上的权值（标记）构成集合Σ；若有 f (p,a) = q，则表示图中有一条从 p 到 q 的权值（标记）为 a 的弧；通常约定 q0 是由一个箭头指向的特殊标记出的结点；Z中的状态由嵌套的双圆圈结点来标记。
DFA M还可以用关系表来表示，称为状态（转换）表。表的第一列的元素与 Q 相对应；第一列的第一个状态为开始状态 q0 ；上角标带 * 的是 Z 中的状态；表的第一行的元素与M的有穷字母表 Σ 相对应；若有 f (p,a) = q，则在 p 对应的行，a 对应的列处的内容为 q。
设DFA M = (Q，Σ，f，q0，Z)，ω = w1w2…wn 是字母表 Σ 上的一个字符串，如果存在Q中的状态序列 p0，p1，…，pn，满足下列条件：
即有 f (q0，w) ∈ Z，则 M 接受（识别）ω；否则称 M 拒绝（不识别）ω。
对于状态图，若存在一条从初态结点到某一终态结点的路径，且在这条路径上所有弧的标记连接成的字符串等于 ω，则称 ω 被确定的有限自动机M所识别（接受）。若 M 的初态结点同时是终态结点，则空串 ε 被 M 所识别。
DFA M 识别的字符串的全体称为 M 识别的语言，记为 L(M)。
对确定的有限自动机稍加修改，使其在某状态下输入一字符的转换状态不是唯一的，而允许转换为多个状态，并允许不扫描字符就可转换状态，便成为了非确定的有限自动机。
在确定的有限自动机中，读入一个字符串 α 后，从初始状态 q0 只有一条路径表述相应的变化；判断字符串 α 是否被一确定的有限自动机所接受，只需跟踪一条路径。但在非确定的有限自动机中，对任一输入字符串 α，可以有若干条路径，这些路径都要被跟踪，以确定其中是否有一条路径，其最后的状态属于终态集。
一个非确定的有限自动机 M(NFA M) 是一个五元组 M = (Q，Σ，f，q0，Z)。其中，Q为状态的有限集合；Σ为输入字符的有限集合（或有穷字母表）；f为状态转换函数，从 Q×(Σ∪{ε})→2Q 的映射。这里的后继状态不是唯一的，它是状态集 Q 的子集；q0为M的开始状态，q0∈Q；Z为M的终态集（接受状态集)，Z⊆Q。
设NFA M = (Q，Σ，f，q0，Z)，ω = w1w2…wn ∈ Σ∪{ε}，如果存在Q中的状态序列 p0，p1，…，pn，满足下列条件：
即有 f (q0，w) ∩ Z ≠ ∅，则 M 接受（识别）ω；否则称 M 拒绝（不识别）ω。
设NFA M = (Q，Σ，f，q0，Z)。假设 I 是 M 的状态集 Q 的一个子集，即 I ⊆ Q，则定义ε—closure(I)为：
状态集 ε—closure(I) 称为状态 I 的 ε 闭包。
设NFA M = (Q，Σ，f，q0，Z)。假设 I ⊆ Q，则定义 Ia = ε—closure({p ∈ f(q,a) | q ∈ ε—closure(I)})为，即 Ia 是从所有 I 的 ε 闭包出发，经过一条 a 弧而到达的状态集的 ε 闭包。
Ia 可看做从状态 I 出发扫描字符串 εmaεn (∀m, n ≥ 0) 后所能到达的状态集，简记为 f(I, a)。
对于一个给定的NFA，一定存在一个DFA，且这两个有限自动机所识别的语言相同。下面介绍非确定的有限自动机的确定化算法——子集法。
设 DFA M 的两个不同状态 q1,q2，如果对任意输入字符串 ω，从q1,q2状态出发，总是同时到达接受/拒绝状态之中，则称 q1,q2 等价，记做 q1~q2。如果两个状态不等价，则称q1,q2是可区别的。
如果从 DFA M 的初态开始，识别任何输入序列都不能到达的那些状态称为无关状态。
如果 DFA M 既没有无关状态，又没有彼此等价的状态，则称 DFA M 是规约的（即最小的确定的有限自动机 M）。
从初态开始标记，逐步对可到达的状态构造标记闭包。
划分法：寻找且合并 DFA M 中的等价状态，即将 DFA M 的状态划分成互不相交的子集，使得任何两个不同子集的状态都是可区别的，且同意子集的任何两个状态都是等价的。从而得到一个与 DFA M 等价的且最小的 DFA M’。
首先对所有状态按终态与非终态初始划分为两个状态子集。在算法中，对于每一个划分 π，属于不同子集的状态是可区分的，而属于同一子集中的各状态是待区分的。算法的第二步检查是否还能对它们进行划分，若能就重新划分。
注意：由子集法从 NFA→DFA 不含有无关状态，化简时不用作无关状态的消除。
设文法 G = ( VN, VT, S, P )为一右线性文法（左线性文法结论相同），则存在一 DFA M = (Q，Σ，f，q0，Z)，使 L(M) = L(G)。
已知一 DFA M = (Q，Σ，f，q0，Z)，则存在一个右线性文法 G = ( VN, VT, S, P )，使 L(M) = L(G)。
综合两个定理结论，正则文法所产生的语言类与有限自动机所识别的语言类相等，即作为描述正则语言的正则文法与作为语言识别机的有限自动机是等价的。
设 Σ 为有限字母表，在 Σ 上的正规式和正规集可递归定义如下：
规定正规式运算的优先级由高到低的次序为 *（闭包）、•（连接）和 |（并），它们的结合性都为左结合。
正规式 r 所表示的正规集 R 是字母表 Σ 上的语言，称为正则语言，用 L(r) 表示，即 R = L(r)。L(r) 中的元素为字符串（句子）。
若两个正规式 r 和 s 所表示的语言 L(r) = L(s)，则称 r,s 等价，记做 r = s。
由前两节的内容，有限自动机接受的语言等价于正规文法产生的正则语言，而正规式或正规集定义的语言也为正则语言。因此，正规式与有限自动机在描述语言上应该等价。
对于 Σ 上的 DFA M = (Q，Σ，f，q0，Z)，定义另一等价 DFA M‘ = (Q’，Σ‘，f’，q0‘，Z’)。其中，Q’ 是由 M 的状态集 Q 加上两个不在 Q 中的附加状态 qA,qB，q0‘ = qA，Z’ = qB。f’ 定义如下：
新定义的 M’ 的状态转换图比 M 的状态转换图多了两个结点 qA 和 qB，qA是用 ε 弧连接到 M 的初态结点 q0，M 的所有终态节点 qj 都通过 ε 弧连接到 qB。
新定义的 M’ 的特点：
注：qi = qk是由为构造2.14即正则语言的特点（线性文法）所假定的。
由于没有从 qB 射出的弧，所以 qB* 不会出现在任何状态转移方程中等式的右边；又因为没有射入 qA 的弧，所以 qA 没有相关的状态转移方程。
蒽感觉证明也不会考，先空着...
例如：
首先拓广文法，添加初态和终态。
例如：
词法分析的任务是对输入的字符串形式的源程序按顺序进行扫描，在扫描的同时，根据源语言的词法分析识别具有独立意义的单词（符号），并产生与其等价的属性字流作为输出。通常属性字流即是对识别的单词给出的标记符号的集合。
完成词法分析任务的程序称为词法分析程序，通常也称为词法分析器或扫描器。它一般是一个独立的子程序或作为语法分析器的一个辅助子程序。
词法分析程序一般具有如下功能：
单词是具有独立意义的最小语法单位，一般常用的程序设计语言的单词可分为：
属性字是扫描器对源程序中各单词处理后的输出形式，也是单词在编译程序处理过程中的一种内部表示，设计成二元组的结构形式：（单词属性，单词值）。
其中，单词属性表示单词的类别，用来刻画和区分单词的特性或特征，通常用整数编码来表示。单词值是编译器设计的单词自身值的内部表示，可以缺省。
在词法分析过程中，编译程序借助操作系统从外部存储介质依次读取源文件中的内容。为提高读取磁盘的效率，方便词法分析器的处理工作，一般采用缓冲输入方案，即在内存中开辟一个大小适当的输入缓冲区，将源程序从磁盘上分批读入缓冲区，扫描器从缓冲区中读取字符进行扫描和处理。
将一个缓冲区分为两个半区，每个半区长度为 n ( n 一般为磁盘块或簇长的整数倍）。之所以把输入缓冲区设计成对半互补的，是因为无论缓冲区设得多大，都不能保证单词符号不被它的边界截断。
输入缓冲区设两个指针以方便扫描器读取字符。指针 B 称为单词起始位置指针，指向当前扫描到的单词的第一个字符，指针 F 称为向前搜索指针用来寻找单词的终点。扫描器每次把长度为 n 的源程序输入到缓冲区的一个半区，如果指针 F 从单词起点出发搜索到半区的边缘（每个半区边缘设专门标志标识）仍未到达单词的终点，就把源程序后续的 n 个字符输入到另一个半区，这样两个半区交替使用达到互补作用。
由于在源程序中，特别是非自由格式书写的源程序，往往有大量的空白符、回车换行符及注释等，这是为增加程序的可读性及程序编辑的方便而设置的，对程序本身无实际意义。此外，像 C 语言有宏定义、文件包含、条件编译等语言特性，为减轻词法分析器实质性处理的负担，因此在进入词法分析器之前，要先对源程序进行预处理，主要功能是：
词法分析器对单词的识别是在对源程序扫描过程中实现的，并对单词进行相应的产生属性字的处理。另外，对程序中各算术常数的识别，还要涉及内码形式的转换工作。
一般程序语言中的单词，在对源程序依次扫描中即可立即确认；但对某些语言，如对关键字使用不加限制的Fortran中，会使单词的识别产生混淆，并非当指针 F 搜索到一个单词终点时就能确认，此时就需要超前搜索技术。
词法分析程序可以是独立的一遍，它把字符串形式的源程序经过扫描和识别转换成单词序列，输出到一个中间文件，该文件作为语法分析程序的输入继续编译的过程。好处是便于自动生成，且与语法分析程序有明确接口。
更一般的情况是将词法分析程序设计成一个子程序，每当语法分析程序处理需要读取单词时，则调用该子程序。此时词法分析和语法分析程序处于同一遍，可以省去中间文件。
注意：终态结点带有*表示在扫描和识别单词过程中，到达一个单词识别态时，对于当前识别的单词多读进了一个字符，即超前搜索。
程序中心法：把状态转换图看成一个流程图，从状态转换图的初态开始，对它的每一个状态结点编一段相应的程序。
不考 略
语法分析是编译程序的核心部分。编译程序在完成词法分析之后就进入语法分析阶段。
语法分析的任务是，按照语言的语法规则，对单词串形式的源程序进行语法检查，并识别出相应的语法成分。语法分析程序处理的对象是词法分析器的输出，即属性字流形式的源程序，它的处理依据是语言的语法，其分析结果是识别出的无语法错误的语法成分（可以用分析树的形式来表示）。
程序设计语言作为一般形式语言的特例，语法分析的关键是语法范畴(在自然语言中通常称为句子或短语)的识别问题。综述之，语法分析程序要解决的问题是：对给定文法 G 和字符串(句子) α (α∈VT*)，判定 α ∈ L(G) ？即判定 α 是否是文法 G 所能产生的句子，同时处理语法错误。
完成语法分析任务的程序称为语法分析程序，即语法分析器或简称分析器。
给定文法 G 和源程序串 $，自上而下分析方法是从文法 G 的开始符号 S 出发，通过反复使用产生式对句型中的非终结符进行替换，即选择合适的产生式进行最左推导，逐步使推导结果与输入串 $ 匹配，则可以确认串 $ 是文法 G 的句子。
与自上而下的分析过程的方向相反，就是从输入字符串 $ 开始，通过反复查找当前句型中存在的文法 G 中某个产生式的候选式，若查找到就用该产生式的左部代换之，即归约。这样逐步归约到文法的开始符号 S，则有 $ ∈ L(G)，即输入串 $ 是文法 G 所描述的语言 L(G) 的符号串(句子)。
如果用分析树表示，就是从分析树的叶结点（叶结点即是输入符号串自身）开始，逐步向上归约直到根结点。
通过例 4-3 观察一般自上而下分析的过程，这是一种带回溯的自上而下分析，回溯的实质是源于一种试探性的推导过程，也就是反复使用文法 G 中的不同的文法规则去谋求匹配输入串 $ 的过程。
例4-3的分析过程可以看出，带回溯的自上而下分析法分析效率低，使系统开销加大甚至会导致算法实现的失败。其原因是分析过程中选择产生式候选式的不确定性，造成匹配输入串的假象。当发现匹配不成功时，回潮到前面分析的某一步。另外，鉴于对源程序的扫描的自左向右和实施自上而下分析采取的是最左推导，因此当文法是左递归文法时，还会造成无止境的推导而无法匹配。
直接与间接的左递归文法都会导致此结果。所以要实施有效的自上而下分析，首先要研究文法左递归的消除方法。文法中的左递归性可以通过对文法产生式进行改写，使之不含左递归。
文法中的直接左递归表现在其含有 A→Aα（α∈VT∪VN>）形式的产生式规则，则在语法分析的最左推导中会呈现 A⇒A… 的形式，间接左递归文法会呈 A⇒+A… 的形式。
有些文法表面上不具有左递归性，却隐含着左递归，经过若干步推导代换，就显现出左递归性了，这是间接左递归文法。
消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。
下面给出一个消除文法所有左递归性的算法，要求文法不含回路（形如 P ⇒+P 的推导），且不含以 ε 为右部的产生式。
对于文法(4.10)，可以使用上述算法按如下步骤改写为文法(4.11)
递归下降分析器的基本构造方法是：对文法的每个非终结符号，都根据其产生式的各个候选式的结构，为其编写一个对应的子程序(或函数)，该子程序完成相应的非终结符对应的语法成分的识别和分析任务。
因此，递归下降分析器的语法分析子程序的功能是：对某个非终结符，用规则的右部符号串去匹配输入串。分析过程是按文法规则自上而下一级一级地调用有关子程序来完成。鉴于文法往往具有递归性(不允许左递归)，故递归下降分析器是由一系列递归子程序组成的分析程序。
注意：递归下降分析法要求文法不具有左递归性。
先欠着，作业里没有
LL(1)分析法是一种自上而下的分析法，使用显式栈而不是递归调用来实现分析。
所谓“LL(1)”是指语法分析是按自左(第一个“L”)至右的顺序扫描输入字符串，并在分析过程中产生句子的最左推导(第二个“L”)。“1”则表示在分析过程中,每一步推导，最多只要向前查看(向右扫描)一个输入字符，即能确定当前推导所应选用的文法规则。
依此类推，如果分析过程中的每一步推导，要向前查看k个输入字符，则称为LL(k)分析法。通常把按LL(1)方法完成语法分析任务的程序称为LL(1)分析程序或LL(1)分析器。LL(1)分析法是比递归下降分析法更有效的一种自上而下的语法分析方法。
LL(1)分析法的实现是由一个总控程序控制输入字符串在一张LL(1)分析表(也称为预测分析表)和一个分析栈上运行而完成语法分析任务的。所以，一个LL(1)分析器的逻辑结构如图4-10所示，由总控程序、LL(1)分析表和分析栈三部分构成的。
用 M[A,a] 形式的矩阵表示。其中 A 是文法的非终结符号，a 是文法的终结符号或 “#”（为分析方便引入的一个特殊终结符号，把它作为输入字符串的结束符)。矩阵元素 M[A,a] 存放一条关于非终结符 A 的产生式（实际为 A 的一个候选式）或用空白来给出一个出错标志。矩阵元素实际是相应的分析动作（即所选用的推导的产生式），即对 [Ai, aj] = Ai→α 表示当前分析栈顶为Ai，输入字符为 aj 时,应选用 Ai→α 进行推导。
用于存放分析过程中的文法符号。分析栈初始化时，在栈底压入一个“#”，然后在次栈底放入文法的开始符号。
总控程序的功能是依据分析表和分析栈联合控制输入字符串的识别和分析，它在任何时候都是根据当前分析栈的栈顶符号 X 和当前的扫描字符 a 来执行控制功能。
LL(1)分析法属于自上而下分析法，实现主要依赖于LL(1)分析表。而对于分析表的构造，关键要解决对文法的每个非终结符对应于哪些终结符时，才能使用相应的文法规则推导，即在分析表的相应位置填入适当的文法规则；而对错误的匹配，则填以空白，实际的LL(1)分析表中应该对应出错处理程序。
在讨论不带回溯的自上而下的分析中，给出了FIRST集合的定义，进一步给出了不带回溯的条件。据此，对文法 G，若文法 G 中产生式形如 A→α 且没有 α⇒ε 的情况，则产生LL(1)分析表很容易。即对文法规则 A→α 而言，只有当a∈FIRST(α) 时,才能在M[A,a]处填入规则 A→α。
若 ε∈FIRST(α)，则面临 a∉FIRST(α) 时并不一定出错。
对某些文法，可能存在 M[A,a] 有若干个文法规则，则称这样的分析表是多重定义的。在这种情况下，会使语法分析陷入困境，不能适用于LL(1)分析法，因此引入LL(1)文法。
一部文法G，若其LL(1)分析表M不含多重定义入口，则称之为一个LL(1)文法。LL(1)文法产生的语言称为LL(1)语言。
自上而下分析中，使用由LL(1)文法构造的分析表完成LL(1)语言的语法分析的方法，称为LL(1)分析法。
设置一个寄存文法符号的符号栈，在分析过程中，把输入字符一个个地按扫描顺序移入栈内，当栈顶符号串形成某个产生式的一个候选式时就进行归约，即把栈顶的这部分替换成该产生式的左部符号，即完成一步归约动作。然后再检查栈顶是否又出现某个产生式的一个候选式，再进行归约，若栈顶没有构成与某个候选式相同的符号串，则再从输入串中继续移进新的符号，依次类推直到整个输入串处理完毕，此时若栈底只有文法的开始符号，则可以确认所分析的符号串是文法的句子，否则，不是文法的句子，要报告语法错误信息。
主要采取的分析动作：移进、归约、接受/报错
“移进-归约”分析采用的是规范归约，将每次归约时呈现在栈顶的要归约的子串称为“可归约串”。依照寻找可归约串的策略不同形成了不同的自下而上分析方法。所以，自下而上分析的关键问题，一是判断栈顶字符串的可归约性，即检查何时处在栈顶的哪个子串是“可归约串”，这是归约条件；二是决定选用文法中哪条规则进行归约，因为一个“可归约串”可能可以归约到多个不同的非终结符，即“可归约串”是不同的产生式的候选式，这是归约原则。这也是任何自下而上分析方法所要解决的问题。
例 5-1 中，归约是从文法开始符号开始，实行最右推导所替换的串及推导的逆序，每步推导中带下划线的子串即为分析所处的当前栈顶的“可规约串”，符号串 abbcde 的最右推导序列为
S ⇒ aABe ⇒ aAde ⇒ aAbcde ⇒ abbcde
一个句型的最左直接短语称为该句型的句柄。
“移进-归约”分析中的“可归约串“就是当前句型的句柄。要注意的是，如果文法是无二义性的，则规范句型的最右推导是唯一的，也就是说每步归约至多存在一个句柄。
算符优先分析法是一种广为使用的自下而上分析法，这种方法特别适用于各类表达式的分析及符号式语言中具有优先级特点的符号串的分析。
所谓算符优先分析法，是仿照数学表达式的运算过程而设计的一种语法分析方法。即定义算符（广义讲是文法的终结符号）之间的某种优先关系和结合性，借助这种关系来寻找、确定可归约串并进行归约。要提醒注意的是，算符优先分析法所进行的归约不是规范归约。
LR 分析法是目前编译程序的语法分析中最常用且有效的自下而上的分析技术，能适用于绝大多数上下文无关语言分析，理论上也比较完善，适用于语法分析器的自动构造。LR 分析法亦不像前面所介绍的几种语法分析方法，对相应的文法都有一定的要求和限制，因此在使用上都有一定的局限性。而 LR 分析则对文法限制较少。
LR 泛指一类自左至右（“L”：Left-to-right）对输入串进行扫描且自下而上分析（“R”：分析过程构成最右推导的逆序）的方法。LR分析的过程是规范归约的序列。采用LR方法构造的语法分析程序统称LR分析器。
在逻辑上，LR 分析器的结构如图 5-10 所示。它有一个输入串，这是 LR 分析器处理的对象，有一个下推分析栈，以及一个 LR 分析总控程序和 LR 分析表。LR 分析器在总控程序的控制下自左至右扫描输入串，并根据当前分析栈顶所存放的文法符号状态及当前扫描读入的符号，依据LR分析表的指示完成分析动作。
下面结合实例，对 LR 的逻辑结构进行分析。
LR 分析表是 LR 分析器的核心。分析表由两个子表构成，即动作表(action表)和状态转换表( goto 表)，也称为动作函数 action 和转换函数 goto, LR 分析即由这两个表来驱动。
动作表的元素action[qm , ai]表示当前栈顶状态为 qm，输入符号为 ai（ai∈VT）时完成的分析动作，包括4类：移进、归约、接受或出错。
状态转换表的元素go[qm , Xi]表示当前栈顶状态为qm，输入符号为Xi（Xi∈VN）时转移到的下一个状态。
一个文法G，若能构造其LR分析表，并使它的每一入口是唯一确定的，则文法G称为LR文法。
一个文法G，若每步最多向前查看k个输入符号，就能唯一决定当前分析动作，从而按LR方法进行分析，则称文法G为LR(k)文法。
LR(0)分析仅仅根据当前分析栈顶状态（该状态记录着已进行过的分析历史情况），而不需从当前输入字符串再向前查看输入符号，来决定当前的分析动作。
规范句型的一个不含句柄之后任何符号的前缀，称为该句型的一个活前缀。
只要在活前缀右边再加上一些符号（包括ε），就可构成一个特殊的最长活前缀，这个活前缀恰好含有句柄，可立即归约。
LR分析中必须使栈中符号始终是活前缀，这样再读入几个符号后，构成刚好包含句柄的活前缀，进而实施归约。
活前缀与句柄间的关系：
以上几种情况可以用LR(0)项目来表示。
在文法G的每个产生式右部（候选式）的任何位置上添加一个圆点，所构成的每个产生式称为LR(0)项目。
约定：若产生式形为 A→ ε，则其LR(0)项目为 A→ • 。
LR(0)项目中的圆点可看成是分析栈栈顶与输入串的分界线，圆点左边为已进入分析栈的部分，右边是当前输入或继续扫描的符号串。
不同的LR(0)项目，反映了分析栈的不同情况，根据作用，将LR(0)项目分为以下4类：
例如：
由 LR(0) 项目构造识别文法 G 的所有可归前缀的 NFA 的方法：
识别文法 G 可归前缀的 DFA 项目集的全体称为文法 G 的 LR(0) 项目集规范族。
在求出文法的全部 LR(0) 项目之后，可用它来构造识别全部可归前缀的 DFA。这种 DFA 的每一个状态由若干个 LR(0) 项目所组成的集合（称为项目集合）来表示，一个 DFA 的全体状态集就构成了 LR(0) 项目集规范族。
另一种方法是从文法的基本项目出发，借鉴 ε-closure 闭包运算的方法，通过对项目集施加闭包运算和求 GO 函数，来构造 LR(0) 项目集规范族。
为使接受状态易于识别，文法开始符号的候选式唯一，对于不仅在一个产生式左端出现的文法的开始符号，要对文法进行拓广。设 G 是一文法，S 是它的开始符号，则将产生式S‘→S加入到 G 中构成新的文法 G’，S‘ 为 G’ 的开始符号，G‘ 称为 G 的拓广文法。
假定 I 是文法 G’ 的任一项目集，则构造 I 的闭包-closure(I) 的方法如下：
若 I 是文法 G 的一个项目集，X 为 G 的符号，则 GO( I, X ) = closure( J )。其中，J = { 形如 A → αX • β 的项目 | A → α • Xβ∈ I }。
GO函数反应了在 LR 分析中，若 I 中有圆点在位于 X 左边的项目：A → α • Xβ，当分析器从输入符号串中识别出文法符号 X 后，分析器要进入的后续状态。
若一个文法 G 的识别可归前缀的 DFA 的每一个状态不存在：① 既含移进项目又含归约项目；② 含有多个归约项目；则每个状态的项目相容，称 G 是一个 LR(0) 文法。
对于任何一个 LR(0) 文法，一定存在不含多重定义的 LR(0) 分析表。
由于只有当文法 G 是 LR(0) 文法，即文法 G 的每一项目集均不含冲突项目时，才能构造出不含冲突动作的 LR(0)分析表。而流行的程设语言一般都不是 LR(0) 的，其适用性受到很大的限制。
移进-归约冲突：在识别活前缀的 DFA 状态中，若既含有圆点不在最后的移进项目，又含有圆点在最后的归约项目，则称该项目存在移进-归约冲突。
归约-归约冲突：若含有两个或两个以上圆点在最后的归约项目，则称该项目集存在归约-归约冲突。
分析表中出现多重定义的原因在于：对含有归约项目 A → α • 的项目集 Ii，不管当前输入符号为何，皆把 action 子表相应于状态 Ii 的那一行的元素都指定为 rj（ j 为 产生式 A → α • 的编号）。因此，如果该项目集 Ii 中同时还含有形如 B → α • bβ（b∈VT）移进项目或形如 C → α • 的归约项目，则在分析表的 Ii 对应的一行里，势必会出现多重定义的元素。
如果对于含有冲突项目的项目集，在构造分析表时，能根据不同的向前符号 ak，将项目集各项目对应的分析动作加以区分，则冲突就可能得到解决。
与LR(0)的区别是：只有当前输入符号属于归约项目左部的FOLLOW集时，才进行归约，否则继续移进。
注意适用场景：移进项目的输入符号（圆点后一个符号）与归约项目的输入符号（左部的FOLLOW集）彼此不相交。否则SLR(1)不足以解决问题，仍存在冲突。
按照 SLR(1) 分析方法构造的文法 G 的 LR 分析表，称为 SLR(1) 分析表。
如果每个入口不含多重定义，则文法 G 称为 SLR(1) 文法。
当所给的文法出现冲突的分析动作时，SLR(1) 方法仅仅孤立地考察当前输入字符是否属于与归约项目 A → α • 相关联的集合 FOLLOW(A)，若属于则按产生式 A → α 进行归约，而没有考察字符串 α 所处的规范句型的"环境"，存在一定的片面性。SLR(1) 方法是当 α 一旦出现在分析栈的顶部（设分析栈当前字符串为 #δα），且当前输入字符 α∈FOLLOW(A)，就贸然将 α 归约为 A，使分析栈中字符串变为 #δA。但若文法中并不存在 δAa为前缀的规范句型，那么这种归约是无效的。
判定现在用产生式归约是否有意义，包含两个确定信息：
当 a ∈ FIRST(w) 时，说明通过这步归约有途径到达开始符号 S，即归约有意义。
为使分析的每一步都能使栈中保持一个规范句型的活前缀，必须要求每一个LR(1)项目对应的活前缀是有效的。
对于项目集 I 中的项目[A→ α • Bβ，a]（在输入符号为 a 时可归约的产生式 A→ α • Bβ），将 [B→ • γ，b]（其中 b∈FIRST(βa) 且 b∈ VT）加入项目集。
图中存在部分细节错误，依据纸质书本中为准。
LALR(1) 分析 (Look-Ahead LR) 是对 LR(1) 分析的一种简化和改进，使 LR(1) 分析更为经济实用且简单。LALR(1) 分析比 LR(1) 分析小得多，对同一个文法， LR(1) 分析表具有和 SLR 分析表相同数目的状态，但却能胜任 SLR(1) 所不能解决的问题，当然比 LR(1) 分析能力差一些，但对目前常用的程设语言基本适用。
LR(1) 分析表之所以状态多，是由于 LR(1) 项目中的搜索符不同，而将原来对应于 LR(0) 项目集的相应状态和项目，分割成多个 LR(1) 项目及 LR(1) 项目集。
对文法 G 的 LR(1) 项目集规范族，若存在两个项目集 I0、I1，其中 I0、I1 项目集中的 LR(0) 项目相同，仅搜索符不同，则称 I0、I1 为 G 的 LR(1) 同心项目集，或称 I0、I1 具有相同的心。
LALR(1) 分析的思想就是在文法的 LR(1) 项目集规范族的基础上，将同心的项目集合并为一，从而得到 LALR(1) 项目集规范族，若不存在冲突（一定是归约-归约冲突），则按这个项目集规范族构造 LALR(1) 分析表。
按上述算法构造的 LALR(1) 分析表，若不存在冲突，则称文法 G 是 LALR(1) 文法。使用 LALR(1) 分析表的分析器叫 LALR(1) 分析器。
任何二义文法绝不是一个 LR 文法，但是应用 LR 分析的基本思想和实现技术，借助一些辅助规则或条件，对某些二义文法所定义的语言仍可用 LR 方法进行分析，且既简单又实用。
从二义文法表示的语言的内涵出发，对文法施加一定的规定或条件，来直接构造其 LR 分析表，如对算符规定优先级和结合规则等解决冲突，避开文法二义性。
LR 分析器在分析过程中的每一步，通过查 action 表可以确定源程序中的错误，元素为“空白”表示出错，应进行相应的错误处理。
编译器每次发现错误时，抛弃一个输入，指导输入符号属于某个指定的同步符号集（如界限符；、} end...）为止。
发现错误时，对剩余符号串作局部校正，使用可以使编译器继续工作的输入串代替剩余输入的前缀。
扩充语言的文法，增加产生错误结构的产生式，分析中可以直接识别处理错误。
获取全局最小代价纠正。
语义分析程序在整个编译过程中，对源程序的语义做出解释，引起源程序发生质的变化；而词法分析和语法分析仅涉及程序语言的结构分析，是对源程序在形式上进行变换处理。
语义分析主要任务是按照语法分析器识别的语法范畴进行语义处理，翻译成相应的中间代码或目标代码。语义分析方法——语法制导翻译及属性翻译文法。语法制导翻译实质是在语法分析过程中同时进行语义处理的一种翻译技术。
对上下文无关文法进行语义处理，集中表达了上下文无关和上下文有关之间的“差”。
上下文无关文法未对词或语法概念进行关联，文法中天然缺失。但目前大多数高级程设语言都是上下文有关，显式表现为先声明后使用。在这种情况下，上下文无关文法无法通过分析树或语法树的形式将这种关系进行表达，因此引入属性文法来表达这种关联性。
了解文法功能，确定需要的属性类型
综合属性和继承属性（确定计算方向），确定类型需考虑：
语法制导翻译是对上下文无关文法制导下的语言进行翻译，实现思想是把语言结构的属性赋给代表语言结构的非终结符号上，属性值由附加到文法产生式的"语义规则"计算，而语义规则的计算可以产生代码。
将语义信息与语言的结构联系起来涉及到两个概念：
语法制导定义和翻译模式都在语法分析的基础上建立分析树，然后遍历分析树，按照分析树对语义规则进行计算。为此，可通过生成代码、查填符号表、给出错误信息等，来完成各种翻译动作。因此，对语义规则计算的过程实际上就是对输入源程序串的翻译过程。
语法制导定义是基于上下文无关文法，较抽象的、隐蔽了一些实现细节的翻译说明。语法制导定义中的每个文法符号都有一个与之相关的属性集合。集合中的属性分为两类：综合属性和继承属性。如果把分析树中表示文法符号的结点看成一个记录，其中包含若干域来存储各种信息，那么属性就相当于记录中域的名称。分析树结点中的属性值要用语义规则来定义，而语义规则和相应结点的产生相关。
语义规则可以建立各属性之间的依赖关系，可以用一个称为依赖图的有向图表示。根据依赖图可以为语义规则推导出计算顺序。按语义规则计算就是定义关于一个输入串的分析树结点的属性值。另外，语义规则还可能有一些其他作用，如输出一个值或修改全局变量等。
在语法制导定义中，每个文法符号具有一组属性，文法的每个产生式 A→α 都有与其相关的语义规则的集合，每条语义规则的形式为：b = f ( c1,c2,...,cn )。其中 f 是一个函数，b 和 ci 可取如下两种情况之一：
理解：产生式左部的综合属性由子结点（右部）决定；产生式右部的继承属性由父结点或兄弟结点（左部或右部）决定。
在这两种情况下，都说属性 b 依赖于属性 c1,c2,...,cn 。每个文法符号的综合属性集和继承属性集的交集应为空集。属性文法是语义函数无副作用的语法制导定义。
通常，语义规则中的函数写成表达式的形式。有时，语法制导定义中的某些语义规则是为了产生副作用，这样的语义规则一般写成过程调用或过程段的形式。在这种情况下，可以把语义规则看成是定义相关产生式左部非终结符的虚拟综合属性。
在语法制导定义中，一条语义规则完成一个计算属性值的动作。设终结符号只有综合属性，其属性值通常由词法分析器提供。此外，对文法的开始符号若不特别说明，则认为没有继承属性。
仅仅使用综合属性的语法制导定义叫做S_属性定义(Synthesis)，对于S_属性定义，分析树的注释可以自底向上完成：从叶结点到根，通过计算语义规则得到结点的属性。
在分析树中，如果一个结点的继承属性值是由该节点的父结点和（或）兄弟结点定义的，则在表达程设语言对它所在上下文的依赖性时，使用继承属性更为方便。
编译程序在执行的过程中，为了完成源程序到目标代码的翻译，需要不断收集、记录和使用源程序中一些语法符号的类型、特征和属性等相关信息。为方便起见，一般的做法是让编译程序在其工作过程中，建立并保持一批表格，如常数表、变量名表、数组名表、过程或子程序名表及标号表等，习惯上将它们统称为符号表或名字表(简称名表)。
符号表的每一登记项，将填入名字标识符以及与该名字相关联的一些信息。这些信息，将全面反映各个符号的属性及它们在编译过程中的特征，诸如名字的种属(常数、变量、数组、标号等)、名字的类型(整型、实型、逻辑型、字符型等)、特征(当前是定义性出现还是使用性出现等)、给该名字分配的存储单元地址以及与该名字的语义有关的其他信息等。
根据对编译程序工作阶段的划分，符号表中的各种信息将在编译程序工作过程中的适当时候填入。对在词法分析阶段就建造符号表的编译程序，当从源程序中识别出一个单词(名字)时，就以此名字查符号表若表中尚无此登记项，则将该名字列入表中。至于与之相关的一些信息，可视工作的方便。分别在语法分析、语义处理及中间代码生成等阶段陆续填入。几乎在编译程序工作的全过程中，都需要对符号表进行频繁的访问，查表或填表等操作，在编译程序的编译过程中是很大的一笔开销。因此，合理地组织符号表，并相应地选择好查表和填表的方法，是提高编译程序工作效率的重要一环。
一般而言，对于同一类符号表，例如变量名表，它的结构以及表中的每一登记项所包含的内容，由于程序设计语言种类和目标计算机的不同，可能有较大的差异。
然而抽象地看各类符号表一般都具有如表6-7所示的形式。由表6-7可以看出，符号表的每一个记录项都由两个数据项组成：
对于标识符的长度有限制或长度变化范围不大的语言来说，每一登记项名字栏的大小可按标识符的最大允许长度来确定。
一般按两种方式来存放各类标识符：一种是将标识符中各字符的“标准值"从左到右依次直接存入名字项中，如果名字中的字符个数小于名字栏的长度，则用空格符或空白字符补全。另一种是将标识符按某种方式转换为相应的内部编码，然后再将此内部码存入名字项中。
对于标识符长度不限，或者标识符长度变化范围较大的语言，可另设一个特定的字符串表，把符号表中的全部标识符都集中地放在此字符串表中，而在符号表的名字栏中仅放置一个指针，该指针用来指示相应标识符的首字符在字符串表中的位置。为了指明每一标识符的长度，可在名字项中放置一个表示相应标识符所含字符个数的整数的信息。
中间语言（中间代码）是一种面向语法，易于翻译成目标程序的源程序的等效内部表示代码。其可理解性及易于生成目标代码的程度介于源语言和目标语言之间，既要考虑从源语言到目标语言的翻译跨度又要考虑目标机的 指令集特点。
使用中间代码有许多优点，不仅仅是作为最后生成目标代码的过渡：
在逆波兰表达法（后缀表达式）中，每个运算符直接跟在其操作数后面。对 N 目运算的算符 θ，其逆波兰表达式形式为 e1e2...enθ (n ≥ 1)。
对逆波兰表达式自左至右进行扫描，遇到操作数就把它推进栈，遇到 N 目运算的运算符即从栈中弹出 N 个操作数进行运算，并将结果推进栈。
原形式：<变量> = <表达式>
逆波兰：<变量> <表达式> =
原形式：IF then else
逆波兰： BZ BR
模拟IF-THEN-ELSE运行：
每条指令由 N 个域组成。其中，第一个域 OP 通常表示操作符，其余的 N - 1 个域表示操作数或中间及最后结果
三元式的每个指令有三个域，一般形式是：
间接码表：用一张分离的表单独给出三元式的执行顺序。
当三元式序列发生变化时，只需要改变该表中三元式的入口顺序（编号），原三元式序列不变。
三元式会写下所有操作，例如在优化时要去掉所有的重复三元式； 而间接三元式中不出现重复的三元式，转而用操作序列代表重复操作。
四元式的每个指令有四个域，一般形式是：
使用四元式表示中间代码对代码优化很方便，在生成目标代码时可以使用引入的临时变量，这将使生成目标代码比较简单。
三元式和逆波兰表示都是树的直接线性表示，树的后序遍历可以产生逆波兰表示，一个三元式对应一棵二叉子树，OP 为子树根，ARG1 和 ARG2 分别对应子树的左右叶结点。
如果语句中等号右边的常量是第一次出现，则将其填入常量表且回送常量表序号，然后将等号左边作为常量名的标识符在符号表中登记新的记录，该记录的信息包括名字、常量标志、类型、对应的常量表序号等。
符号表示例：
符号子表示例：
【注】应该还有一张总符号表，其中记录类型作为一个整体（name，TYPE=record，length，offset）记录在其中。
L : S；
其中，L 为语句标号，S 为一个语句。
goto L；
对程序中某个标号的第一次出现（定义性/使用性）都要填标号表（可与符号表合一），每个标号对应标号表的一个记录：
鉴于上述情况，必须把所有以 L 为转移目标的四元式的地址全部记录下来，以便一旦 L 定义性出现时确定其转移地址就可以进行回填。利用拉链返填技术来完成上述的记录及回填工作。
【注】此处的语句顺序符合表达顺序，但逻辑顺序与标号升序一致
数组这类数据由于具有较多的说明信息，如维数、每维大小、类型以及与数组元素地址计算有关的一些信息，所以对数组说明的处理，一般单独设置一种表登记数组的各种信息，称该表为内情向量表。每个数组对应表中的一个内情向量。
数组的使用是以数组元素（亦称下标变量）引用的形式出现的。一般在源程序的编译时，还无法计算出数组元素的地址，因为数组元素引用的下标中往往含有变量，只有到目标程序运行时才能进行。因此，在编译时，遇到数组元素的引用要生成计算其地址的中间代码或目标指令。
数组在存储器中的存放方式决定着数组元素的地址的计算方法，从而也决定着应该产生相应的什么样的中间代码。
函数及局部量信息符号表，并填入有关的属性：种属(过程或函数等)、是否为外部过程数据类型(对函数而言)、形参个数、形参的信息(供语义检査用，如种属、类型等)、过程的入口地址等等
代码优化是指在不改变程序运行效果的前提下，对被编译的程序进行变换，使之能够生成更加高效的目标代码。
这里指的变换，是通过重排、删除、合并或改变程序等手段，使程序产生形式上的变动。
优化可在编译的各个阶段进行。主要时机是在语法、语义分析生成中间代码之后，另一类优化则是在生成目标程序时进行的。 前者优化不依赖于具体的计算机而取决于语言的结构，后者依赖于具体目标机。
将原来处于循环体内多次乘法运算用强度较低的加法运算替代。
在每次循环迭代时，若循环迭代增量的改变多于一次，则称这种类型的循环为多步循环。值的改变是线性的循环增量，称为循环归纳变量，可以外提到循环体外。
将具有一个以上的循环控制变量/迭代增量，且这些量之间存在某种线性关系，这样的循环称为复合变量循环。
通常代码优化阶段由控制流分析、数据流分析和代码变换三部分组成。
局部优化是指在程序的一个基本块内进行的优化，因为基本块内的语句是顺序执行的，没有转进转出、分叉汇合等问题，所以处理起来较简单。
凡是未包含在基本块中的语句，都是程序的控制流不可到达的语句，直接从程序中删除。
把一个程序划分成若干基本块后，可以按照程序的执行过程用有向边把基本块连接起来，这就构成了程序的控制流图，简称为流图。流图是一个具有唯一首结点的有向图。
G = ( N，E，n0 )
DAG（Directed Acyclic Graph）是无环路的有向图。
由于基本块是由一顺序执行的语句序列组成的，所以基本块可以用DAG来表示。基本块的DAG是结点上带有下列标记的DAG：
流图的一个结点是一个基本块，可用DAG表示 。
流图确认的是基本块之间的关系，DAG确认的是基本块内各四元式间的关系。
ni DOM nj：ni 是 nj 的必经结点。
在程序流图G中，结点n的全部必经结点，称为结点n的必经结点集，记做D(n)。
设a→b是流图G中一条有向边，如果 b DOM a，则称 a→b 是流图G中的一 条回边，记作 <a,b>。
若<n,d>是一回边，则由结点d、结点n以及所有通路到达n而该通路不经过d的所有结点序列构成一个循环L，d是循环L的唯一入口。
为了进行循环优化和全局优化（多个基本块范围的优化），编译程序需要收集整个程序范围内的有关信息及分布在程序流程图每个基本块的信息，这些信息是程序中数据流的信息，这一工作称为数据流分析。
在一个程序流图的基本块中，认为前后相继的两个语句之间为一个“点”，用 Pi 表示。
同样，流图中两个前后相继的基本块 Bi 和 Bi+1 ，其 Bi 的最后一个语句之后和 Bi+1 的第一个语句之前亦分别为程序的一个点。
变量 x 获得值的中间代码的位置 d，称为 x 的定值点。定值点在以下三种情况中出现：
引用变量 x 的中间代码的位置 d，称为 x 的引用点。
设有流图 G，变量 A 在 G 中某点 d 的定值到达另一点 p，是指流图中从点 d 有一通路到达点 p 且该通路上没有对变量 A 的再定值。
假设在程序中某点 P 引用了变量 A 的值，则把 G 中能到达 P 的 A 的定值点的全体，称为A在**引用点 P **的引用-定值链 (ud链)。
ud链是相对于引用点的定值情况：即某变量 A 在点 d 的引用的 ud 链，是变量 A 引用前所有可能到达 d 点的对 A 定值的定值表。
在程序中对某变量 A 和某点P，如果存在一条从 P 开始的通路，其中引用了 A 在点 P 的值，则称 A 在点 P 是活跃的，否则称 A 在点 P 是死亡的。