2.1 ANTLR元语言⌗

  • 解释器interpreter：执行语句，比如Python解释器。
  • 编译器compiler：将源语言转换成目标语言，比如Java编译器。

解析分为两步

  • 词法分析 lexical analysis, tokenizing，使用词法分析器 lexer
  • 语法分析 parsing，使用语法分析器 parser
stat: assign
    | ifstat
    | whilestat
    ;

2.2解析器的实现⌗

ANTLR生成recursive-descent parsers递归下降解析器，下降表示从解析树的树根开始解析，直到树叶。第一个调用的规则是start symbol开始符号。比如stat()。recursive-descent parsers递归下降解析器是top-down parser自顶向下解析器的一种。

void assign(){
    match(ID);
    match("=");
    expr();
    match(';');
}

可选语句的解析，类似于switch逻辑，需要用到lookahead token，有时还需要向前看多个token，ANTLR会自动处理：

stat: assign
    | ifstat
    | whilestat
    ;

void stat() {
    switch ( «current input token» ) {
    CASE ID : assign(); break;
    CASE IF : ifstat(); break; // IF is token type for keyword 'if'
    CASE WHILE : whilestat(); break;
    ...
    default : «raise no viable alternative exception» } 
}

2.3 有歧义的语法⌗

重复的规则：

stat: ID '=' expr ';'
    | ID '=' expr ';'
    ;
expr: INT ;

没有重复，但是有歧义的语法：

stat: expr ';'
    | ID '()' ')' ';'
    ;
expr: ID '(' ')'
    | INT
    ;

ANTLR解析有歧义的语法时采用第一个可行的选择。

词法分析和语法分析都可能发生歧义，比如：

BEGIN: 'begin';
ID: [a-z]+;

词法分析器会选择最长的字符串进行匹配，如果输入是beginner，会比配为ID，而不是BEGIN和ner。

有些平常的歧义可以通过优先级解决，5.4节会讲到：

1+2*3

C语言有另一种歧义，比如：

i*j

其中i可能是typedef定义的某个类型，也可能是某个变量ID，需要语义分析解决，第11章会讲到。

2.4 使用解析树构建语言应用⌗

从字符流到解析树需要用到的Java类：CharStream 、Lexer、Token、 Parser、 ParseTree。lexer和parser连起来称为TokenStream。

解析树中，叶子节点指向token stream中的token，token记录了CharStream中的开始截止位置，空格可以跳过不处理，不生成token。

解析树相关的类：RuleNode、TerminalNode

class RuleNode
+ getChild()
+ getParent()

RuleNode只是基类，用于派生其他类，ANTLR为每一个rule都生成一个子类，比如StatContext、AssignContext、ExprContext等等。称为context（上下文）对象，每一个上下文对象记录了识别出的短语中的开始和结束token，以及访问短语中所有元素的方法。比如AssignContext提供了ID()和expr()方法。

TerminalNode是token的容器。

2.5 解析树Listeners和Visitors⌗

ANTLR提供了两种遍历树的机制。默认的是Listener接口，对内置的tree walker触发的事件做出相应，类似于XML解析器的SAX处理机制，通过回调函数接收事件信号，类似于startDocument()和endDocument()。

ANTLR运行时提供ParseTreeWalker对解析树进行深度优先遍历。ANTLR生成ParseTreeListener子类，对每一个语法规则都有enter和exit方法，比如assign规则有enterAssign()和exitAssign()。

Visitor接口可以实现自定义的遍历规则。

术语⌗

  • Language：语言
  • Grammar：语法
  • Syntax tree or parse tree：语法树或解析树
  • Token：词法单元
  • Lexer or tokenizer：词法分析器
  • Parser：语法分析器
  • Recursive-descent parser：递归下降语法分析器
  • Lookahead：向前看单元