上一篇我们使用ANTLR来描述了Jerry语言的基本语法，并通过ANTLRWorks来实验该语法对样本代码生 成的解析树。但如同上一篇最后所述，这样得到的解析树中有太多对后续处理来说无用的冗余信息。我们 需要消除这些冗余信息，得到抽象语法树（AST）。
本篇将以之前做的语法为基础，通过添加树重写规则来将ANTLR默认生成的解析树简化整理为抽象语法 树。
本文涉及的源码和运行时库打包在附件里了，懒得复制粘贴的话就直接下载附件的版本，用 ANTLRWorks来查看和编辑语法文件吧～
修改后的语法文件如下：
Jerry.g（ANTLR 3.1语法文件，以Java为生成目标语言）
Java代码
1.grammar Jerry;2.3.options {4. language = Java;5. utput = AST;6. ASTLabelType = CommonTree;7.}8.9.tokens {10. // imaginary tokens11. VAR_DECL;12. SIMPLE_TYPE;13. ARRAY_TYPE;14. ARRAY_LITERAL;15. SIMPLE_VAR_Access;16. ARRAY_VAR_Access;17. UNARY_MINUS;18. BLOCK;19. EXPR_STMT;20.}21.22.// parser rules23.24.program : statementList EOF!25. {26. System.out.println(27. null == $statementList.tree ?28. "null" :29. $statementList.tree.toStringTree());30. }31. ;32.33.statementList34. : statement*35. ;36.37.statement38. : expressionStatement39. | variableDeclaration40. | blockStatement41. | ifStatement42. | whileStatement43. | breakStatement44. | readStatement45. | writeStatement46. ;47.48.expressionStatement49. : expression SEMICOLON50. -> ^( EXPR_STMT expression )51. ;52.53.variableDeclaration54. : typeSpecifier55. ( Identifier56. ( -> ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) Identifier )57. | ( LBRACK Integer RBRACK )+58. - > ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier Integer+ ) Identifier )59. | EQ expression60. -> ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) Identifier expression )61. | ( LBRACK Integer RBRACK )+ EQ arrayLiteral62. -> ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier Integer+ ) Identifier arrayLiteral )63. )64. )65. ( COMMA id=Identifier66. ( -> $variableDeclaration ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) $id )67. | ( LBRACK dim1+=Integer RBRACK )+68. -> $variableDeclaration ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier $dim1+ ) $id )69. | EQ exp=expression70. -> $variableDeclaration ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) $id $exp )71. | ( LBRACK dim2+=Integer RBRACK )+ EQ al=arrayLiteral72. -> $variableDeclaration ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier $dim2+ ) $id $al ) 73. )74. { if (null != $dim1) $dim1.clear(); if (null != $dim2) $dim2.clear(); }75. )*76. SEMICOLON77. ;78.79.typeSpecifier80. : INT | REAL81. ;82.83.arrayLiteral84. : LBRACE85. arrayLiteralElement ( COMMA arrayLiteralElement )*86. RBRACE87. -> ^( ARRAY_LITERAL arrayLiteralElement+ )88. ;89.90.arrayLiteralElement91. : expression92. | arrayLiteral93. ;94.95.blockStatement96. : LBRACE statementList RBRACE97. -> ^( BLOCK statementList )98. ;99.100.ifStatement101. : IF^ LPAREN! expression RPAREN! statement ( ELSE! statement )?102. ;103.104.whileStatement105. : WHILE^ LPAREN! expression RPAREN! statement106. ;107.108.breakStatement109. : BREAK SEMICOLON!110. ;111.112.readStatement113. : READ^ variableAccess SEMICOLON!114. ;115.116.writeStatement117. : WRITE^ expression SEMICOLON!118. ;119.120.variableAccess121. : Identifier122. ( -> ^( SIMPLE_VAR_Access Identifier )123. | ( LBRACK Integer RBRACK ) +124. -> ^( ARRAY_VAR_Access Identifier Integer+ )125. ) 126. ;127.128.expression129. : assignmentExpression130. | logicalOrExpression131. ;132.133.assignmentExpression134. : variableAccess EQ^ expression135. ;136.137.logicalOrExpression138. : logicalAndExpression ( OROR^ logicalAndExpression )*139. ;140.141.logicalAndExpression142. : relationalExpression ( ANDAND^ relationalExpression )*143. ;144.145.relationalExpression146. : additiveExpression ( relationalOperaTor^ additiveExpression )?147. | BANG^ relationalExpression148. ;149.150.additiveExpression151. : multiplicativeExpression ( additiveOperaTor^ multiplicativeExpression )*152. ;153.154.multiplicativeExpression155. : primaryExpression ( multiplicativeOperaTor^ primaryExpression )*156. ;157.158.primaryExpression159. : variableAccess160. | Integer161. | RealNumber162. | LPAREN! expression RPAREN!163. | MINUS primaryExpression164. -> ^( UNARY_MINUS primaryExpression )165. ;166.167.relationalOperaTor168. : LT | GT | EQEQ | LE | GE | NE169. ;170.171.additiveOperaTor172. : PLUS | MINUS173. ;174.175.multiplicativeOperaTor176. : MUL | DIV177. ;178.179.// lexer rules180.181.LPAREN : '('182. ;183.184.RPAREN : ')'185. ;186.187.LBRACK : '['188. ;189.190.RBRACK : ']'191. ;192.193.LBRACE : '{'194. ;195.196.RBRACE : '}'197. ;198.199.COMMA : ','200. ;201.202.SEMICOLON203. : ';'204. ;205.206.PLUS : '+'207. ;208.209.MINUS : '-'210. ;211.212.MUL : '*'213. ;214.215.DIV : '/'216. ;217.218.EQEQ : '=='219. ;220.221.NE : '!='222. ;223.224.LT : '<'225. ;226.227.LE : ''231. ;232.233.GE : '>='234. ;235.236.BANG : '!'237. ;238.239.ANDAND : '&&'240. ;241.242.OROR : '||'243. ;244.245.EQ : '='246. ;247.248.IF : 'if'249. ;250.251.ELSE : 'else'252. ;253.254.WHILE : 'while'255. ;256.257.BREAK : 'break'258. ;259.260.READ : 'read'261. ;262.263.WRITE : 'write'264. ;265.266.INT : 'int'267. ;268.269.REAL : 'real'270. ;271.272.Identifier273. : LetterOrUnderscore ( LetterOrUnderscore | Digit )*274. ;275.276.Integer : Digit+277. ;278.279.RealNumber280. : Digit+ '.' Digit+281. ;282.283.fragment284.Digit : '0'..'9'285. ;286.287.fragment288.LetterOrUnderscore289. : Letter | '_'290. ;291.292.fragment293.Letter : ( 'a'..'z' | 'A'..'Z' )294. ;295.296.WS : ( ' ' | '/t' | '/r' | '/n' )+ { $channel = HIDDEN; }297. ;298.299.Comment300. : '/*' ( options { greedy = false; } : . )* '*/' { $channel = HIDDEN; }301. ;302.303.LineComment304. : '//' ~ ('/n'|'/r')* '/r'? '/n' { $channel = HIDDEN; }305. ;
稍微说明一下修改点。应该观察到lexer rules部分是完全没有改变的，修改的主要是一些选项和 parser rules。
首先，在文件的开头添加了一组选项：
Java代码
options {language = Java;utput = AST;ASTLabelType = CommonTree;}
ANTLR会知道应该使用生成AST的模式，以CommonTree作为AST的节点类型，并以Java作为生成的解析器 源码的语言。上一篇是在ANTLRWorks里编辑和实验语法的，这次我们需要生成实际能运行的解析器，所以 需要指定这些选项（默认就是生成Java源码，不过后续文章中我应该会换用CSharp2目标。这个以后再说 ）。
接下来，可以看到除了原本在lexer rules里定义的实际存在的token类型之外，这次我们在语法文件 的开头还增加了一组虚拟的token类型。这些token类型是为了让生成出来的抽象语法树易于解析而添加的 。
例如，观察VAR_DECL这个token类型。在原本的语法中，没有任何关键字能清楚的标识出当前处理的内 容是一个变量声明。为了方便后续分析，我们可以“制造”出一个虚构的token作为一个变量声明语句的 根元素，然后以变量的类型、标识符和初始值为子元素。
然后就是最重要的部分，树重写规则了。有两种形式来表述树重写规则：一是直接在原本的语法规则 上添加树生成用的运算符（^和!），二是在原本的语法规则后添加一个箭头（”->”），并在箭头后显 式指定需要生成的节点的结构。
看两个例子：
while语句。原本的语法是：
Java代码
whileStatement : 'while' '(' expression ')' statement ;
这里我们想让生成出来的子树以’while’为根节点，以expression和statement为子节点。
可以直接在该语法上添加树生成运算符：在某个元素后加上帽子符号（’^’）来表示它是生成的子树的 根节点，在某个元素后加上叹号（’!’）来表示生成的子树中应该忽略该元素。于是修改得到的语法是：
Java代码
whileStatement : 'while'^ '('! expression ')'! statement ;
也可以显式指定树重写规则。一棵子树用这种方式来表示：
Java代码
^( root element1 element2 ... )
这里我们要的就是：
Java代码
whileStatement : 'while' '(' expression ')' statement -> ^( 'while' expression statement ) ;
这种形式我们能一目了然看到最终生成的子树的结构。
两种形式是等价的，可以根据具体情况来选择能简单而清晰的表示出树改写规则的版本。
对表达式相关的语法规则，我们几乎都是用添加运算符的形式来表示树改写规则，因为对左结合的双 目运算符，这样是最简洁的。
ANTLR生成的解析器使用LL(*)算法；与一般的LL解析器一样，ANTLR不支持左递归的语法规则。这使得 书写左结合的双目运算符时，一般得写成这样的形式：
Java代码
exprWithHigherPrecedence : exprWithLowerPrecedence ( op exprWithLowerPrecedence )* ;
而不能以左递归来指定左结合。（但右结合还是可以用右递归来指定的。）
那么在表示树改写规则的时候，使用运算符来修饰语法就是这样：
Java代码
exprWithHigherPrecedence : exprWithLowerPrecedence ( op^ exprWithLowerPrecedence )* ;
只是在op的后面添加了一个帽子符号（’^’），表明在没有匹配到op运算符时就直接返回 exprWithLowerPrecedence规则所生成的树；而如果匹配到了op运算符，则每匹配到一次就生成一个新的 以op为根节点的、前后两个较低优先级的表达式节点为子节点的树。
这个树改写规则如果要显式指定，就得写成：
Java代码
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
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例子：
C代码
// line comment// declare variables with/without initializersint 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语法文件生成的解析器，我们可以解析这个例子，得到对应的抽象语法树的字符串表示 。表示方法是：
Java代码
(root element1 element2 ...)
跟LISP的S-expression非常类似。
于是执行测试程序。将要解析的代码保存到JerrySample.txt中，然后执行下面的命令：
引用
java -cp ".;antlrworks-1.2.2.jar" TestJerry < JerrySample.txt
得到输出：
Java代码
(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)))
这样太乱了看不清楚。将其格式稍微整理一下得到：
Java代码
(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在这里的应 用。
来说是非者，便是是非人。
