最近在学习编译原理相关知识，主要看的是编译器前端分析技术，主要学习的有词法分析、语法分析、语义分析、有限自动机、上下文无关文法、BNF范式、语法分析树等相关前端概念内容，后续可能使用Anltr或Peg对特定的DSL代码进行解析，学习相关内容更加有助于理解解析过程和原理。

一、编译器工作流程

整个编译器的工作流程可以概括为前端、中端和后端，如下图所示。编译器的前端主要任务是对代码字符流进行词法分析，得到符号Token流，然后通过语法分析将Token流进行文法校验，生成语法解析树，最后进行语音分析对类型和各种转义情况作处理，生成最终的语法解析树。编译器的中端和后端任务是对这颗语法解析树进一步分析，生成指定语言的中间表示，并进行机器码优化和目标操作系统环境适配，从而生成特定的目标机器语言。

前端分析各阶段的重点内容：

• 一、词法分析：正则表达、Token流、有限状态机（图）
  • 目标：将对应的代码字符串转化为Token流。
• 二、语法分析：(E)BNF、递归下降、左递归、上下文无关文法、左推导、AST语法解析树、LL、LR
  • 目标：将Token流作为待校验的句子s，通过已定义的上下文无关文法G，来校验s是否能被G所推倒，从而生成AST语法解析树。
• 词法分析和语法分析相关工具：Antlr、Peg，通过自定义的解析规则对源代码解析，生成特定的AST。
• 三、语义分析：符号表、类型检查、类型转化
  • 目标：通过符号表中对应的规则，对已生成的AST进行校验，核心是类型检查、类型转换。

二、重点内容和概念总结

2.1、词法分析

词法分析的任务是从源代码中读取输入字符，按照构词规则构词规则切分成一系列的单词（token），提交给语法分析使用。词法分析器的分析结果，即输出为token序列，其中token包含两部分内容，即token=类型枚举+属性值，token也被称为“词素”，指的是单个有意义的元素。token可使用如下对象表示：
<token-type, attribute-value>

比如有如下源程序：
int a = 3 * b;

这条语句可以映射成如下词法单元. 并且这些词法单元将被传递给语法分析阶段：

• int 是一个词素，属于声明关键字类型，值为int，被映射成词法单元 <declaration,int>
• a是一个词素，属于标识符类型，值为a，被映射成词法单元 <id,a>
• = 是一个词素, 属于赋值类型，值为=，被映射成词法单元 <assignment,=>，当然也可以忽略掉属性值，直接写为或<=>
• 3 同样是一个词素, 属于数字字面量类型，值为3，被映射成词法单元 <int_literal , 3>或
• • 也是一个词素, 属于运算符类型，值为*,被映射成词法单元<star, >或、<>
• b 被映射成词法单元 <id , b>
• ; 是一个词素，属于终结符类型，值为;，被映射为词法单元<terminator,;>或或<;>
• 分割词素的空格被词法分析器忽略掉
  经过上述的词法分析，就可以得到该代码的Token流如下：
  [<declaration,int>, <id,a>, , <int_literal , 3>,, <id , b>,]

2.1.1、符号串

• 字母表（符号表，符号集）：由若干元素（符号、字母）组成的有限非空集合称为字母表
• 符号串：由字母表中的符号组成的任何有穷序列称为符号串
• 空符号串εε：不包含任何符号的符号串，其长度为0
• 符号串的方幂：符号串自身连接𝑛n次得到的符号串𝑥𝑛xn 定义为 𝑥𝑥…𝑥𝑥xx…xx； 𝑥1=𝑥x1=x, 𝑥2=𝑥𝑥x2=xx，且规定𝑥0=εx0=ε
• 符号串集合（或语言）：若集合A中所有元素都是某字母表ΣΣ上的符号串，则称A为字母表ΣΣ上的符号串集合（或语言）
• 符号串集合常用操作：
  

2.1.2、正则表达式

正则表达式在词法分析中有所应用，正则表达式使用特定的运算符运算符及运算对象运算对象按规则构造的表达式，是描述语言词法规则的形式化工具。和下文要提到的上下文无关文法不同的是，正则表达式无法嵌套递归。以下是基本的正则表达式规则：

2.1.3、有限状态机(FSM)

有限状态机,也称为FSM(Finite State Machine)，其在任意时刻都处于有限状态集合中的某一状态。当其获得一个输入字符时，将从当前状态转换到另一个状态，或者仍然保持在当前状态。任何一个FSM都可以用状态转换图来描述，图中的节点表示FSM中的一个状态，有向（方向表示从一个初态转换到次态）加权（权表示事件）边表示输入字符时状态的变化。如果图中不存在与当前状态与输入字符对应的有向边，则FSM将进入“消亡状态(Doom State)”，此后FSM将一直保持“消亡状态”。状态转换图中还有两个特殊状态：状态1称为“起始状态”，表示FSM的初始状态。状态6称为“结束状态”。

状态机的四要素

状态机可归纳为4个要素，即现态、条件、动作、次态。“现态”和“条件”是因，“动作”和“次态”是果。详解如下：

• 现态：是指当前所处的状态。
• 条件：又称为“事件”。当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。
• 动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。
• 次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。

无限状态机

无限状态机拥有无限个状态，也就是状态集合是无穷大的，其输出不止与输入相关，还和当前状态相关。

有限状态自动机(DFA)

一般来讲，有限状态机（FSM）在转变状态同时会进行输出，而有限状态自动机（一般使用的都是确定性有限状态机DFA，简称有限自动机）主要工作是进行状态转变，而不具备输出。

确定性有限自动机的组成如下：

• 有限个输入符号组成的集合，记作Σ
• 有限个状态的集合，记作𝑆
• 转换函数𝑇:S×Σ→S
• 初始状态𝑠0∈𝑆0∈S,识别符号串的起始状态
• 若干个识别符号串的接受状态（或称为终止状态）的集合𝐴⊆𝑆
  由上述五个元素组成的五元式𝑀=(𝑆,Σ,𝑇,𝑠0,𝐴)称为一个确定的有限自动机。
  

如果状态结点通过a条件进行改变，则状态转化图为：

以下是一个词法分析中的标识符、比较操作符和数字字面量的有限自动机，可以解析如 age >= 10 这样的比较操作并生成Token流：

状态转化图

有一组被称为“状态”（state）的节点或圆圈。词法分析器在扫描输入串的过程中寻找和某个模式匹配的词素，而状态转换图中的每个状态代表一个可能在这个过程中出现的情况。状态图中的边（edge）从图的一个状态指向另一个状态。这也是有限自动机分析最重要的一步：
状态转换图的约定：

• 约定1：某些装成为接受状态或最终状态。这些状态表明已经找到了一个词素。我们用双层的圆圈来表示一个接受状态。
• 约定2：如果需要将forward回退一个位置，那么将在该接受状态的附加加上一个*。
• 约定3：有一个状态被指定为开始状态，也叫初始状态。
  

梳理出状态转换图，是构造有限自动机的基础。

最小化DNA的方法

将识别功能相同的状态合并为一个状态，通过状态等价类划分来实现
对于任意给定的输入串w，若DFA分别从状态𝑠1s1和𝑠2s2出发，对于是否接受w有相同的结论，则称状态𝑠1和𝑠2位于同一个等价类s1和s2位于同一个等价类，否则称状态s1和s2是可区分的。
DFA最小化的算法步骤为:

1. 将状态集合𝑆S分为两个等价类：𝐴A和𝑆−𝐴S−A
2. 细分等价类：对于当前划分的某个等价类K，𝑠1,𝑠2∈𝐾s1,s2∈K，如果满足
3. 存在𝑎,𝑠1或𝑠2中的一个无法识别𝑎存在a,s1或s2中的一个无法识别a
4. 存在𝑎,𝑠1或𝑠2识别𝑎后到达的状态分别在目前划分的不同等价类中存在a,s1或s2识别a后到达的状态分别在目前划分的不同等价类中
5. 那么K就划分为不同的等价类𝐾𝑖,𝐾𝑗,使得𝑠1∈𝐾𝑖,𝑠2∈𝐾𝑗Ki,Kj,使得s1∈Ki,s2∈Kj
6. 递归上述步骤2中细分等价类的工作，直到所有等价类都不能再细分为止

用代码实现有限自动机

• 首先画出状态转化图，确定状态及转换条件(词法分析中，以单个字符作为状态转化条件)
• 将每个状态抽象成枚举类型
• 确定初始化状态
• 不同的状态之间进行切换时，保留下当前状态的字符串(也就是Token)
• 生成Token列表

2.2、语法分析

语法分析以词法分析程序输出的Token流为输入，分析源程序的语法结构，判断它是否为相应程序设计语言的合法程序，最后生成符合特定文法的语法分析树。

2.2.1、上下文无关文法及BNF范式规则

上下文无关文法

一个正则表达式可以用来表示一个句子集合（正则语言），且每个正则表达式都可以构造出有限状态自动机来判断任意的句子是否属于这个句子集合，但是正则表达式无法解析出动态的、复杂的程序代码，所以需要使用上下文无关文法这个分析工具。

上下文无关文法拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字符串是否是由某个上下文无关文法产生的。例子可以参见LR分析器和LL分析器。

BNF（巴克斯-诺尔范式）经常用来表达上下文无关文法。

上下文无关文法的核心在于选择和替换。假设一个句子S具备主、谓、宾三个组成结构，并且主语可以是你、我、他、它，谓语可以是吃、看、摸、玩，宾语可以是书、电脑、游戏，那么可以从上至下描述这个句子，这也就是一个基本的上下文无关文法了：
S -> 主 谓 宾
主 -> 你 | 我 | 他 ｜ 它
谓 -> 吃 | 看 | 摸 | 玩
宾 -> 书 | 电脑 | 游戏

以下是上下文无关文法的一些术语：

• 解析（parse） ：语法分析的主要工作就是解析，指的是给定一个句子 s 和语法 G ，判断 s 是否属于 G ，如果是，则找出从起始符号推导得到 s 的全过程并生成语法分析树。推导过程中的任何符号串（包括起始符号和最终的句子）都称为 中间句子（working string） 。
• 终结符集合 T （terminal set） ： 一个有限集合，其元素称为 终结符（terminal）,终结符指的是无法被展开的符号，比如吃、 看、书、电脑等无法被继续展开 。
• 非终结符集合 N （non-terminal set) ： 一个有限集合，与 T 无公共元素，其元素称为 非终结符（non-terminal），非终结符指的是可以被展开的符号，比如主、谓、宾等可被继续展开 。
• 符号集合 V （alphabet） ： T 和 N 的并集，其元素称为 符号（symbol） 。因此终结符和非终结符都是符号。符号可用字母：A, B, C, X, Y, Z, a, b, c 等表示。
• 符号串（a string of symbols） ： 一串符号，如 X1 X2 … Xn 。只有终结符的符号串称为 句子（sentence）。 空串 （不含任何符号）也是一个符号串，用 ε 表示。符号串一般用小写字母 u, v, w 表示。
• 产生式（production） ： 一个描述符号串如何转换的规则。对于上下文本无关语法，其固定形式为： A -> u ，其中 A 为非终结符， u 为一个符号串。
• 产生式集合 P （production set） ： 一个由有限个产生式组成的集合。
• 展开（expand） ： 一个动作：将一个产生式 A -> u 应用到一个含有 A 的符号串 vAw 上，用 u 代替该符号串中的 A ，得到一个新的符号串 vuw 。
• 折叠（reduce） ： 一个动作：将一个产生式 A -> u 应用到一个含有 u 的符号串 vuw 上，用 A 代替该符号串中的 u ，得到一个新的符号串 vAw 。
• 起始符号 S （start symbol） ： N 中的一个特定的元素。
• 推导（derivate） ： 一个过程：从一个符号串 u 开始，应用一系列的产生式，展开到另一个的符号串 v。若 v 可以由 u 推导得到，则可写成： u => v 。
• 上下文本无关语法 G （context-free grammar, CFG） ： 一个 4 元组： (T, N, P, S) ，其中 T 为终结符集合， N 为非终结符集合， P 为产生式集合， S 为起始符号。一个句子如果能从语法 G 的 S 推导得到，可以直接称此句子由语法 G 推导得到，也可称此句子符合这个语法，或者说此句子属于 G 语言。 G 语言（ G language） 就是语法 G 推导出来的所有句子的集合，有时也用 G 代表这个集合。

BNF范式

BNF范式是上下文无关文法的一种描述形式，BNF描述了推导规则(产生式)的集合，基本结构为：
< non-terminal> ::= < replacement>

BNF规定：
< > : 内包含的为必选项，非终结符。
“…” : 术语符号,终结符
[ ] : 内包含的为可选项。
{ } : 内包含的为可重复0至无数次的项。
| : 表示在其左右两边任选一项，相当于"OR"的意思。
::= : 是“被定义为”的意思
[…] : 选项，最多出现一次
{…} : 重复项，任意次数，包括 0 次
(…) : 分组
| : 并列选项，只能选一个

以下是Java for语句的BNF定义：
FOR_STATEMENT ::=
“for” “(” ( (variable_declaration “;”) |( expression “;” ) | “;” )
[ expression ] “;”
[ expression ] “)”
statement

2.2.2、语法分析树

语法分析的作用是，根据定义的文法G，对Token串s进行校验与分析，并生成一棵语法分析树AST。
语法分析树的作用是让计算机程序理解Token串的含义，并根据相关的算法对树进行遍历或解析，从而生成该Token串表达的结果。

例如要解析加法表达式，首先通过词法分析生成了如下Token串:
[<number,12>, <+>, <number,53>]

根据加法表达式的BNF：
::=
“+”
| “+”
| + number
| number + number
| number
::=
“-”
| “(” “-” “)”
| - number
| number - number
| number

推导12 + 53语法解析树：
Expr ==> Expr + Expr ==> number + Expr ==> number + number ==> 12 + 53

推导12 + (53 - 7)语法解析树：
Expr ==> Expr + Expr ==> number + Expr ==> number + Expr2 ==> 12 + (Expr2 - Expr2) ==> 12 + (number - number) ==> 12 + (53 - 7)

对于上面两颗语法分析树来说，只需要通过后序遍历就可以正确计算表达式的结果了，一般情况下也是对生成的语法分析树进行后序遍历分析，因为采用后序遍历才可以从树的底层开始计算，直至上层获取到最终的结果，语法解析树的优先级也是叶子结点优先、根结点最后计算的。

2.2.3、递归下降分析

在语法解析的过程中，BNF产生式的左边会被右边替代，如果替代之后还有非终结符，那么继续这个替代过程，直到最后全部都是终结符，只有终结符才可以成为AST的叶子节点，这个过程被称为做推导过程，整个过程被称为递归下降分析。在这个过程中，上级文法嵌套下级文法，上级的算法调用下级的算法。表现在生成AST中，上级算法生成上级节点，下级算法生成下级节点。这就是“下降”的含义，而程序结构基本上是跟文法规则同构的。

2.2.4、左递归问题和二义性问题

在推导过程中，假如产生式 S ::= S + T, 即产生式的第一个元素是它自身，那么程序就会无限地递归
下去，这种情况就叫做左递归。左递归问题通常可以通过移换元素位置使其不为第一个元素来解决，比如 S ::= S + T可以写为S ::= T + S,这种方法被称为右递归，通过右递归会产生书面表达顺序错乱问题，所以要消除左递归，还可以采用文法改写的方法：

二义性问题指的是在推导的过程中，由于优先级不确定导致同一式子产生了多个推导过程，生成多棵语法分析树，导致计算结果出错，比如12+53*7具有两种推导：

为了避免二义性，需要确定表达式的优先级和顺序。

2.2.5、LL及LR分析

LL(1) 分析法是一种自顶向下分析方法，它通过精心构造语法规则而使得每个推导步可以直接挑选出合适的产生式。
LL(1) 法的基本思路为：

• 每个推导步中，从左向右比较中间句子和最终句子，找到第一个不匹配的符号，如：中间句子为 u X v 、最终句子为 u a w 。显然，a 一定是终结符， X 则可能为非终结符，也可能为终结符，有以下 4 种情况：
• 情况 A ： X 为终结符，这种情况表明无论怎么展开都不可能展开到最终句子，即最终句子不合语法，此时终止推导。
• 情况 B ： X 为非终结符，假设它的所有产生式为 X -> u1 | u2 | … | un ，将 a 和这些产生式的右边 u1, u2, … , un 相比较，找出可以和 a 匹配的 ui ，将 ui 代替中间句子 u X v 中的 X ，得到下一个中间句子 u ui v，然后开始下一轮展开。
• 情况 C ： X 为非终结符，但它的所有产生式的右边 u1, u2, … , un 中，没有一个可以和 “a” 匹配上，这种情况表明最终句子不合语法，此时终止推导。
• 情况 D ： X 为非终结符，但它的所有产生式的右边 u1, u2, … , un 中，有两个或以上的 ui 可以和 “a” 匹配上，这种情况表明此语法不适于用 LL(1) 分析法，需要修改语法。
  所谓的 LL(1) ，第一个 L 表示从左向右扫描输入流，第二个 L 表示每一步展开的时候取中间句子中左边第一个非终结符进行展开，括号里面的 1 表示每次只读入 1 个符号，每次只利用这 1 个符号的信息来挑选产生式。
  事实上，还有 LL(2) 、LL(3) 、 LL(k) 等分析法，每次一次性读入多个符号，然后利用这些符号的信息来挑选产生式。

自底向上分析法的解析力量比自顶向下分析法要强大的多，和自顶向下分析法相比，它可以解析更为复杂、更为广泛的语法。但自底向上分析法的构造过程也复杂的多，LR 分析法是一种常见的自底向上分析法。

2.3、语义分析

语义分析器(semantic analyzer) 使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致, 同时它也收集类型信息，并把这些信息存放在语法树或符号表中,供随后的中间代码生成使用。
语义分析有个重要的步骤是类型检查，编译器检查每个运算符是否具有匹配的运算分量，如Java和C中要求数组的下标必须是整数，若果用一个浮点数作为数组的下标，编译器必须报出错误, 并给出相应的提示，有些编译器允许自动类型转换, 如Java和C，这些都是在语义分析阶段进行操作。当一个运算符应用于一个浮点数和一个整数时, 编译器自动会将该整数转换成一个浮点数. 如下图显示了语义分析器的工作,展示了一个自动类型转换：

2.4、代码生成

不同的编译器对中间表示的选择和设计各有不同。中间表示可以是一种真正的语言，也可以是由编译器的各个处理阶段共享的多个内部数据结构组成。C语言是一种程序设计语言。它具有很好的灵活性和通用性，可以很方便的把C程序编译成高效的机器代码，并且有很多C的编译器可用。因此C语言也常常被用作中间表示。早期的C++编译器的前端生成C代码，而把C编译器作为后端。
代码生成属于编译器的后端技术，是实现一门编译型跨平台语言编译器必须掌握的技术，由于本文篇幅有限以及日常工作中不会涉及，故留到下次有需要学习时再介绍了。