乐者为王

Do one thing, and do it well.

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

  • predication 断定
  • predict 预判
  • lookahead 预读

ANTLR工具根据语法规则,例如我们刚才看到的assign,生成递归下降语法分析器。递归下降语法分析器只是递归方法的一个集合,每个规则一个方法。下降这个术语指的是分析从语法分析树的根开始向着叶子进行(记号)。我们首先调用的规则,即stat符号,成为语法分析树的根。那也就意味着对ANTLR 4权威参考读书笔记(8)中的语法分析树来说需要调用方法stat()。这类分析更通用的术语是自顶向下分析:递归下降语法分析器仅仅是自顶向下语法分析器实现的一种。

要了解递归下降语法分析器是什么样子,可以看看下面ANTLR为规则assign生成的方法(稍微做过整理):

1
2
3
4
5
6
// assign : ID '=' expr ;
void assign() {    // 根据规则assign生成的方法
    match(ID);     // 比较ID和当前输入符号然后消费
    match('=');
    expr();        // 通过调用expr()匹配表达式
}

递归下降语法分析器最酷的部分是通过跟踪调用方法stat()、assign()和expr()绘制出的调用关系图反映了内部的语法分析树节点。match()的调用对应语法分析树叶子。为了在一个手工构建的语法分析器中手动构建一颗语法分析树,我们需要在每个规则方法的开始处插入“添加新子树根”操作,以及给match()一个“添加新叶子节点”操作。

方法assign()只是检查确保所有必要的记号存在且以正确的顺序。当语法分析器进入assign()时,它不必在多个选项之间进行选择。选项是规则定义右边的选择之一。例如,调用assign的stat规则可能有其它类型的语句。

1
2
3
4
5
6
7
/** 匹配起始于当前输入位置的任何语句 */
stat
    : assign    // 第一个选项('|'是选项分隔符)
    | ifstat    // 第二个选项
    | whilestat
    ...
    ;

stat的分析规则看起来像一条switch语句:

1
2
3
4
5
6
7
8
9
void stat() {
    switch ( «current input token» ) {
        CASE ID : assign(); break;
        CASE IF : ifstat(); break;    // IF是关键字'if'的记号类型
        CASE WHILE : whilestat(); break;
        ...
        default : «raise no viable alternative exception»
    }
}

方法stat()必须通过检查下一个输入记号作出分析决定或断定。分析决定预判哪一个选项将会成功。在本例中,当看到WHILE关键字时会预判是规则stat的第三个选项。规则方法stat()然后就会调用whilestat()。你以前可能听说过术语预读记号,那只是下一个输入记号。预读记号可以是语法分析器在匹配和消费输入记号之前嗅探的任何记号。

有时候,语法分析器需要一些预读记号去预判哪个选项会成功。它甚至必须考虑从当前位置直到文件结尾的所有的记号。ANTLR默默地为你处理所有的这些事情,但是对决策过程有个基本的了解是有帮助的,可以让调试生成的语法分析器更容易。

为更好地理解分析决定,想象有一个单一入口和单一出口的迷宫,有单词写在地板上。每个沿着从入口到出口路径的单词序列表示一个句子。迷宫的结构与定义一门语言的语法规则类似。为测试一个句子在一门语言中的成员身份,我们在穿越迷宫时把句子的单词和沿着地板的单词作比较。如果通过句子的单词我们能到达出口,那么句子就是有效的。

为了通过迷宫,我们必须在每个岔口选择一条有效路径,正如我们必须在语法分析器中选择选项一样。通过把我们句子中下一个单词(们)和沿着来自每个岔口的每条路径上可见的单词比较,我们做出决定该走哪条路。我们能从岔口看到的单词与预读记号类似。当每条路径以唯一的单词开始时决定是相当容易的。在规则stat中,每个选项从唯一的记号开始,因此stat()可以通过查看第一个预读记号识别选项。

当单词从一个岔口重叠部分开始每条路径时,语法分析器需要继续往前看,扫描可以识别选项的单词。ANTLR可以根据需要为每个分析决定自动上下调节预读数量。如果预读的结果是多条同样的到出口的路径,那说明当前的输入短语有多种解释,这会导致二义性。

Comments