PDF《ANTLR 4简明教程》

8 基本概念 一门语言由有效的句子组成,一个句子由短语组成,一个短语由子短语和词汇符号组成.要 实现一门语言,我们必须构建一个应用,它能读取句子以及对发现的短语和输入符号作出适 当的反应. 这样的应用必须能识别特定语言的所有有效的句子、短语和子短语.识别一个短语意味着我 们能确定短语的各种组件并能指出它与其它短语的区别.例如,我们把输入 nu = 123;

识别 为赋值语句,这意味着我们知道nu是赋值目标以及123是要存储的值.识别赋值语句 nu = 123;

也意味着应用认为它是明显不同于,比如说, a + b 语句的. 识别语言的程序被称为语法分析器.语法指代控制语言成员的规则,每条规则都表示一个短 语的结构,文法就是一组规则.为了更容易地实现识别语言的程序,通常我们会把语法分析 过程拆解成两个相似但不同的任务或阶段. 把字符组成单词或符号(记号)的过程被称为词法分析或简单标记化.我们把标记输入的程 序称为词法分析器.词法分析器能把相关的记号组成记号类型,例如INT(整数)、ID(标志 符)、FLOAT(浮点数)等.当语法分析器只关心类型的时候,词法分析器会把词汇符号组 成类型,而不是单独的符号.记号至少包含两部分信息:记号类型(确定词法结构)和匹配 记号的文本. 第二阶段是真正的语法分析器,它使用这些记号去识别句子结构,在这里是赋值语句.默认 情况下,ANTLR生成的语法分析器会构建一个称为语法分析树或语法树的数据结构,它记录 语法分析器如何识别输入句子的结构以及它的组件短语.下图说明了语言识别器的基本的数 据流: 语法分析树的内部节点是分组和确认它们子节点的短语名字.根节点是最抽象的短语名字, 在本例中是prog( program 的缩写).语法分析树的叶子节点永远是输入记号. 通过生成语法分析树,语法分析器给应用的其余部分提供了方便的数据结构,它们含有关于 语法分析器如何把符号组成短语的完整信息.树是非常容易处理的,并且也能被程序员很好 的理解.更好的是,语法分析器能自动地生成语法分析树. 基本概念

9 通过操作语法分析树,需要识别相同语言的多个应用能重用同一个语法分析器.当然,你也 可以选择直接在语法中嵌入特定应用的代码片段,这是语法分析器生成器传统的做法. ANTLR v4仍然允许这样做,但是语法分析树有助于更简洁更解耦的设计. 语法分析树对于需要多次树遍历的转换也是非常有用的,因为在计算依赖关系的阶段通常会 需要前一个阶段的信息.相比于在每个阶段都要准备输入字符,我们只需要遍历语法分析树 多次,更具有效率. 因为我们用一套规则指定短语,语法分析树子树根节点对应于语法规则名.这里的语法规则 对应于上图中assign子树的第一层: assign : ID '

='

expr 匹配赋值语句像 a=5 明白ANTLR如何把这些规则转换为人类可读的语法分析代码是使用和调试语法的基础,因此 让我们深入地挖掘语法分析是如何工作的. 实现语法分析器 ANTLR工具根据语法规则,例如我们刚才看到的assign,生成递归下降语法分析器.递归下 降语法分析器只是递归方法的一个集合,每个规则一个方法.下降这个术语指的是分析从语 法分析树的根开始向着叶子进行(记号).我们首先调用的规则,即prog符号,成为语法分 析树的根.那也就意味着对前面部分的语法分析树来说需要调用方法prog().这类分析更通用 的术语是自顶向下分析:递归下降语法分析器仅仅是自顶向下语法分析器实现的一种. 要了解递归下降语法分析器是什么样子,这里是ANTLR为规则assign生成的方法(稍微整 理): // assign : ID '