第四节 编译器前端

编程语言用到的编译器，说到底就是一种翻译工具，将一种计算机语言翻译为另一种计算机语言。编译器前端指的是编程语言的语法分析部分。

BNF（巴科斯-诺尔范式）

在BNF出现之前的年代，计算机先驱们用字符串处理、正则表达式来解析语言文法，对中缀运算符通过波兰、逆波兰表达式等方式格式化处理。这种方式虽然能解析语言代码，但新的问题随之未来：语法解析方式与编译器代码耦合度极高，开发编译器虽然能一把梭，但在需要升级语言，修改语言语法的情况下，改起来如同地狱。

BNF实际是一种文法描述方式，能描述绝大部分计算机语言语法。它有非终结符与终结符两种类型的描述符。非终结符就类似二叉树（多叉树）的根节点和子节点，终结符就类似二叉树（多叉树）的叶子节点。其中根节点与子节点用于描述这棵树允许的生产方式，叶子结点就是编程语言的文本。

	非终结符	终结符
描述对象	非终结符及终结符的组合	某一个或多个固定的文法内容

编译过程就像把一串代码塞给二叉树（多叉树）的根节点，然后让二叉树（多叉树）自由生长，当最后生长出来的形状通过中序遍历（打个比方）刚好能输出这一串代码，那么就完成了代码的解析。这棵树不是二叉树，它真实存在，名叫AST（语法解析树）。

Antlr

Antlr是一个基于BNF改进的文法解析库，它使用了LL方式来解析自定义文法。它是目前使用最广泛的文法解析库。

举例使用Antlr描述四则运算

ADD_SUB:      '+' | '-';
MUL_DIV:      '*' | '/';
four_op:     ADD_SUB | MUL_DIV;
RAW_NUM:     [0-9]+;
num:         ADD_SUB RAW_NUM;
quotexpr:    '(' expr ')';
atom:        num | quotexpr;
expr:        atom (four_op atom)*;

其中大写字母开头的为终结符，小写字母开头的为非终结符，一行描述一种解析规则。规则语法是：

终结符或非终结符名称: 语法表达式;

语法表达式可以写圆括号()代表分组，问号?代表前者匹配0或1次，星号*代表前者匹配任意次数（0次或无数次），加号+代表前者匹配1次以上。

LL与LR

LL就是从根节点开始，一枝一丫解析代码，最终生成整棵树。LR就是从叶子结点开始，一步一步逆推树结构，最终生成整棵树。

	LL	LR
理解的难易度	易	难
使用情况	广泛使用	极少使用
性能	偏高	偏低
是否有左递归问题	有（可以解决）	无
表达范围	相同	相同

LL与LR解决不了的问题

TODO

就业方向

• 基础设施（编程语言）领域