ANTLR笔记2 - 简单语法说明

ANTLR的语法文件使用扩展巴科斯范式EBNF描述，记得编译原理的用起来非常简单，需要进一步了解的是怎么构造自己的recognizer和translator。很多的语法不需要从头写，一方面很多语言标准中基本都使用EBNF描述，另一方面ANTLR网站http://www.antlr.org/grammar/list上有大量写好的语法文件，可以参考使用。
我已经忘得一干二净，从头大致了解一下。

巴科斯范式扩展符号 EBNF
() : 产生式组合
?  : 产生式出现0或1次
*  : 0或多次
+  : 1或多次
.   : 任意一个字符
~  : 不出现后面的字符
..  : 字符范围
可以参考http://www.cl.cam.ac.uk/~mgk25/iso-ebnf.html

例子1，整数定义:
integer : (HEX_PREFIX | OCTAL_PREFIX)? DIGITS; //可以有一个16进制或8进制前缀，没有则为10进制定义
HEX_PREFIX: '0x'; //16进制前缀
OCTAL_PREFIX: '0o'; //8进制前缀
DIGITS: '1'..'9' '0'..'9'*; //第一个字符必须为1-9，后面可以是任意多个0-9字符

例子2，多行注释符号/*和*/的定义:
ML_COMMENT : '/*' ( options {greedy=false;} : . )* '*/' ;
/*开头，*/结束，(.)*表示中间可以有任意多个字符，options {greedy=false;}是一个谓词选项，告诉分析器不要采用贪婪模式，即匹配到随后出现的第一个*/就结束，而不是试图去匹配输入字符流中的最后一个*/。

左递归、右递归 left/right recursion
如果一个产生式在最左开始位置包含它自己，叫左递归，例如exp: A | exp ',' A。而exp: A ',' exp | A则是右递归。用实际例子来看。
1. 右递归
例如实现一个表达式: +8结果为9；++8结果为10；+++8结果为11，以此类推。右递归语法为:
expr: PLUS expr | INT;
INT: '1'..'9' '0'..'9'*;
PLUS: '+';
用ANTLR笔记1中C#示例的方法来运行这个例子的语法文件内容如下:

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->left returns [int value] : e=expr { $value = $e.value; };
expr returns [int value] :
    PLUS e=expr { $value=$e.value+1; }
    | INT { $value=int.Parse( $INT.text ); };
INT: '1'..'9' '0'..'9'*;
PLUS: '+';

有个理解上容易产生歧义的地方，即expr应当解析成expr: (PLUS expr) | INT;还是expr: PLUS (expr | INT);？应当是前面这种方式。
2. 左递归
例如实现表达式: 8+结果为9；8++结果为10；8+++结果为11，以此类推。左递归语法为:
expr: expr | INT PLUS;
INT: '1'..'9' '0'..'9'*;
PLUS: '+';
ANTLR不支持左递归，上面的语法在生成时会报错: error(210):  The following sets of rules are mutually left-recursive [expr]。
将这个语法改为下面这样，就不是左递归了。
expr: INT PLUS*;
INT: '1'..'9' '0'..'9'*;
PLUS: '+';

零散的概念
语法多义性: 语法设计最值得关注的问题。第一点是人的思维对语法描述理解的歧义，与语法解释器的实际结果不一致，例如上面提到的expr的问题。另外就是语法描述本身逻辑上存在多义性，即对同样的输入可以解释成多种结果，它们都符合语法描述的规则。

lexer: 词法分析器，从输入字符流解析出词汇序列(tokens)。
parser: 语法解析器，对词汇进行语法分析，生成语法树(抽象语法树AST)。
EBNF的语法不区分词法分析和语法分析，对应的只有终结符、非终结符，终结符描述输入，非终结符描述输入所表达的树结构。ANTLR使用词法分析器识别终结符，使用语法分析器分析非终结符(生成的分析器代码文件有两个，一个是词法分析器***Lexer，一个是语法分析器***Parser)，并要求词法规则全部以大写开始，语法规则全部以小写开始。对每一个语法规则，最终都必须以词法规则结束，否则是一个无效语法，生成时会报错。

ANTLR生成的分析器代码中，语法规则都会有一个同名的方法，而词法规则的名称则跟语法文件给出的不一样。如果需要使用这些词法规则，可取的方法之一是定义一个语法规则与之对应；另外就是定义一个符号表，例如ANTLR笔记1中示例1里面的tokens{...}。定义符号表的优点是会优先匹配符号表，例如一些关键字等，可以避免他们被其它规则匹配上。
关于规则的定义顺序，语法文件中先出现的规则具有优先匹配的作用。

ANTLR笔记1中示例1的简单说明
1. grammar SimpleCalc;，定义语法名称。语法文件(.g文件)名称必须与这里指定的名称一致。默认情况生成的语法分析器类名为"语法名称"+Parser，词法分析器类名为"语法名称"+Lexer。
2. options {...}，定义全局配置参数，设置ANTLR生成过程中的一些控制选项，示例中指定目标语言为C#。
3. tokens {...}，定义全局的符号表。
4. @members {...}，这里面给出的代码将放入到生成的语法分析器类中，作为分析器类的成员属性、方法等。
   示例中为分析器添加了一个Main方法，省得再格外写一个测试类。
   Main方法先从命令行读取输入字符，将输入字符传给生成的词法分析器SimpleCalcLexer，得到词汇序列CommonTokenStream。接下来使用生成的语法分析器SimpleCalcParser对词汇序列进行分析，在生成语法树的过程中直接由expr()方法返回计算结果。
5. 语法规则。
   把语法规则中的{...}、[...]等相关ANTLR的Action去掉就是EBNF。
   ANTLR生成的语法解析器代码中，对应每个语法规则都会生成一个方法，这个方法完成对应语法规则的分析逻辑。{...}、[...]等就是我们自己的recognizer、translator需要的一些额外控制(Action)，分析匹配的逻辑由ANTLR完成，我们添加的这些控制就是对匹配到的结果怎样进行处理，是生成一个语法树，再由其它程序对语法树进行翻译，还是直接结合ANTLR的分析过程进行翻译转换或计算处理等，由我们进行控制。示例中是直接进行计算求值。
   returns [...]告诉ANTLR生成的方法需要返回什么内容，[int value]表示返回值类型为int，名字叫做value，就是声明了一个变量，用它来返回。在方法体里面，我们通过{...}中的内容进行求值运算，并把结果设置给value。{...}我们可以看作是一个宏，或者是一个模板，在里面我们可以使用ANTLR在代码生成时内置的一些变量/对象，它们以$开始(象StringTemplate语法，但不需要对应的$进行闭合)，这些变量在代码生成过程中ANTLR为我们设置好。其它的代码保持不变，放入到方法的相应位置上。
6. 词法规则。
   { $channel = HIDDEN; }。默认情况下ANTLR在词法分析器和语法分析器之间使用两个通道通讯，一个default和一个hidden。语法分析器监听default通道接收词汇序列，所以如果将某个词汇发送到hidden通道，这个词汇就会被语法分析器忽略掉。示例中将回车换行等空白字符都过滤掉，不进行语法分析。
   fragment: 对词法规则有效(我没有看到对语法规则有作用)，它在生成的语法树上不会有对应的节点，即可以这样理解，它是我们在语法中定义的一个宏，可以被其它语法规则调用，但它不会成为最终语法树上的节点。