程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> 一個簡單的語言的語法（二）：ANTLR的重寫規則

一個簡單的語言的語法（二）：ANTLR的重寫規則

編輯：關於JAVA

上一篇我們使用ANTLR來描述了Jerry語言的基本語法，並通過ANTLRWorks來實驗該語法對樣本代碼生成的解析樹。但如同上一篇最後所述，這樣得到的解析樹中有太多對後續處理來說無用的冗余信息。我們需要消除這些冗余信息，得到抽象語法樹（AST）。

本篇將以之前做的語法為基礎，通過添加樹重寫規則來將ANTLR默認生成的解析樹簡化整理為抽象語法樹。

本文涉及的源碼和運行時庫打包在附件裡了，懶得復制粘貼的話就直接下載附件的版本，用 ANTLRWorks來查看和編輯語法文件吧～

修改後的語法文件如下：

Jerry.g（ANTLR 3.1語法文件，以Java為生成目標語言）

Java代碼

1.grammar Jerry; 2. 3.options { 4. language = Java; 5. output = AST; 6. ASTLabelType = CommonTree; 7.} 8. 9.tokens { 10. // imaginary tokens 11. 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 rules 23. 24.program : statementList EOF! 25. { 26. System.out.println( 27. null == $statementList.tree ? 28. "null" : 29. $statementList.tree.toStringTree()); 30. } 31. ; 32. 33.statementList 34. : statement* 35. ; 36. 37.statement 38. : expressionStatement 39. | variableDeclaration 40. | blockStatement 41. | ifStatement 42. | whileStatement 43. | breakStatement 44. | readStatement 45. | writeStatement 46. ; 47. 48.expressionStatement 49. : expression SEMICOLON 50. -> ^( EXPR_STMT expression ) 51. ; 52. 53.variableDeclaration 54. : typeSpecifier 55. ( Identifier 56. ( -> ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) Identifier ) 57. | ( LBRACK Integer RBRACK )+ 58. - > ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier Integer+ ) Identifier ) 59. | EQ expression 60. -> ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) Identifier expression ) 61. | ( LBRACK Integer RBRACK )+ EQ arrayLiteral 62. -> ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier Integer+ ) Identifier arrayLiteral ) 63. ) 64. ) 65. ( COMMA id=Identifier 66. ( -> $variableDeclaration ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) $id ) 67. | ( LBRACK dim1+=Integer RBRACK )+ 68. -> $variableDeclaration ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier $dim1+ ) $id ) 69. | EQ exp=expression 70. -> $variableDeclaration ^( VAR_DECL ^( SIMPLE_TYPE typeSpecifier ) $id $exp ) 71. | ( LBRACK dim2+=Integer RBRACK )+ EQ al=arrayLiteral 72. -> $variableDeclaration ^( VAR_DECL ^( ARRAY_TYPE typeSpecifier $dim2+ ) $id $al ) 73. ) 74. { if (null != $dim1) $dim1.clear(); if (null != $dim2) $dim2.clear(); } 75. )* 76. SEMICOLON 77. ; 78. 79.typeSpecifier 80. : INT | REAL 81. ; 82. 83.arrayLiteral 84. : LBRACE 85. arrayLiteralElement ( COMMA arrayLiteralElement )* 86. RBRACE 87. -> ^( ARRAY_LITERAL arrayLiteralElement+ ) 88. ; 89. 90.arrayLiteralElement 91. : expression 92. | arrayLiteral 93. ; 94. 95.blockStatement 96. : LBRACE statementList RBRACE 97. -> ^( BLOCK statementList ) 98. ; 99. 100.ifStatement 101. : IF^ LPAREN! expression RPAREN! statement ( ELSE! statement )? 102. ; 103. 104.whileStatement 105. : WHILE^ LPAREN! expression RPAREN! statement 106. ; 107. 108.breakStatement 109. : BREAK SEMICOLON! 110. ; 111. 112.readStatement 113. : READ^ variableAccess SEMICOLON! 114. ; 115. 116.writeStatement 117. : WRITE^ expression SEMICOLON! 118. ; 119. 120.variableAccess 121. : Identifier 122. ( -> ^( SIMPLE_VAR_ACCESS Identifier ) 123. | ( LBRACK Integer RBRACK ) + 124. -> ^( ARRAY_VAR_ACCESS Identifier Integer+ ) 125. ) 126. ; 127. 128.expression 129. : assignmentExpression 130. | logicalOrExpression 131. ; 132. 133.assignmentExpression 134. : variableAccess EQ^ expression 135. ; 136. 137.logicalOrExpression 138. : logicalAndExpression ( OROR^ logicalAndExpression )* 139. ; 140. 141.logicalAndExpression 142. : relationalExpression ( ANDAND^ relationalExpression )* 143. ; 144. 145.relationalExpression 146. : additiveExpression ( relationalOperator^ additiveExpression )? 147. | BANG^ relationalExpression 148. ; 149. 150.additiveExpression 151. : multiplicativeExpression ( additiveOperator^ multiplicativeExpression )* 152. ; 153. 154.multiplicativeExpression 155. : primaryExpression ( multiplicativeOperator^ primaryExpression )* 156. ; 157. 158.primaryExpression 159. : variableAccess 160. | Integer 161. | RealNumber 162. | LPAREN! expression RPAREN! 163. | MINUS primaryExpression 164. -> ^( UNARY_MINUS primaryExpression ) 165. ; 166. 167.relationalOperator 168. : LT | GT | EQEQ | LE | GE | NE 169. ; 170. 171.additiveOperator 172. : PLUS | MINUS 173. ; 174. 175.multiplicativeOperator 176. : MUL | DIV 177. ; 178. 179.// lexer rules 180. 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.SEMICOLON 203. : ';' 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 : '<=' 228. ; 229. 230.GT : '>' 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.Identifier 273. : LetterOrUnderscore ( LetterOrUnderscore | Digit )* 274. ; 275. 276.Integer : Digit+ 277. ; 278. 279.RealNumber 280. : Digit+ '.' Digit+ 281. ; 282. 283.fragment 284.Digit : '0'..'9' 285. ; 286. 287.fragment 288.LetterOrUnderscore 289. : Letter | '_' 290. ; 291. 292.fragment 293.Letter : ( 'a'..'z' | 'A'..'Z' ) 294. ; 295. 296.WS : ( ' ' | '\t' | '\r' | '\n' )+ { $channel = HIDDEN; } 297. ; 298. 299.Comment 300. : '/*' ( options { greedy = false; } : . )* '*/' { $channel = HIDDEN; } 301. ; 302. 303.LineComment 304. : '//' ~ ('\n'|'\r')* '\r'? '\n' { $channel = HIDDEN; } 305. ;

稍微說明一下修改點。應該觀察到lexer rules部分是完全沒有改變的，修改的主要是一些選項和 parser rules。

首先，在文件的開頭添加了一組選項：

Java代碼

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語句。原本的語法是：

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 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語法文件生成的解析器，我們可以解析這個例子，得到對應的抽象語法樹的字符串表示。表示方法是：

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在這裡的應用。

關於JAVA