为了后面的tree grammar更简洁，本篇对上一篇的树重写规则和一些语法细节做了些调整。并且，将 生成的lexer和parser的源码目标换到了CSharp2，以便后面能使用一些.NET的库。
要使用CSharp2的目标，需要从官网下载相应的运行时库。当前的最新版是3.1.1，可以从这里获取。 CSharp/CSharp2目标的详细情况，可以查阅官网上的文档。以上一篇的语法为基础，要换到CSharp2目标 只要把几个嵌入动作里的System.out.println换成Console.WriteLine，把toStringTree换成 ToStringTree，把clear换成Clear就可以了。编译的时候至少需要引用Antlr3.Runtime.dll。
那么除去更换生成目标带来的影响，这次做了些怎样的修改呢？
首先，语法做了些细微的调整。例如说，program规则从原本允许没有语句到现在要求至少有一条语句 ；blockStatement为空block写了条专门的分支；expressionStatement也添加了一个EXPR_STMT的虚构 token为根节点，等等。
变化最大的还是variableDeclaration及相关规则。上一篇里这条规则的重写规则并不区分有初始化与 无初始化、简单类型与数组类型的区别；本篇里则将这两个区别都明确的写在了重写规则里，以不同的虚 构token来作为生成的树的根节点。这样，到写后面的tree grammar的时候，需要的lookahead数就可以减 少。
ANTLR所生成的AST，以深度优先的方式遍历，可以看做一个一维的流：每一层父子关系都可以表示为 ：
root -> “down” -> element1 -> element2 -> … -> elementN -> “up” -> …
其中”down”和”up”是ANTLR插入的虚构token，用于指定树的层次。
这样，后面使用tree grammar来遍历AST时，实际上遍历的就是这样一个一维的流 （CommonTreeNodeStream）。所以我们也可以把tree grammar看做是隐含了”down”和”up”虚构token的普 通parser grammar。那么，tree grammar中需要的lookahead个数的分析，也就跟parser grammar的一样 。
看看下面的例子。对于上一篇variableDeclaration的重写规则中出现的变量声明的类型，可以用这样 的tree grammar来匹配：
Java代码
type : ^( SIMPLE_TYPE INT ) | ^( SIMPLE_TYPE REAL ) | ^( ARRAY_TYPE INT Integer+ ) | ^( ARRAY_TYPE REAL Integer+ ) ;
树语法的^( … )就隐含了”down”和”up”这两个虚构token。实际上这条规则匹配的是：
可以很清楚的看到”down”和”up”在规则中的位置。
在进入这条规则之后，需要多少个lookahead才足以判断应该选择哪条分支呢？
向前看一位：只能排除掉两个分支，还有两个，不够；
向前看两位：第二位是什么呢？四个分支里第二位都是”down”节点，对判断分支没帮助，还是不够用 ；
向前看三位：SIMPLE和ARRAY、INT和REAL都能分开了，足够。
那么对这条规则而言，需要2个lookahead。阅读ANTLR生成的源码，可以看到input.LA(3)这样的调用 ，表示向前看第三位的token。每多一个lookahead，生成的代码就得多以层嵌套的if-else，很是麻烦。
如果能调整一下parser这边生成的AST的结构，让tree grammar那边能写成：
Java代码
simpleType : INT | REAL ;arrayType : ^( INT Integer+ ) | ^( REAL Integer+ ) ;
那么这两条规则都只需要1个lookahead就足以判断分支了，比原本的写法要简单，也会稍微快一些。 写了个Ruby脚本来检查生成的源码里用的lookahead的个数（*）：
Ruby代码
1.def check_lookaheads(file)2. lookaheads = open file, 'r' do |f|3. ret = []4. f.readlines.grep(/^/s+(.+/.la/((/d+)/).+)$/i) do5. ret << "#{$2}: #{$1}"6. end7. ret8. end9.end10.11.if __FILE__ == $012. la = check_lookaheads ARGV[0] || 'JerryParser.cs'13. puts 'Lookaheads:', la, ''14. puts "Non-LL(1)'s:", la.select { |l| ?1 != l[0] } 15.end
明白了这个道理，就应该尽量将重写规则中的各个根节点设计成能直接区分的。
实际上不只是树的语法，在编程语言的源码的语法设计上也是一样：最容易解析的语法是每条规则都 以特殊的token开头的语法，例如说声明变量就以var关键字开头，声明函数就以function关键字开头等。 这样能保证语法只需要1个lookahead。而类似C的语法对解析器来说实在算不上友善……|||
（*：ANTLR在遇到比较复杂的判断条件时不会直接在规则对应的方法里调用input.LA(n)，而是会生成 一个DFA类来计算应该走的分支。上面的Ruby脚本不检查这个状况。）
其次，所有虚构token都添加了一些信息在后面。例如说原本一元负号的规则是：
Java代码
MINUS primaryExpression -> ^( UNARY_MINUS primaryExpression )
则UNARY_MINUS这个虚构token将不包含任何文字、位置信息。因为MINUS原本携带的位置信息已经丢失 了，所以如果后续处理中需要知道这个表达式的位置就没办法得到。
改写为这样：
Java代码
MINUS primaryExpression -> ^( UNARY_MINUS[$MINUS] primaryExpression )
则使得UNARY_MINUS继承MINUS匹配时的文字、位置等属性，解决了前面的问题。
除此之外，原本写在program规则里的嵌入动作也去掉了。之前写在那里主要是为了在parser内输出 AST的字符串表示，只是演示用。
修改后的完整语法如下：
C#代码
1.grammar Jerry;2.3.options {4. language = CSharp2;5. utput = AST;6. ASTLabelType = CommonTree;7.}8.9.tokens {10. // imaginary tokens11. SIMPLE_VAR_DECL;12. SIMPLE_VAR_DECL_INIT;13. ARRAY_VAR_DECL;14. ARRAY_VAR_DECL_INIT;15. ARRAY_LITERAL;16. SIMPLE_VAR_Access;17. ARRAY_VAR_Access;18. UNARY_MINUS;19. BLOCK;20. EMPTY_BLOCK;21. EXPR_STMT;22.}23.24.// parser rules25.26.program : statement+ EOF!27. ;28.29.statement30. : expressionStatement31. | variableDeclaration32. | blockStatement33. | ifStatement34. | whileStatement35. | breakStatement36. | readStatement37. | writeStatement38. ;39.40.expressionStatement41. : expression SEMICOLON42. - > ^( EXPR_STMT[$expression.start, "ExprStmt"] expression )43. ;44.45.variableDeclaration46. : typeSpecifier47. ( id1=Identifier48. ( ( -> ^( SIMPLE_VAR_DECL[$id1, "VarDecl"] ^( typeSpecifier ) $id1 ) )49. | ( EQ expression50. -> ^( SIMPLE_VAR_DECL_INIT[$id1, "VarDeclInit"] ^( typeSpecifier ) $id1 expression ) )51. | ( ( LBRACK Integer RBRACK )+52. -> ^( ARRAY_VAR_DECL[$id1, "VarDecl"] ^( typeSpecifier Integer+ ) $id1 ) ) 53. | ( ( LBRACK Integer RBRACK )+ EQ arrayLiteral54. -> ^( ARRAY_VAR_DECL_INIT[$id1, "VarDeclInit"] ^( typeSpecifier Integer+ ) $id1 arrayLiteral ) )55. )56. )57. ( COMMA id2=Identifier58. ( ( -> $variableDeclaration ^( SIMPLE_VAR_DECL[$id2, "VarDecl"] ^( typeSpecifier) $id2 ) )59. | ( EQ exp=expression60. -> $variableDeclaration ^( SIMPLE_VAR_DECL_INIT [$id2, "VarDeclInit"] ^( typeSpecifier ) $id2 $exp ) )61. | ( ( LBRACK dim1+=Integer RBRACK )+62. -> $variableDeclaration ^( ARRAY_VAR_DECL[$id2, "VarDecl"] ^( typeSpecifier $dim1+ ) $id2 ) )63. | ( ( LBRACK dim2+=Integer RBRACK )+ EQ al=arrayLiteral64. - > $variableDeclaration ^( ARRAY_VAR_DECL_INIT[$id2, "VarDeclInit"] ^( typeSpecifier $dim2+ ) $id2 $al ) )65. )66. { if (null != $dim1) $dim1.Clear(); if (null != $dim2) $dim2.Clear(); }67. )*68. SEMICOLON69. ;70.71.typeSpecifier72. : INT | REAL73. ;74.75.arrayLiteral76. : LBRACE77. arrayLiteralElement ( COMMA arrayLiteralElement )*78. RBRACE79. -> ^( ARRAY_LITERAL [$LBRACE, "Array"] arrayLiteralElement+ )80. ;81.82.arrayLiteralElement83. : expression84. | arrayLiteral85. ;86.87.blockStatement88. : LBRACE statement+ RBRACE89. -> ^( BLOCK[$LBRACE, "Block"] statement+ )90. | LBRACE RBRACE // empty block91. -> EMPTY_BLOCK[$LBRACE, "EmptyBlock"]92. ;93.94.ifStatement95. : IF^ LPAREN! expression RPAREN! statement ( ELSE! statement )?96. ;97.98.whileStatement99. : WHILE^ LPAREN! expression RPAREN! statement100. ;101.102.breakStatement103. : BREAK SEMICOLON!104. ;105.106.readStatement107. : READ^ variableAccess SEMICOLON!108. ;109.110.writeStatement111. : WRITE^ expression SEMICOLON!112. ;113.114.variableAccess115. : Identifier116. ( -> ^( SIMPLE_VAR_Access[$Identifier, "VarAccess"] Identifier )117. | ( LBRACK Integer RBRACK )+118. -> ^( ARRAY_VAR_Access[$Identifier, "VarAccess"] Identifier Integer+ )119. )120. ;121.122.expression123. : assignmentExpression124. | logicalOrExpression125. ;126.127.assignmentExpression128. : variableAccess EQ^ expression129. ;130.131.logicalOrExpression132. : logicalAndExpression ( OROR^ logicalAndExpression )*133. ;134.135.logicalAndExpression136. : relationalExpression ( ANDAND^ relationalExpression )*137. ;138.139.relationalExpression140. : additiveExpression ( relationalOperaTor^ additiveExpression )?141. | BANG^ relationalExpression142. ;143.144.additiveExpression145. : multiplicativeExpression ( additiveOperaTor^ multiplicativeExpression )*146. ;147.148.multiplicativeExpression149. : primaryExpression ( multiplicativeOperaTor^ primaryExpression )*150. ;151.152.primaryExpression153. : variableAccess154. | Integer155. | RealNumber156. | LPAREN! expression RPAREN!157. | MINUS primaryExpression158. -> ^( UNARY_MINUS[$MINUS] primaryExpression ) 159. ;160.161.relationalOperaTor162. : LT | GT | EQEQ | LE | GE | NE163. ;164.165.additiveOperaTor166. : PLUS | MINUS167. ;168.169.multiplicativeOperaTor170. : MUL | DIV171. ;172.173.// lexer rules174.175.LPAREN : '('176. ;177.178.RPAREN : ')'179. ;180.181.LBRACK : '['182. ;183.184.RBRACK : ']'185. ;186.187.LBRACE : '{'188. ;189.190.RBRACE : '}'191. ;192.193.COMMA : ','194. ;195.196.SEMICOLON197. : ';'198. ;199.200.PLUS : '+'201. ;202.203.MINUS : '-'204. ;205.206.MUL : '*'207. ;208.209.DIV : '/'210. ;211.212.EQEQ : '=='213. ;214.215.NE : '!='216. ;217.218.LT : '<'219. ;220.221.LE : ''225. ;226.227.GE : '>='228. ;229.230.BANG : '!'231. ;232.233.ANDAND : '&&'234. ;235.236.OROR : '||'237. ;238.239.EQ : '='240. ;241.242.IF : 'if'243. ;244.245.ELSE : 'else'246. ;247.248.WHILE : 'while'249. ;250.251.BREAK : 'break'252. ;253.254.READ : 'read'255. ;256.257.WRITE : 'write'258. ;259.260.INT : 'int'261. ;262.263.REAL : 'real'264. ;265.266.Identifier267. : LetterOrUnderscore ( LetterOrUnderscore | Digit )*268. ;269.270.Integer : Digit+271. ;272.273.RealNumber274. : Digit+ '.' Digit+275. ;276.277.fragment278.Digit : '0'..'9'279. ;280.281.fragment282.LetterOrUnderscore283. : Letter | '_'284. ;285.286.fragment287.Letter : ( 'a'..'z' | 'A'..'Z' )288. ;289.290.WS : ( ' ' | '/t' | '/r' | '/n' )+ { $channel = HIDDEN; }291. ;292.293.Comment294. : '/*' ( options { greedy = false; } : . )* '*/' { $channel = HIDDEN; }295. ;296.297.LineComment298. : '//' ~ ('/n'|'/r')* '/r'? '/n' { $channel = HIDDEN; }299. ;
同上一篇一样，也写一个启动lexer和parser的程序。这次是用C#来写：
C#代码
using System;using System.IO;using Antlr.Runtime; // Antlr3.Runtime.dllusing Antlr.Runtime.Tree;using Antlr.Utility.Tree; // Antlr3.Utility.dllsealed class TestJerryAst { static void PrintUsage( ) { Console.WriteLine( "Usage: TestJerryAst [-dot] <source file>" ); } static void Main( string[] args ) { bool generateDot = false; string srcFile; switch ( args.Length ) { case 0: PrintUsage( ); return; case 1: if ( !File.Exists( args[ 0 ] ) ) goto case 0; srcFile = args[ 0 ]; break; default: if ( "-dot" == args[ 0 ] ) { generateDot = true; if ( !File.Exists( args[ 1 ] ) ) goto case 0; srcFile = args[ 1 ]; } else { goto case 1; } break; } var input = new ANTLRReaderStream( File.OpenText( srcFile ) ); var lexer = new JerryLexer( input ); var tokens = new CommonTokenStream( lexer ); var parser = new JerryParser( tokens ); var programReturn = parser.program(); var ast = ( CommonTree ) programReturn.Tree; // Generate DOT diagram if -dot option is given if ( generateDot ) { var dotgen = new DOTTreeGeneraTor( ); var astDot = dotgen.ToDOT( ast ); Console.WriteLine( astDot ); } else { Console.WriteLine( ast.ToStringTree( ) ); } }}
因为使用了DOTTreeGeneraTor，编译时记得在引用Antlr3.Runtime.dll之外，还需要引用 Antlr3.Utility.dll与StringTemplate.dll。
继续使用前两篇用过的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;
通过上面的程序，可以得到这样的AST：
上面的程序生成的是.dot文件（输出到标准输出流上）。使用Graphviz的dot，将这个文件以
Java代码
dot JerrySample.dot -Tpng -o JerrySample.png
这样的命令来转换，就能得到PNG图像。
本篇就到这里。下一篇看看遍历AST用的基本tree grammar。
既有美妙的风景，也会有称不上景、只有风的地方。
