1. 步调编译
1.1 步调编译的目的
步调编译的目的把源代码变成目的代码。如果源代码在操纵体系上运行：目的代码就是“汇编代码”。再通过汇编和链接的过程形成可执行文件，然后通过加载器加载到操纵体系执行。
1.2 步调编译流程
1.2.1 词法分析
源代码步调被输入到扫描器（Scanner），扫描器对源代码举行简单的词法分析，运用雷同于有限状态机（Finite State Machine）的算法可以很轻松的将源代码字符序列分割成一系列的暗号（Token）。
词法分析产生的暗号一样寻常可以分为如下几类：关键字、标识符、字面量（包含数字、字符串等）和特别符号（如加号、等号）。在辨认暗号的同时，扫描器也完成了其他工作，好比将标识符存放到符号表，将数字、字符串常量存放到文字表等，以备反面的步调使用。
例如c代码：
sum=3+2;
词法分析器通常不会关心暗号之间的关系（属于语法分析的范畴），举例来说：词法分析器可以大概将括号辨认为暗号，但并不包管括号是否匹配。
词法分析器有两大类实现方案及特点：
- 手动构造
复杂，容易堕落；
比力可控，是主流的方案（GCC、LLVM 等采取此办法）；
- 自动构造
构造速率快，工作量少；
细节难以控制；
1.2.2 语法分析
语法分析器（Grammar Parser）将对由扫描器产生的暗号举行语法分析，从而产生语法树（Syntax Tree）。
语法分析器的使命重要是确定是否可以以及怎样从语法的起始符号推导出输入符号串（输入文本），重要可以通过两种方式完成：
- 自顶向下分析：根据情势语法规则，在语法分析树的自顶向下睁开中搜刮输入符号串大概的最左推导。单词按从左到右的序次依次使用。
- 自底向上分析：语法分析器从现有的输入符号串开始，实验将其根据给定的情势语法规则举行改写，终极改写为语法的起始符号。
1.2.3 语义分析
语义分析也称为范例查抄、上下文相干分析。它负责查抄步调（抽象语法树）的上下文
1. 相干的属性，这是具体语言相干的，典范的环境包罗：
2. 变量在使用前先举行声明
3. 每个表达式都有符合的范例
4. 函数调用和函数的界说一致
1.2.4 中心代码
中心表现(intermediate representation)，简称为IR。如果源语言语法布局较为简单，编译器大概会用唯一的IR，如果源语言语法布局比力复杂（eg：rust），则在转换为目的语言的过程中大概会使用了一系列的IR。
泛泛而言，IR从布局上分为三类：
1. 图IR， 将编译器的知识编码在图中。算法通过图中的对象来表述：结点、边、列表、树。
2. 线性IR， 雷同于某些抽象机上的伪代码。相应的算法将迭代遍历简单的线性操纵序列。本书使用的ILOC代码就是一种线性IR。
3. 肴杂IR， 团结了图IR和线性IR的要素，为的是获取两者的上风而避免其缺点。一种常见的肴杂表现使用底层的线性IR来表现无循环代码的块，使用图来表现这些块之间的控制流。
更多相干内容拜见中心代码表现
具体中心代码的表现情势有多种具体请见1，2：
逆波兰表现
三地址码（三元式、四元式）
抽象语法树
P-代码
1.2.5 中心代码优化
优化实在可以在编译的各个阶段举行，但最重要的一类优化是在目的代码天生从前，对语法分析、语义分析后产生的中心代码举行优化。这是由于中心代码的情势不依赖于具体的盘算机，它可以是三地址码的情势，以是相应的对于中心代码的优化也不依赖于具体的盘算机。另一类优化是在天生目的代码时举行的，它很大步调上依赖于具体的盘算机。
优化过程中须要遵从的原则：
- 等价原则：颠末优化后不应该改变步调运行的效果。这是最不应该也不能粉碎的原则，试问步调效果都不精确了，优化的意义安在？
- 有效原则：优化后的代码运行快、存储空间需求小。这也正是我们优化代码的目的，从时空两个维度尽大概让代码服从高。
- 合算原则：尽大概以较低的代价，取得较高的优化效果。
常见的代码优化技能有：删除多余运算、归并已知量和复写传播，删除无用赋值等。更多相干内容请移步
1.2.6 目的代码天生
以根本块为单元天生目的代码（龙书：把中心代码分别成为根本块 (basic block)。每个根本块是满足下列条件的最大的连续三地址指令序列。 ①控制流只能从根本块中的第 一个指令进人该块。也就是说，没有跳转到根本块中心的转移指令。 ②除了根本块的末了一个指令，控制流在脱离根本块之前不会停机大概跳转。）更多请见
- 依次把四元式的中心代码变更成目的代码
- 在根本块的范围内思量怎样充实使用寄存器
- 进入根本块时，全部寄存器空闲
- 脱离根本块时，把存在寄存器中的现行的值存回主存中，开释全部寄存器
- 不特别阐明，全部阐明变量在根本块出口之后均为非生动变量
2. 编译过程中涉及的技能
2.1 词法分析
2.1.1 词法分析过程中涉及的点
- 词法单元(Token)：<词法单元名、属性值 (可选) >；单元名是表现词法单元种类的抽象符号，语法分析器通过单元名即可确定词法单元序列的布局；属性值通常用于语义分析之后的阶段。
- 模式 (Pattern)：形貌了一类词法单元的词素大概具有的情势；
- 词素 (Lexeme)：源步调中的字符序列； 它和某个词法单元的模式匹配，被词法分析器辨认为该词法单元的实例；
- 状态转移图：用于辨认词法单元；我们须要把模式转换成状态转换图。状态转换图有一组被称为状态的结点。每个状态代表一个大概和模式匹配的词素。状态图中的边从图的一个状态指向另一个状态。每条边的标号包含了一个或多个符号。更多请见词法分析-南京大学例如：
非确定状态的有限状态自动机（NonDeterministic Finite Automata，NFA）：
- 确定状态的有限状态自动机（Deterministic Finite Automata，DFA）：将上图中赤色的框框消撤消就完成DFA了，从NFA转换为DFA为子集构造的过程，转换过程可以参考NFA转DFA
2.1.2 词法分析工具
- flex词法分析器：Lex 是 LEXical compiler 的缩写，是一个词法分析器（scanner）的天生工具，它使用正则表达式（regular expression）来形貌各个词法单元的模式，由此给出一个词法分析器的规约，并天生相应的实现代码。 Lex 步调的输入方法称为 Lex 语言，而 Lex 步调本身被称为 Lex 编译器；flex是lex的开源版本。
- ANTLR4词法分析器：ANTLR4集词法与语法分析与一身，其词法分析的使用如下例所示，更多请见Antlr4浅显快速入门
// 表明SearchLexer.g4文件是词法分析器(lexer)界说文件// 词法分析器的名称一定要和文件名保持一致lexer grammar SearchLexer;channels { ESQLCOMMENT, ERRORCHANNEL}//SKIP 当Antlr分析到下面的代码时，会选择跳过// 遇到 \t\r\n 会忽略SPACE: [ \t\r\n]+ -> channel(HIDDEN);// 遇到 /*! */ 会看成表明跳过SPEC_ESSQL_COMMENT: '/*!' .+? '*/' -> channel(ESQLCOMMENT);// 遇到 /* */ 会看成表明跳过COMMENT_INPUT: '/*' .*? '*/' -> channel(HIDDEN);// 遇到 -- 会看成表明跳过// 遇到 # 会看成表明跳过LINE_COMMENT: ( ('-- ' | '#') ~[\r\n]* ('\r'? '\n' | EOF) | '--' ('\r'? '\n' | EOF) ) -> channel(HIDDEN);// 界说Token，模式为 {field}:{value}MINUS: '-'; //使MINUS和-等价，以下同理STAR: '*';COLON: ':'|'\uFF1A';EQ: '=';NE: '!=';BOOLOR: '||'|'|'; // 使BOOLOR与||大概|等价BOOLAND: '&&'|COMMA|'&';//CONSTRUCTORSDOT: '.' -> mode(AFTER_DOT);LBRACKET: '[';RBRACKET: ']';LPAREN: '(';RPAREN: ')';COMMA: ','|'\uFF0C'; // 使COMMA与,或，等价(\uFF0C表现，的unicode编码)SEMI: ';';GT: '>';// 这里和以下代码等价// AFTER: 'after' 但是这种代码只能表现小写的after，是巨细写区分的，如许不好// 通过下面界说的fragment，将AFTER用A F T E R表现，一定要每个字母空一格，就可以不区分巨细写了// 全部语法的关键字都发起使用这种方式声明AFTER: A F T E R;SINGLE_QUOTE: '\'';DOUBLE_QUOTE: '"';REVERSE_QUOTE: '`';UNDERLINE: '_';CHINESE: '\u4E00'..'\u9FA5'; //表现全部中文的unicode编码，以支持中文ID: (CHINESE|ID_LETTER|DOT|MINUS|UNDERLINE|INT|FLOAT|REVERSE_QUOTE|DOUBLE_QUOTE|SINGLE_QUOTE)+;// ? 表现无关紧要// + 表现至少有一个// | 表现或的关系// * 表现有0大概多个INT: MINUS? DEC_DIGIT+;FLOAT: (MINUS? DEC_DIGIT+ DOT DEC_DIGIT+)| (MINUS? DOT DEC_DIGIT+);// 使用DEC_DIGIT代表0到9之间的数字fragment DEC_DIGIT: [0-9]; // 使用ID_LETTER代表a-z的大写小写字母和_fragment ID_LETTER: [a-zA-Z]| UNDERLINE;// 表现用A代表a和A，如许就可以不区分巨细写了，以下同理fragment A: [aA]; fragment B: [bB];fragment C: [cC];fragment D: [dD];fragment E: [eE];fragment F: [fF];fragment G: [gG];fragment H: [hH];fragment I: [iI];fragment J: [jJ];fragment K: [kK];fragment L: [lL];fragment M: [mM];fragment N: [nN];fragment O: [oO];fragment P: [pP];fragment Q: [qQ];fragment R: [rR];fragment S: [sS];fragment T: [tT];fragment U: [uU];fragment V: [vV];fragment W: [wW];fragment X: [xX];fragment Y: [yY];fragment Z: [zZ];mode AFTER_DOT;//DEFAULT_MODE是Antlr中默认界说好的modeDOTINTEGER: ( '0' | [1-9] [0-9]*) -> mode(DEFAULT_MODE);DOTID: [_a-zA-Z] [_a-zA-Z0-9]* -> mode(DEFAULT_MODE);2.2 语法分析
2.2.1 文法
文法G 界说为四元组（VN ,VT ,P,S）
VN ：非闭幕符集
VT ：闭幕符集
P ：产生式聚集（规则聚集）
S ：开始符号（辨认符号
- 0型文法：0型文法也称为短语文法，0型文法的本领相称于图灵机（Turing）。大概说，任何0型语言都是递归可罗列的；反之，递归可罗列集必定是一个0型语言。 对0型文法产生式的情势作某些限定，以给出1，2和3型文法的界说。
- 1型文法（上下文有关文法）：此文法对应于线性有界自动机。它是在0型文法的根本上每一个α→β,都有|β|>=|α|。这里的|β|表现的是β的长度
- 2型文法（上下文无关文法，context-free grammar，CFG）：它对应于下推自动机。2型文法是在1型文法的根本上,再满足：每一个α→β都有α是非闭幕符。
- 3型文法（右线性/左线性/正规文法）：它对应于有限状态自动机。它是在2型文法的根本上满足:A→α|αB（右线性）或A→α|Bα（左线性）；
2.2.2 语法分析中的技能
- 自顶向下分析算法
- 递归降落分析算法（自顶向下）
- LL (1) 分析算法（自顶向下）
- 自底向上分析算法
自顶向下分析就是从起始符号开始，不绝的挑选出符合的产生式，将中心句子中的非闭幕符的睁开，终极睁开到给定的句子。它的焦颔首脑在于，当我们从左往右匹配这个句子的时间，每匹配一次须要从上往下遍历一次这个 CFG 从而找到符合的产生式，以是被称为自顶向下分析算法。
递归降落分析算法本质也是一种自顶向下分析算法，其根本头脑如下：(1)对每一个非闭幕符构造一个分析函数;(2)用前看符号引导产生式规则的选择。递归降落分析算法使用 “分治法” 来进步分析的服从，对于每一个产生式规则，都应该界说一个本身函数。由于在上下文无关文法中，闭幕符不大概出如今产生式的左边（可以在产生式左边出现闭幕符的文法叫做上下文有关文法），上下文无关文法中全部的产生式左边只有一个非闭幕符。以是我们在调用产生式规则的函数后，就分为两种环境：（1）遇到闭幕符，由于闭幕符本质上是 token，以是直接把这个闭幕符和句子中对应位置的 token 举行比力，判定是否符合即可；符合就继承，不符合就返回；（2）遇到非闭幕符，此时只须要调用这个非闭幕符对应的函数即可。在这里函数大概会递归的调用，这也是算法名称的泉源。同上例
EOF = '\n' # 用换行符作为EOF符号class Parser(object): def __init__(self, sentence): self.sentence = sentence self.current_pos = 0 # 当前的token下标 def parse_S(self): self.parse_A() self.parse_B() def parse_A(self): token = self.get_next_token() # 从句子中取出一个Token if token == 'a': # 和CFG中的Token举行比力 self.parse_A() # 执行非闭幕符所对应的函数 elif token != 'a': self.put_token_back() def parse_B(self): token = self.get_next_token() if token == 'b': token = self.get_next_token() if token == EOF: pass else: self.parse_B() else: raise Exception('非闭幕符 B 分析非常') def get_next_token(self): if self.current_pos == len(self.sentence): raise Exception('数组越界') next_token = self.sentence[self.current_pos] self.current_pos += 1 return next_token def put_token_back(self): self.current_pos -= 1if __name__ == '__main__': sentence = 'aab' parser = Parser(sentence + EOF) parser.parse_S() 以上代码只要能正常运行竣事而不出现非常，就阐明句子’aab’符合此文法。（1）由于 S 的产生式是非闭幕符 A 和 B，以是只须要调用 A 和 B 的函数即可；（2）A 产生式涉及到了闭幕符，以是我们须要先从句子取一个 Token，然后根据 Token 的值举行逻辑判定：如果 token 是 a，则获取到非闭幕符 A，继承递归执行 A 的函数；如果不是 a，那么不做任何操纵，还要把当前的 token 放回到句子中；（3）B 产生式第一个 token 是一样的，无法举行区分，我们可以用第二个 token 判定：如果已经到了句子末端（也就是说此 token 不是 b），不做任何操纵；如果尚有 token，则继承执行。
LL (1) 算法也是一个自顶向下的分析算法，它的界说为：从左（L）向右读入一个步调，最左（L）推导，采取一个（1）前看符号。LL (1) 算法和自顶向下分析算法本质上是一致的，它们的区别就在于 LL (1) 算法使用了一种称为分析表的工具来避免了回溯操纵，进步了服从。在实际中，我们可以根据某种 LL (1) 分析器来生因素析表，之后根据分析表来举行语法分析操纵，我们可以以为这种方法是一种半自动的语法分析方法。LL (1) 的总体工作方式如下所示：
例如对于文法：1.S → F，2.S → ( S + F )，3.F → 1，分析“( 1 + 1 )”
最开始栈中的元素为：S；执行 else 中的代码，把 S pop 出去。此时第一个 token 为 (，查阅分析表可得我们应该执行产生式 2，以是被 push 举行 stack 的值为 (S + F)
此时栈为： (S + F)；栈顶元素 (便是当前的 token，( 被 pop，token 向后移一位
栈：S + F)；当前 token 为 1，栈顶元素 S，查分析表可得产生式 1，栈变为 F + F)
栈：F + F)；栈顶 F，token 1
栈：1 + F)；栈顶 1，token 1
栈：+ F)；栈顶 +,token +
栈：F)；栈顶 F，token 1
栈：1)；栈顶 1，token 1
栈：)；栈顶 )，token )
栈：None；token 为空。流程竣事
自底向上分析算法是语法分析的另一类告急算法，它包含了 LR (0) 算法、SLR 算法和 LR (1) 算法。自底向上分析算法的重要方式是根据句子的 Token，使用产生式来自右向左举行分析，即把右侧的内容 “紧缩” 为左侧的非闭幕符，这种举动我们称为规约（reduce）。自底向上语法分析算法是从语法分析树的叶子节点开始，渐渐向上到达根节点，反向构造出一个最右推导序列，从而构建完备的语法分析树，适用于LR(k)文法。LR(k)文法的L是输入从左到右，R是反向最右推导（rightmost derivation in reverse），k是前瞻符号数量。更多表明请移步语法分析。
2.2.3 语法分析工具
- yacc是一个LALR（1）分析器自动天生器，是贝尔实验室在UNIX上初次实现，与LEX有直接的接口，一样寻常使用是 Yacc + Lex 或 Bison + Flex；其使用先容可以移步高效分析器 Lex&YACC(Flex&Bison) 使用教程大概yacc
- ANTLR4：ANTLR（全名：ANother Tool for Language Recognition）是基于LL(*)算法实现的语法分析器天生器（parser generator），用Java语言编写，使用自上而下（top-down）的递归降落LL分析器方法。由旧金山大学的Terence Parr博士等人于1989年开始发展。使用例程请移步Antlr4浅显快速入门
2.3 语义分析
语法分析基于CFG（Context-Free Grammar）上下文无关文法，因此无法做语义分析；语义分析往往与语法元素的上下文密切相干。
2.3.1 语义分析的具体内容
查抄步调是否符合语言的语义规则：
- 范例规则
- 变量使用规则
- 函数调用 (foo(…)) 规则
- 属性访问 (x.f) 规则
- ...
Syntax-Directed Definition n (SDD) 是上下文无关文法和属性/规则的团结：（1）属性和文法符号相干联，按照须要来确定各个文法符号须要哪些属性；（2）规则和产生式相干联。SDD三要素：文法、属性、规则，此中属性可视为语义的具象化表现：范例、值、名字、地址。一个分析树结点和它的分支对应一个产生式规则，而对应的语义规则确定了这些结点上属性的取值和盘算。
- 综合属性 (Synthesized Attribute)（自底向上）：结点N的属性值由N的产生式所关联的语义规则来界说；通过N的子结点或N本身的属性值来界说
- 继承属性 (Inherited Attribute)（自顶向下）：结点N的属性值由N的父结点所关联的语义规则来界说；依赖于N的父结点、N本身和N的兄弟结点上的属性值；
- 不允许N的继承属性通过N的子结点上的属性来界说，但允许N的综合属性依赖于N本身的继承属性；闭幕符号有综合属性 (来自词法分析)，但无继承属性；
- 只包含综合(Synthesized)属性的SDD称为S属性的SDD：每个语义规则都根据产生式体中的属性值来盘算头部，非闭幕符号的属性值
- S属性的SDD可以和LR语法分析器一起实现：栈中的状态/文法符号可以附加相应的属性值；归约时，按照语义规则盘算归约得到的符号的属性值；没有副作用的SDD称为属性文法 (Attribute Grammar)。
3 参考
（1）一篇文章明白编译全过程
（2）GCC编译器原理
（3）词法分析维基百科
（4）词法分析
（5）语法分析
（6）语法分析维基百科
（7）语义分析
（8）文法分类
（9）编译原理之文法分类
（10）语法分析 |
