ANTLR——语法

Note:这里记录的仅仅是我在阅读ANTLR-v3的PDF文档时摘录的一点资料，比起源文档来讲少了很多内容，并且可能存在着某些用词不准的地方，强烈建议有需求的人们去读他的原文。此外，本文针对的是ANTLR3的文档，不是V2，两者差别较大。

1. ANTLR的语法的一般规则

   一个计算机语言由一系列的句子(Sentences)组成。句子（Sentence）由一串的词汇（Vocabulary）和标点（Sybols）组成，而不是一串随机的字符。句子可以分解为短语（Phrase），Phrase可以分解为SubPhrase。计算机不能直接识别输入的这些句子和短语，它需要一些规则来对短语进行判断和识别，这些规则组成了该语言的语法。

   对于ANTLR来讲，它本身支持四种语法，分别为：Lexer、Parser、Tree以及Lexer和Parser的联合。

   这四种语法的基本结构是相同的，如下：

/** This is a document comment */
grammarType grammar name;    // GrammarType Must be the one of the types we talked above;   name is the Name of this grammar, which should indicating its role.

<<optionsSpec>>                // Specifics about Options.

<<tokensSpec>>                // Specifics about Tokens.

<<attributeScopes>>          // Specifics about Tokens.

<<actions>>                     // Actions

/** doc comment */
rule1 : ... | ... | ... ;
rule2 : ... | ... | ... ;
...

   上述的这个基本结构的次序（指语法类型、选项等等）不能颠倒。在这些基本细节之后，紧跟着的是规则（Rules），同一条规则之间可以用"|"来表示“或”，每条规则均以分号结尾。

   下面是一个简单的例子：

grammar T;
options {
    language=Java;    // Set target language
}
@members {
    String s;
}
r : ID {s = $ID.text; System.out.println("found "+s);} ;
ID: ('a'..'z'|'A'..'Z') + ;
WS: (' ' |'\n' |'\r' )+ {skip();} ; // ignore whitespace


   它声明了名为T的语法，用于将满足该语法条件的text进行打印，并忽略空格和换行符。

   该语法将目标语言设置成为了Java，这样，ANTLR会针对lexer, parser, 和tree这几种类型分别生成TLexer.java, TParser.java,和 T.java这几个文件。而对于第四种Lexer和Tree的联合，ANTLR除了生成TLexer.java和T.java以外，还会生成一个中间物（或者称为一个临时文件）——T__.g，其中包含了从这种“联合语法”中得到的词法细节。除了这些针对不同类型而生成的文件外，ANTLR对每种类型都会生成一个附加的词汇文件，本例中名为T.tokens，其中记录了可以供其他类型的语法来使用的符号。

   使用下面的命令来将该语法（T）转换成为Java代码：

java org.cntlr.Tool T.g

  我们需要一个主程序来展示该语法如何解析从标准输入中传入的数据，主程序名为Test.java，内容如下：

import org.antlr.runtime_code_page.*;
public class Test {
    public static void main(String[] args) throws Exception {
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        TLexer lexer = new TLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        TParser parser = new TParser(tokens);
        parser.r();
    }
}

   其中有几个ANTLR提供的类，ANTLRInputStream与CommonTokenStream分别用于向Lexer和Parser中提供字符（characters）和符号（Tokens）。当主程序调用了由语法规则生成的方法时，解析开始了。习惯上这些语法规则的一条一般命名为Start，而且一般来讲这条规则会被最先调用，当然，我们也可以直接调用我们想要的那条规则。例如在Test.java这个程序中，我们便使用parser.r()来直接调用了标号为r的那条规则。

   程序需要编译才能执行，编译的命令为：

javac Test.java TLexer.java TParser.java

   执行的时候有一点需要注意，该程序运行后需要从Stdin中接收输入，输入必须以End-Of-File来结尾。Linux/Unix中的EOF为Ctrl+D，而Windows中为Ctrl+Z。下面为用Test来测试这个语法的结果：

C:\WINDOWS\system32\cmd.exe /c java Test
ABC
^Z
found ABC

C :\WINDOWS\system32\cmd.exe /c java Test
ABC
^Z
found ABC

C :\WINDOWS\system32\cmd.exe /c java Test
asdf123
^Z
line 1:4 no viable alternative at character '1'
line 1:5 no viable alternative at character '2'
line 1:6 no viable alternative at character '3'
found asdf


   其中的前两侧测试中的输入合乎语法规则，执行成功；而第三次中输入中包含了非法字符（数字），执行失败。

2. 语法辞典

  ANTLR基本采用了C语言的语法风格，对于一些C中没有的派生用法，他提供的名称浅显易懂。

2.1 注释

   ANTLR中支持三种注释：单行、多行和Javadoc-style。下面的代码给出了三种风格的注释：

/** This grammar is an example illustrating he three kinds of comments. 
 * This is the javadoc-style.
 */ 
 grammar T;

/* This is a multi-line 
  comment.
*/

decl : ID ; // This is a single-line comment.

2.2 标识符

   ANTLR里，lexer和Token的名字须以大写字母开头；而非lexer的规则的名字则以小写开头。除了第一个字母外，标识符的其余字母则大小写均可，但是却只能使用ASCII字符。下面为几个例子。

ID, LPAREN, RIGHT_CURLY // token names/rules
expr, simpleDeclarator, d2, header_file // rule names

2.3 文字（Literals）

同多数的语言一样，ANTLR对字符（charactors）和文字（Literals）不加以区分。Literals以单引号包装，且不包含正则表达式。

2.4 动作（Actions）

动作是指用目标语言写成的代码块，可以应用在一个语法文件的多个地方，并且使用的方法是一样的──一段用花括号包括起来的任意代码。但是，这些代码必须用目标语言（在option中定义的语言）来写。

2.5 模板（Templates）

最大的模板就是ANTLR提供的StringTempate，到目前为止还没有看到专门的这个方面的介绍，这里也就暂时略过吧！

3、规则（Rules）

语法规则合起来定义了一个语言的所有语句；而单条的语法规则描述了符合语法的句子片段（或称为短语）。每个规则都有其他的等价规则。而且，就像C语言中一个函数可以调用其他函数一样，规则也可以引用其他的规则。如果一条规则直接地或者间接地的调用了它本身，那么该规则被称为递归规则。
lexer、paser和tree parser的规则的语法（syntax）基本相同，但是tree parser中规则可能会使用树状结构元素。
除了短语的语法结构以外，ANTLR的规则还有很多的其他部分，用于细化选项（Options）、属性（Attributes）、异常处理（Exception Handling）、树构造和模板构造等等。其通用结构如下：

/** comment */
access-modifier rule-name[<>] returns [<>]
    <>
    <>
    <>
    <>
    : <> -> <>
    | <> -> <>
    ..<
    | <> -> <>
    ;
    <>

前面提到，一个规则可以引用其他的规则，这个引用是通过标签（Label）来实现的，标签的设置很简单，形如：x=T，例如：
classDef
    : c='class' name=ID '{' m=members '}'
    ;
对他们的引用可以通过在其标号前面加上$来实现，例如：$c会返回class的Token等等。

如同其他语言的函数一样，ANTLR的规则也可以有参数和返回值。但不同的是，一般的函数在传递参数的时候使用圆括号，而ANTLR的规则则使用方括号；此外，函数一般只有一个返回值，如果需要函数对多个变量值进行修改则需要使用地址指针，而ANTLR则可以直接返回多个返回值，下面是一个简单的例子：

r[int a, String b] returns [int c, String d]
    :    ... {$c=$a; $d=$b;}
    ;

前面提到过，用目标语言写成的Actions可以被嵌入到规则中。但是值得注意的是，当Action位于规则的位置前后不同的时候，需要对Action加上不同的标记：@init和@after。例如：
r returns [int n]
@init {
    $n=0; // init return value
}

@after {
    System.out.println("return value n="+$n);
}
    :    ... {$n=23;}
    |    ... {$n=9;}
    |    ... {$n=1;}
    |    //use initialized value of n;
    ;

语法预测问题。ANTLR规则支持语法预测。语法预测一定程度上解决了某些情况下从左因式分解带来的问题。语法预测与一般的规则差别不大，但是语法预测有了一个特殊的标记“=>”，例如下面的例子：
stat:    (decl)=>decl ';'
    |    expr ';'
这里的第一条规则使用了语法预测，如果右端有decl元素，则将其赋值给decl；否则，执行第二条。（更多的内容在后文，这里有个概念即可。）

ANTLR支持异常处理，其异常处理与Java和C++类似，通过throw(), try(), catch()来实现。

ANTLR支持面向Token的多个通道，并可定制ANTLR对这些通道中的Token的处理方式。例如，将空格、制表符等等符号隐藏就利用了这种通道技术，下面的代码隐藏了空格、制表符以及换行符：
WS    :    (' '|'\t'|'\r'|'\n')+ {$channal=HIDDEN;};
上面的例子中，词法分析器将空格等等也进行了分析，只是其结果被隐藏了。但是出于效能的考虑，很多时候我们希望这些字符在词法分析的时候可以不处理而直接忽略掉，这可以通过下面的语句来实现(向其中嵌入Action)：
WS    :    (' '|'\t'|'\r'|'\n')+ {skip()};
这里有两点值得注意：一是我们发可以在词法分析中通过getCharPositionInLine()函数来获取任意字符在该句中的位置；另外一个是在对字符进行处理中，一个制表符是被当作一个字符来处理的。

4. 记号（Token Specification）

关键词token可以用来引入新的记号或者给已有的记号一个新的名字。其语法：
tokens {
    token-name1;
    token-name2 = 'string-literal';
}

上面的例子给出了两种使用方法。

其中第一种用于生成一个虚拟记号，它并不与任何已有的记号或者输入流相关联。虚拟记号常常用来被当作一个子树的根节点，从而演化成为该子树表达的操作数的操作符。例如我们定义VARDEF为声明int i的一个typedef，那么，其表达的子树为：^(VARDEF int i)。那么其在语法解析中可以表示为：
grammar T;
tokens {
    VARDEF;
}
var    :    type ID ';' ->V(vardef type ID);

前面提到的两种用法的后一种用来给已有的一个符号生成一个别名。例如将取余符号“%”起名为MOD，可用下式标识：
grammar T;
tokens {
    MOD='%';
}
expr :    INT (MOD INT)* ;

5. 全局属性范围
ANTLR支持用户定义全局属性，这些全局属性可以被其作用范围的所有规则以及嵌入规则的Action了解和读取。scope的定义语法为：
scope name {
    type1 attribute-name1;
    type2 attribute-name2;
}

例如，下面定义了一个用于处理SymbolList的全局scope:
scope SybolScope {
    List sybols;
}
其他的规则可以通过下面的形式来使用上面的这个csope:
classDefinition
scope SymbolScope;

关于属性和scope的更多内容可参考文档的第六章。

6. 语法中的动作

前面已经提到，ANTLR支持在语法的规则中嵌入动作（Action），但是Action必须以目标语言写成。ANTLR提供动作的命名规则以确定动作的执行时间。动作的语法规则如下：

@action-name { ... }
@action-scope-name::action-name { ... }