ANTLR

http://blog.csdn.net/dc_726/article/details/45399371

当我们实现一种语言时,我们需要构建读取句子 (sentence) 的应用,并对输入中的元素做出反应。如果应用计算或执行句子,我们就叫它解释器 (interpreter) ,包括计算器、配置文件读取器、Python解释器都属于解释器。如果我们将句子转换成另一种语言,我们就叫它翻译器 (translator) ,像Java到C#的翻译器和编译器都属于翻译器。不管是解释器还是翻译器,应用首先都要识别出所有有效的句子、词组、字词组等,识别语言的程序就叫解析器 (parser) 或语法分析器 (syntax analyzer) 。我们学习的重点就是如何实现自己的解析器,去解析我们的目标语言,像DSL语言、配置文件、自定义SQL等等。

1.2 元编程

手动编写解析器是非常繁琐的,所以我们有了ANTLR。只需编写ANTLR的语法文件,描述我们要解析的语言的语法,之后ANTLR就会自动生成能解析这种语言的解析器。也就是说,ANTLR是一种能写出程序的程序。在学习LISP或Ruby的宏时,我们经常能接触到元编程的概念。而用来声明我们语言的ANTLR语言的语法,就是元语言 (meta-language) 。

1.3 解析过程

为了简单起见,我们将解析分为两个阶段,对应我们的大脑读取文字时的过程。当我们读到一个句子时,在第一阶段,大脑会下意识地将字符组成单词,然后像查词典一样识别出它们的意思。在第二阶段,大脑会根据已识别的单词去识别句子的结构。第一阶段的过程叫词法分析 (lexical analysis) ,对应的分析程序叫做lexer,负责将符号 (token) 分组成符号类 (token class or token type) 。而第二阶段就是真正的parser,默认ANTLR会构建出一棵分析树 (parse tree) 或叫语法树 (syntax tree) 。如下图,就是简单的赋值表达式的解析过程:

语法树的叶子是输入token,而上级结点时包含其孩子结点的词组名 (phase) ,线性的句子其实是语法树的序列化。最终生成语法树的好处是:

  1. 树形结构易于遍历和处理,并且易被程序员理解,方便了应用代码做进一步处理。

  2. 多种解释或翻译的应用代码都可以重用一个解析器。但ANTLR也支持像传统解析器生成器那样,将应用处理代码嵌入到语法中。

  3. 对于因为计算依赖而需要多趟处理的翻译器来说,语法树非常有用！我们不用多次调用解析器去解析,只需高效地遍历语法树多次。