乐者为王

Do one thing, and do it well.

ANTLR 4权威参考读书笔记(8)

  • sentence 句子

一门语言由有效的句子组成,一个句子由短语组成,一个短语由子短语和词汇符号组成。要实现一门语言,我们必须构建一个能读取句子以及对发现的短语和输入符号作出适当反应的应用。

这样的应用必须能够识别特定语言的所有有效的句子、短语和子短语。识别一个短语意味着我们能够确定短语的各种组件并能指出它与其它短语的区别。例如,我们把输入sp=100识别为赋值语句,这就意味着我们知道sp是赋值目标以及100是要存储的值。识别赋值语句sp=100也意味着应用认为它是明显不同于,比如说,a+b语句的。在识别后,应用将执行适当的操作,例如performAssignment("sp", 100)或者translateAssignment("sp", 100)。

识别语言的程序被称为语法分析器。语法指代控制语言成员的规则,每条规则都表示一个短语的结构。为了更容易地实现识别语言的程序,通常我们会把识别语言的语法分析拆解成两个相似但不同的任务或阶段。

把字符组成单词或符号(记号)的过程被称为词法分析或简单标记化。我们把标记输入的程序称为词法分析器。词法分析器能把相关的记号组成记号类型,例如INT(整数)、ID(标志符)、FLOAT(浮点数)等。当语法分析器只关心类型的时候,词法分析器会把词汇符号组成类型,而不是单独的符号。记号至少包含两块信息:记号类型(确定词法结构)和匹配记号的文本。

第二阶段是真正的语法分析器,它使用这些记号去识别句子结构,在本例中是赋值语句。默认情况下,ANTLR生成的语法分析器会构建一个称为语法分析树或语法树的数据结构,它记录语法分析器如何识别输入句子的结构和它的组件短语。下图阐明了语言识别器的基本数据流:

basic-data-flow

语法分析树的内部节点是分组和确认它们子节点的短语名字。根节点是最抽象的短语名字,在本例中是stat(“statement”的缩写)。语法分析树的叶子节点永远是输入记号。

通过生成语法分析树,语法分析器给应用的其余部分提供了方便的数据结构,它们含有关于语法分析器如何把符号组成短语的完整信息。树是非常容易处理的,并且也能被程序员很好的理解。更好的是,语法分析器能自动地生成语法分析树。

通过操作语法分析树,需要识别相同语言的多个应用能复用同一个语法分析器。当然,你也可以选择直接在语法中嵌入特定应用的代码片段,这是语法分析器生成器传统的做法。ANTLR v4仍然允许这样做,但是语法分析树有助于更简洁更解耦的设计。

语法分析树对于需要多次树遍历的转换也是非常有用的,因为在计算依赖关系的阶段通常会需要前一个阶段的信息。相比于在每个阶段都要准备输入字符,我们只需要遍历语法分析树多次,更具有效率。

我们使用一套规则指定短语:语法分析树子树根节点对应于语法规则名。这里的语法规则对应于上图中assign子树的第一层:

1
assign : ID '=' expr ;    // 匹配赋值语句像"sp = 100"

明白ANTLR如何把这些规则转换为人类可读的语法分析代码是使用和调试语法的基础,可以让我们更深入地挖掘语法分析是如何工作的。

Comments