一个简单的语言的语法（二）：ANTLR的重写规则

系列链接：
一个简单的语言的语法（一）：用ANTLR描述语法
一个简单的语言的语法（二）：ANTLR的重写规则
一个简单的语言的语法（三）：做些小调整，并将生成目标换到CSharp2

上一篇我们使用ANTLR来描述了Jerry语言的基本语法，并通过ANTLRWorks来实验该语法对样本代码生成的解析树。但如同上一篇最后所述，这样得到的解析树中有太多对后续处理来说无用的冗余信息。我们需要消除这些冗余信息，得到抽象语法树（AST）。
本篇将以之前做的语法为基础，通过添加树重写规则来将ANTLR默认生成的解析树简化整理为抽象语法树。

本文涉及的源码和运行时库打包在附件里了，懒得复制粘贴的话就直接下载附件的版本，用ANTLRWorks来查看和编辑语法文件吧～

修改后的语法文件如下：
Jerry.g（ANTLR 3.1语法文件，以Java为生成目标语言）

grammar Jerry;

options {
	language = Java;
	output = AST;
	ASTLabelType = CommonTree;
}

tokens {
	// imaginary tokens
	VAR_DECL;
	SIMPLE_TYPE;
	ARRAY_TYPE;
	ARRAY_LITERAL;
	SIMPLE_VAR_ACCESS;
	ARRAY_VAR_ACCESS;
	UNARY_MINUS;
	BLOCK;
	EXPR_STMT;
}

// parser rules

program	:	statementList EOF!
		{
			System.out.println(
				null == $statementList.tree ?
				"null" :
				$statementList.tree.toStringTree());
		}
	;

statementList
	:	statement*
	;

statement
	:	expressionStatement
	|	variableDeclaration
	|	blockStatement
	|	ifStatement
	|	whileStatement
	|	breakStatement
	|	readStatement
	|	writeStatement
	;

expressionStatement
	:	expression SEMICOLON
			-> ^( EXPR_STMT expression )
	;

variableDeclaration
	:	typeSpecifier
			( Identifier
				(	-> ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) Identifier )
				| ( LBRACK Integer RBRACK )+
					-> ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier Integer+ ) Identifier )
				| EQ expression
					-> ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) Identifier expression )
				| ( LBRACK Integer RBRACK )+ EQ arrayLiteral
					-> ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier Integer+ ) Identifier arrayLiteral )
				)
			)
			( COMMA id=Identifier
				(	-> $variableDeclaration ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) $id )
				| ( LBRACK dim1+=Integer RBRACK )+
					-> $variableDeclaration ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier $dim1+ ) $id )
				| EQ exp=expression
					-> $variableDeclaration ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) $id $exp )
				| ( LBRACK dim2+=Integer RBRACK )+ EQ al=arrayLiteral
					-> $variableDeclaration ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier $dim2+ ) $id $al )
				)
				{ if (null != $dim1) $dim1.clear(); if (null != $dim2) $dim2.clear(); }
			)*
		SEMICOLON
	;

typeSpecifier
	:	INT | REAL
	;

arrayLiteral
	:	LBRACE
			arrayLiteralElement ( COMMA arrayLiteralElement )*
		RBRACE
			-> ^( ARRAY_LITERAL arrayLiteralElement+ )
	;

arrayLiteralElement
	:	expression
	|	arrayLiteral
	;

blockStatement
	:	LBRACE statementList RBRACE
			-> ^( BLOCK statementList )
	;

ifStatement
	:	IF^ LPAREN! expression RPAREN! statement ( ELSE! statement )?
	;

whileStatement
	:	WHILE^ LPAREN! expression RPAREN! statement
	;

breakStatement
	:	BREAK SEMICOLON!
	;

readStatement
	:	READ^ variableAccess SEMICOLON!
	;

writeStatement
	:	WRITE^ expression SEMICOLON!
	;

variableAccess
	:	Identifier
		(	-> ^( SIMPLE_VAR_ACCESS Identifier )
		| ( LBRACK Integer RBRACK )+
			-> ^( ARRAY_VAR_ACCESS Identifier Integer+ )
		)
	;

expression
	:	assignmentExpression
	|	logicalOrExpression
	;

assignmentExpression
	:	variableAccess EQ^ expression
	;

logicalOrExpression
	:	logicalAndExpression ( OROR^ logicalAndExpression )*
	;

logicalAndExpression
	:	relationalExpression ( ANDAND^ relationalExpression )*
	;

relationalExpression
	:	additiveExpression ( relationalOperator^ additiveExpression )?
	|	BANG^ relationalExpression
	;

additiveExpression
	:	multiplicativeExpression ( additiveOperator^ multiplicativeExpression )*
	;
  
multiplicativeExpression
	:	primaryExpression ( multiplicativeOperator^ primaryExpression )*
	;

primaryExpression
	:	variableAccess
	|	Integer
	|	RealNumber
	|	LPAREN! expression RPAREN!
	|	MINUS primaryExpression
			-> ^( UNARY_MINUS primaryExpression )
	;

relationalOperator   
	:	LT | GT | EQEQ | LE | GE | NE
	;

additiveOperator
	:	PLUS | MINUS
	;

multiplicativeOperator
	:	MUL | DIV
	;

// lexer rules

LPAREN	:	'('
	;

RPAREN	:	')'
	;

LBRACK	:	'['
	;

RBRACK	:	']'
	;

LBRACE	:	'{'
	;

RBRACE	:	'}'
	;

COMMA	:	','
	;

SEMICOLON
	:	';'
	;

PLUS	:	'+'
	;

MINUS	:	'-'
	;

MUL	:	'*'
	;

DIV	:	'/'
	;

EQEQ	:	'=='
	;

NE	:	'!='
	;

LT	:	'<'
	;

LE	:	'<='
	;

GT	:	'>'
	;

GE	:	'>='
	;

BANG	:	'!'
	;

ANDAND	:	'&&'
	;

OROR	:	'||'
	;

EQ	:	'='
	;

IF	:	'if'
	;

ELSE	:	'else'
	;

WHILE	:	'while'
	;

BREAK	:	'break'
	;

READ	:	'read'
	;

WRITE	:	'write'
	;

INT	:	'int'
	;

REAL	:	'real'
	;

Identifier
	:	LetterOrUnderscore ( LetterOrUnderscore | Digit )*
	;

Integer	:	Digit+
	;

RealNumber
	:	Digit+ '.' Digit+
	;

fragment
Digit	:	'0'..'9'
	;

fragment
LetterOrUnderscore
	:	Letter | '_'
	;

fragment
Letter	:	( 'a'..'z' | 'A'..'Z' )
	;

WS	:	( ' ' | '\t' | '\r' | '\n' )+ { $channel = HIDDEN; }   
	;

Comment
	:	'/*' ( options { greedy = false; } : . )* '*/' { $channel = HIDDEN; }
	;

LineComment
	:	'//' ~('\n'|'\r')* '\r'? '\n' { $channel = HIDDEN; }
	;

稍微说明一下修改点。应该观察到lexer rules部分是完全没有改变的，修改的主要是一些选项和parser rules。

首先，在文件的开头添加了一组选项：

options {
	language = Java;
	output = AST;
	ASTLabelType = CommonTree;
}

ANTLR会知道应该使用生成AST的模式，以CommonTree作为AST的节点类型，并以Java作为生成的解析器源码的语言。上一篇是在ANTLRWorks里编辑和实验语法的，这次我们需要生成实际能运行的解析器，所以需要指定这些选项（默认就是生成Java源码，不过后续文章中我应该会换用CSharp2目标。这个以后再说）。

接下来，可以看到除了原本在lexer rules里定义的实际存在的token类型之外，这次我们在语法文件的开头还增加了一组虚拟的token类型。这些token类型是为了让生成出来的抽象语法树易于解析而添加的。
例如，观察VAR_DECL这个token类型。在原本的语法中，没有任何关键字能清楚的标识出当前处理的内容是一个变量声明。为了方便后续分析，我们可以“制造”出一个虚构的token作为一个变量声明语句的根元素，然后以变量的类型、标识符和初始值为子元素。

然后就是最重要的部分，树重写规则了。有两种形式来表述树重写规则：一是直接在原本的语法规则上添加树生成用的运算符（^和!），二是在原本的语法规则后添加一个箭头（"->"），并在箭头后显式指定需要生成的节点的结构。
看两个例子：
while语句。原本的语法是：

whileStatement : 'while' '(' expression ')' statement ;

这里我们想让生成出来的子树以'while'为根节点，以expression和statement为子节点。
可以直接在该语法上添加树生成运算符：在某个元素后加上帽子符号（'^'）来表示它是生成的子树的根节点，在某个元素后加上叹号（'!'）来表示生成的子树中应该忽略该元素。于是修改得到的语法是：

whileStatement : 'while'^ '('! expression ')'! statement ;

也可以显式指定树重写规则。一棵子树用这种方式来表示：

^( root element1 element2 ... )

这里我们要的就是：

whileStatement : 'while' '(' expression ')' statement
    -> ^( 'while' expression statement )
  ;

这种形式我们能一目了然看到最终生成的子树的结构。
两种形式是等价的，可以根据具体情况来选择能简单而清晰的表示出树改写规则的版本。

对表达式相关的语法规则，我们几乎都是用添加运算符的形式来表示树改写规则，因为对左结合的双目运算符，这样是最简洁的。
ANTLR生成的解析器使用LL(*)算法；与一般的LL解析器一样，ANTLR不支持左递归的语法规则。这使得书写左结合的双目运算符时，一般得写成这样的形式：

exprWithHigherPrecedence
  : exprWithLowerPrecedence ( op exprWithLowerPrecedence )*
  ;

而不能以左递归来指定左结合。（但右结合还是可以用右递归来指定的。）
那么在表示树改写规则的时候，使用运算符来修饰语法就是这样：

exprWithHigherPrecedence
  : exprWithLowerPrecedence ( op^ exprWithLowerPrecedence )*
  ;

只是在op的后面添加了一个帽子符号（'^'），表明在没有匹配到op运算符时就直接返回exprWithLowerPrecedence规则所生成的树；而如果匹配到了op运算符，则每匹配到一次就生成一个新的以op为根节点的、前后两个较低优先级的表达式节点为子节点的树。
这个树改写规则如果要显式指定，就得写成：

exprWithHigherPrecedence
  : exprWithLowerPrecedence
      ( op exp=exprWithLowerPrecedence
          -> ^( op $exprWithHigherPrecedence $exp )
      )*
  ;

后者相比之下麻烦多了，所以一般都会使用前者。

可惜C风格的变量声明语句的语法很麻烦，结果variableDeclaration在修改后膨胀了好多 T T
最不爽的地方就是C风格的数组变量声明是把数组的维度写在变量名后面的。这就使得语句开头的类型（例如int、char等）可能只是变量的实际类型的一部分，而另一部分要在变量名的之前（例如表示指针的星号（'*'））或之后（例如表示数组的方括号（'[' ']'））。
就不能把整个类型写在一起么……T T 于是衍生出来的Java和C#明显都吸取了这个教训。

在语法的program规则中，我们添加了一条嵌入语法动作，让生成的解析器在匹配完program规则后将其对应的抽象语法树以字符串的形式输出出来。

如果是在ANTLRWorks里编辑该语法文件，可以在菜单里选择Generate -> Generate Code来生成出解析器的源码。这里例子中我们会得到JerryLexer.java和JerryParser.java。
要运行这个解析器，还需要写一个简单的启动程序来调用生成出来的JerryLexer和JerryParser。源码如下：
TestJerry.java

import org.antlr.runtime.*;

public class TestJerry {
    public static void main(String[] args) throws Exception {
        // Create an input character stream from standard in
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        // Create an JerryLexer that feeds from that stream
        JerryLexer lexer = new JerryLexer(input);
        // Create a stream of tokens fed by the lexer
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        // Create a parser that feeds off the token stream
        JerryParser parser = new JerryParser(tokens);
        // Begin parsing at rule prog
        parser.program();
    }
}

它指定从标准输入流得到要解析的Jerry代码，然后通过JerryLexer将代码解析成token流，再将token流交给JerryParser进行句法分析。

将JerryLexer.java、JerryParser.java和TestJerry.java放在跟ANTLRWorks同一目录下，然后编译它们：

引用

javac -Xlint:unchecked -cp antlrworks-1.2.2.jar JerryLexer.java JerryParser.java TestJerry.java

（因为ANTLRWorks里含有ANTLR的运行时库，而我正好又是用ANTLRWorks来编辑语法文件的，所以直接用ANTLRWorks的JAR包放在classpath里来得到需要的ANTLR运行时类。实际开发的话可以从ANTLR官网获得只含有ANTLR运行时库的JAR包并在编译和运行的时候将其添加到classpath里。）

上一篇的最后有这样的一段Jerry例子：

// line comment
// declare variables with/without initializers
int i = 1, j;
int x = i + 2 * 3 - 4 / ( 6 - - 7 );
int array[2][3] = {
  { 0, 1, 2 },
  { 3, 4, 6 }
};

/*
  block comment
*/

while (i < 10) i = i + 1;
while (!x > 0 && i < 10) {
  x = x - 1;
  if (i < 5) break;
  else read i;
}

write x - j;

（语法是符合要求的，至于代码的意义就别追究了，只是用来演示各种语法结构随便写的）

用本篇的ANTLR语法文件生成的解析器，我们可以解析这个例子，得到对应的抽象语法树的字符串表示。表示方法是：

(root element1 element2 ...)

跟LISP的S-expression非常类似。

于是执行测试程序。将要解析的代码保存到JerrySample.txt中，然后执行下面的命令：

引用

java -cp ".;antlrworks-1.2.2.jar" TestJerry < JerrySample.txt

得到输出：

(VAR_DECL (SIMPLE_TYPE int) i 1) (VAR_DECL (SIMPLE_TYPE int) j) (VAR_DECL (SIMPLE_TYPE int) x (- (+ (SIMPLE_VAR_ACCESS i) (* 2 3)) (/ 4 (- 6 (UNARY_MINUS 7))))) (VAR_DECL (ARRAY_TYPE int 2 3) array (ARRAY_LITERAL (ARRAY_LITERAL 0 1 2) (ARRAY_LITERAL 3 4 6))) (while (< (SIMPLE_VAR_ACCESS i) 10) (= (SIMPLE_VAR_ACCESS i) (+ (SIMPLE_VAR_ACCESS i) 1))) (while (&& (! (> (SIMPLE_VAR_ACCESS x) 0)) (< (SIMPLE_VAR_ACCESS i) 10)) (BLOCK (= (SIMPLE_VAR_ACCESS x) (- (SIMPLE_VAR_ACCESS x) 1)) (if (< (SIMPLE_VAR_ACCESS i) 5) break (read (SIMPLE_VAR_ACCESS i))))) (write (- (SIMPLE_VAR_ACCESS x) (SIMPLE_VAR_ACCESS j)))

这样太乱了看不清楚。将其格式稍微整理一下得到：

(VAR_DECL
  (SIMPLE_TYPE int)
  i
  1
)
(VAR_DECL
  (SIMPLE_TYPE int)
  j
)
(VAR_DECL
  (SIMPLE_TYPE int)
  x
  (-
    (+ (SIMPLE_VAR_ACCESS i) (* 2 3))
    (/ 4 (- 6 (UNARY_MINUS 7)))
  )
)
(VAR_DECL
  (ARRAY_TYPE
    int
    2
    3
  )
  array
  (ARRAY_LITERAL
    (ARRAY_LITERAL 0 1 2)
    (ARRAY_LITERAL 3 4 6)
  )
)

(while
  (< (SIMPLE_VAR_ACCESS i) 10)
  (= (SIMPLE_VAR_ACCESS i) (+ (SIMPLE_VAR_ACCESS i) 1))
)
(while
  (&&
    (! (> (SIMPLE_VAR_ACCESS x) 0))
    (< (SIMPLE_VAR_ACCESS i) 10)
  )
  (BLOCK
    (= (SIMPLE_VAR_ACCESS x) (- (SIMPLE_VAR_ACCESS x) 1))
    (if
      (< (SIMPLE_VAR_ACCESS i) 5)
      break
      (read (SIMPLE_VAR_ACCESS i))
    )
  )
)
(write
  (- (SIMPLE_VAR_ACCESS x) (SIMPLE_VAR_ACCESS j)))

可以跟原本的代码对比一下，看看是否保持了原本的结构。

得到这棵抽象语法树之后，接下来就可以对树来做匹配和分析了。由于树本身已经有了结构，下面就可以用更干净的描述方式来表述我们要对树做的处理。下一篇就来看看ANTLR的tree grammar在这里的应用。