一文了解 Yacc、Lex、JavaCC、ANTLR 等编译器相关概念

Compiler

定义一种“上下文无关文法”（context-free grammar，CFG），然后写一个 C 程序来解释这种 CFG，那么这个 C 程序就叫做“编译器”（compiler）。只不过这个编译器只能编译特定的 CFG，就像 g++ 只能编译 C++，javac 只能编译 Java 代码，这些都是编译器。

CC

CC 即 compiler-compiler，意思是“编译器的编译器”，另外还可以叫做 compiler generator。

对于任意给定的 CFG，如果可以写出一个 C 程序，生成另一段 C 程序代码，这段 C 程序代码是给定 CFG 的编译器。那么，这个 C 程序就叫做 CC。

Yacc、Bison

Yacc 即 Yet Another Compiler-Compiler，是经典的生成语法分析器的工具，将任何一种编程语言的所有语法翻译成针对此种语言的 Yacc 语法解析器。

Yacc 采用自下而上（LALR）语法分析方法，输入是巴科斯范式（Backus-Naur Form，BNF）表达的语法规则以及语法规约的处理代码，输出的是基于表驱动的编译器，包括输入的语法规约的处理代码部分。

Yacc 最初由 AT&T 的 Steven C. Johnson 为 Unix 操作系统开发，后来一些兼容程序如 Berkeley Yacc（byacc）、GNU Bison 相续出现。它们在原先基础上做了一些改进或者扩展，但基本概念是相通的。

GNU Bison 是 Yacc 的 GNU 自由软件版本，基本兼容 Yacc，并做了一些改进。在新近版本中，除了与 Yacc 相同的 LALR 语法分析，Bison 还增加了对 GLR（Generalized LR） 语法分析的支持。

Lex、Flex

Lex 是 LEXical compiler 的缩写，是一个词法分析器（scanner）的生成工具，它使用正则表达式（regular expression）来描述各个词法单元的模式，由此给出一个词法分析器的规约，并生成相应的实现代码。 Lex 程序的输入方法称为 Lex 语言，而 Lex 程序本身被称为 Lex 编译器。

Yacc 生成的编译器主要是用 C 语言写成的语法解析器（Parser），需要与词法分析器一起使用（一般为 Lex），再把两部分产生的 C 程序代码一起编译。描述词法分析器的文件 *.l，经过 Lex 编译后，生成一个 lex.yy.c 的文件，然后由 C 编译器编译生成一个词法分析器。词法分析器，简单来说，其任务就是将输入的各种符号，转化成相应的标识符（token），转化后的标识符很容易被后续阶段处理。

Flex 是 Lex 的开源版本，是 Lex 编译器的一种替代实现。

JavaCC

JavaCC 即 Java Compiler Compiler，是开源、轻量的语法分析器生成器和词法分析器生成器，采用纯 Java 编写，可生成 Java、C++ 和 C# 代码。ANTLR 根据输入的文法生成由 Java 语言编写的分析器，相当于 Java 界的 Yacc + Lex 或 Bison + Flex。

和 YACC 类似，JavaCC 由（Extended Backus-Naur Form，EBNF） 格式的形式文法生成语法分析器。不同的是，JavaCC 生成的是自顶向下 LL 语法分析器对 CFG 进行解析。同时，JavaCC 生成词法分析器的方式也和 Lex 很像。JavaCC 还提供 JJTree 帮助使用者构建语法树，JJDoc 工具为源文件生成 BNF 范式文档。

JavaCC 源自著名的 Sun 公司。1996 年，Sun 推出了一个名为 Jack 的语法解析器生成器。后来，负责“Jack”的开发者创办了自己的公司 Metamata，并将 Jack 改名为 JavaCC。Metamata 最后成为了WebGain 的一部分，后 WebGain 关闭。目前 JavaCC 代码以 BSD 许可证托管在 GitHub。

很多著名开源项目用到了 JavaCC，包括：

• Apache ActiveMQ
• Apache Zookeeper
• Apache Lucene
• Apache Tomcat
• Apache Avro
• Apache Camel
• Apache Calcite

ANTLR

ANTLR 即 ANother Tool for Language Recognition，是基于自顶向下的递归下降 LL 算法实现的语法解析器生成器（parser generator），采用纯 Java 语言编写。ANTLR 能够自动生成解析器，并将用户编写的 ANTLR 语法规则直接生成目标语言的解析器。所生成的解析器客户端将输入的文本生成抽象语法树，并提供遍历树的接口，以访问文本的各个部分。

ANTLR 是 Terence Parr 在普渡大学攻读硕士学位时的创作，在著名编译器领域大师 Hank Dietz 教授的指导下，开始研究构造自动化的分析器。1993年，Parr 取得博士学位，并于同年发布 ANTLR 1.10 版。最早的 ANTLR 只支持 Java, 直到 ANTLR 3 以后开始支持 Ada95、C、C＃、JavaScript、Objective-C、Perl、Python、Ruby、C++ 和 Standard ML。

ANTLR 生成的代码与使用递归下降法（构造手工分析器的主要方法）产生的代码非常相似，便于程序员阅读和理解，与 Yacc 产生的晦涩代码相比进步了很多。与 JavaCC 相比，ANTLR 功能更加全面，开箱即用，另外支持语言更丰富，不止局限于 Java 语言。

使用 ANTLR 的著名项目包括：