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)：源程序中的字符序列； 它和某个词法单元的模式匹配，被词法分析器识别为该词法单元的实例；
• 状态转移图：用于识别词法单元；我们需要把模式转换成状态转换图。状态转换图有一组被称为状态的结点。每个状态代表一个可能和模式匹配的词素。状态图中的边从图的一个状态指向另一个状态。每条边的标号包含了一个或多个符号。更多请见词法分析-南京大学例如：
  
  

  词法单元relop状态转移图

• 非确定状态的有限状态自动机（NonDeterministic Finite Automata，NFA）：
  

  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的开源版本。
  
  

  lex程序的结构
  
  
  

  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|'&';

//CONSTRUCTORS

DOT: '.' -> 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中默认定义好的mode
DOTINTEGER: ( '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 -= 1


if __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）语法分析