在JavaEye的博客頻道逛，看到NeuronR的blog上有關於他的編譯器實踐的帖子，覺得有點意思，於是 平行的用別的方法來做那個編譯器。那邊要求是用C來實現，我這邊就用些方便些的語言來實現吧。
本篇將通過ANTLR 3.1描述Jerry語言，並在ANTLRWorks裡實驗，通過生成的解析器來得到Jerry程序代 碼對應的解析樹。
關注過解析器生成器的話，ANTLR應該不會是個陌生的名字才對。Anyway簡短說幾句。ANTLR在生成解 析器方面正得到越來越多的應用，幾個實例，XRuby項目用了，Jython現在正在使用，SapphireSteel的 Ruby和ActionScript IDE也用ANTLR來生成編譯器前端。
ANTLR，ANother Tool for Language Recognition，是由Terence Parr教授開發的語言工具，用於協 助生成解析器、編譯器、解釋器等與語言處理相關的程序。它由PCCTS發展而來，特征是可以生成采用LL (*)算法的遞歸下降式的解析器。它所使用的語法表述格式類似於常見的EBNF（extended Backus–Naur form），易於理解和維護。
讀了編譯器構造實踐[任務布置]之後，大概琢磨著語法應該是像這樣的吧：
Jerry.g：（ANTLR 3.1語法）
Java代碼
1.grammar Jerry;
2.
3.program : statementList EOF
4. ;
5.
6.statementList
7. : statement*
8. ;
9.
10.statement
11. : expressionStatement
12. | variableDeclaration
13. | blockStatement
14. | ifStatement
15. | whileStatement
16. | breakStatement
17. | readStatement
18. | writeStatement
19. ;
20.
21.expressionStatement
22. : expression SEMICOLON
23. ;
24.
25.variableDeclaration
26. : typeSpecifier Identifier ( LBRACK Integer RBRACK )* initializer?
27. ( COMMA Identifier ( LBRACK Integer RBRACK )* initializer? )*
28. SEMICOLON
29. ;
30.
31.typeSpecifier
32. : INT | REAL
33. ;
34.
35.initializer
36. : EQ ( expression | arrayLiteral )
37. ;
38.
39.arrayLiteral
40. : LBRACE
41. ( expression | arrayLiteral ) ( COMMA ( expression | arrayLiteral ) )*
42. RBRACE
43. ;
44.
45.blockStatement
46. : LBRACE statementList RBRACE
47. ;
48.
49.ifStatement
50. : IF LPAREN expression RPAREN statement ( ELSE statement )?
51. ;
52.
53.whileStatement
54. : WHILE LPAREN expression RPAREN statement
55. ;
56.
57.breakStatement
58. : BREAK SEMICOLON
59. ;
60.
61.readStatement
62. : READ variableAccess SEMICOLON
63. ;
64.
65.writeStatement
66. : WRITE expression SEMICOLON
67. ;
68.
69.variableAccess
70. : Identifier ( LBRACK Integer RBRACK )*
71. ;
72.
73.expression
74. : assignmentExpression
75. | logicalOrExpression
76. ;
77.
78.assignmentExpression
79. : variableAccess EQ expression
80. ;
81.
82.logicalOrExpression
83. : logicalAndExpression ( OROR logicalAndExpression )*
84. ;
85.
86.logicalAndExpression
87. : relationalExpression ( ANDAND relationalExpression )*
88. ;
89.
90.relationalExpression
91. : additiveExpression ( relationalOperator additiveExpression )?
92. | BANG relationalExpression
93. ;
94.
95.additiveExpression
96. : multiplicativeExpression ( additiveOperator multiplicativeExpression )*
97. ;
98.
99.multiplicativeExpression
100. : primaryExpression ( multiplicativeOperator primaryExpression )*
101. ;
102.
103.primaryExpression
104. : variableAccess
105. | Integer
106. | RealNumber
107. | LPAREN expression RPAREN
108. | SUB primaryExpression
109. ;
110.
111.relationalOperator
112. : LT | GT | EQEQ | LE | GE | NE
113. ;
114.
115.additiveOperator
116. : ADD | SUB
117. ;
118.
119.multiplicativeOperator
120. : MUL | DIV
121. ;
122.
123.// lexer rules
124.
125.LPAREN : '('
126. ;
127.
128.RPAREN : ')'
129. ;
130.
131.LBRACK : '['
132. ;
133.
134.RBRACK : ']'
135. ;
136.
137.LBRACE : '{'
138. ;
139.
140.RBRACE : '}'
141. ;
142.
143.COMMA : ','
144. ;
145.
146.SEMICOLON
147. : ';'
148. ;
149.
150.ADD : '+'
151. ;
152.
153.SUB : '-'
154. ;
155.
156.MUL : '*'
157. ;
158.
159.DIV : '/'
160. ;
161.
162.EQEQ : '=='
163. ;
164.
165.NE : '!='
166. ;
167.
168.LT : '<'
169. ;
170.
171.LE : '<='
172. ;
173.
174.GT : '>'
175. ;
176.
177.GE : '>='
178. ;
179.
180.BANG : '!'
181. ;
182.
183.ANDAND : '&&'
184. ;
185.
186.OROR : '||'
187. ;
188.
189.EQ : '='
190. ;
191.
192.IF : 'if'
193. ;
194.
195.ELSE : 'else'
196. ;
197.
198.WHILE : 'while'
199. ;
200.
201.BREAK : 'break'
202. ;
203.
204.READ : 'read'
205. ;
206.
207.WRITE : 'write'
208. ;
209.
210.INT : 'int'
211. ;
212.
213.REAL : 'real'
214. ;
215.
216.Identifier
217. : LetterOrUnderscore ( LetterOrUnderscore | Digit )*
218. ;
219.
220.Integer : Digit+
221. ;
222.
223.RealNumber
224. : Digit+ '.' Digit+
225. ;
226.
227.fragment
228.Digit : '0'..'9'
229. ;
230.
231.fragment
232.LetterOrUnderscore
233. : Letter | '_'
234. ;
235.
236.fragment
237.Letter : ( 'a'..'z' | 'A'..'Z' )
238. ;
239.
240.WS : ( ' ' | '\t' | '\r' | '\n' )+ { $channel = HIDDEN; }
241. ;
242.
243.Comment
244. : '/*' ( options { greedy = false; } : . )* '*/' { $channel = HIDDEN; }
245. ;
246.
247.LineComment
248. : '//' ~ ('\n'|'\r')* '\r'? '\n' { $channel = HIDDEN; }
249. ;
基本上是怎麼簡單怎麼寫弄出來的語法而已。有些地方，例如下標表達式（index expression），是 可以顯式寫這麼一條規則：
Java代碼
indexExpression : expression | indexExpression '[' Integer ']' ;
然後削除直接左遞歸：
Java代碼
indexExpression : expression ( '[' Integer ']' )* ;
然後看情況再消除間接左遞歸。
但在Jerry語言裡，能使用下標的只有數組變量，那就干脆不定義單獨的下標表達式，而直接把下標的 操作合並到variableAccess規則的數組變量分支裡，也就是：
Java代碼
variableAccess : Identifier ( '[' Integer ']' )* ;
另外Jerry語言裡的左值也只可能用變量訪問來表示，所以也沒有針對左值寫特殊的規則（賦值表達式 和read語句都需要用到左值的概念），直接就用variableAccess了。
這語法只是大概猜的而已。有些細節在NeuronR的帖子裡沒有提到，所以語法或許與他的課程實踐的要 求不完全一樣。Anyway，我就先以這個理解為基礎來平行做後續的實現了。
幾個不太肯定的細節：
1、if和while語句的條件表達式的類型有沒有要求？
我這裡是不在語法上對表達式類型做限制，到後面的語義分析的時候再檢查。
2、int/real與邏輯/比較運算表達式的類型（boolean）是否有隱式轉換的關系？
我這裡假設是“有”。如果有的話，relationalExpression那裡就能偷懶；不然可能得做點麻煩些的 處理……
主要是關系到那個一元布爾否定運算符（'!'），C-like語言裡它應該是跟一元算術求反運算符（'-' ）的優先級一樣吧？在這個Jerry語言它的優先級裡卻比所有算術和比較運算符要低。
看像這樣的Java代碼：
Java代碼
public class Test {
public static void main(String[] args) {
if (! 1 != 1 || 1 == 1 ) { System.out.println("true"); }
else { System.out.println("false"); }
}
}
編譯的時候會有錯誤，因為!的優先級比!=高，而!不能作用在類型為int的1上；
但這樣的Jerry代碼：
C代碼
if (! 1 != 1 || 1 == 1 ) write 1; else write 0;
卻應該能正確編譯，且運行結果為1，因為!的優先級比!=低而比||高，所以1 != 1是false，它的反是 true；然後1 == 1是true，跟前面的true做或運算也還是true。
這語法比較的詭異……
3、變量聲明是否一定要一並出現在同一個作用域的其它語句的前面（就像C89那樣）？
我這裡假設是“否”。變量可以在任何能出現語句的地方出現。作用域從聲明開始，到它的包圍塊結 束為止。
4、浮點數的字面量是否要求小數點前必須有至少一位數字？浮點數字面量是否允許或要求後綴修飾（ 例如'r'或者'f'或者'd'之類）？
我的假設是浮點數只有一種字面量，滿足這種形式：（用Perl兼容的正則表達式表示）
Js代碼
/\d+\.\d+/
也就是小數點前後都必須有數字，而且沒有後綴。
5、多維數組的語義是怎樣的？
能否支持這樣的聲明和賦值：
Java代碼
int array2d[2][]; int array1d[10]; array2d[0] = array1d;
這個沒辦法假設……只能暫時認為數組聲明的時候是多少維在訪問的時候也必須用多少維來訪問；這 樣比較簡單，哈哈。
6、數組聲明的時候，是否允許用數組字面量來初始化？
我這裡假設是“是”。
7、數組字面量是否允許空元素？同時，數組可否聲明為零長度的？
我這裡假設數組字面量不允許內容為空（跟C一樣），數組也不可以聲明為零長度的。
8、是否有強制類型轉換的表達式？（根據原帖，賦值表達式有類型轉換語義）
這裡假設是“否”。有C-style的強制類型轉換的話語法會麻煩不少……
暫時就先這樣吧。上面的語法裡有經典的dangling-else問題；不過ANTLR默認是匹配優先，能自動消 除這個二義性，所以就沒做特別的處理。
對這樣的一段代碼來測試：
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;
可以生成這樣的解析樹（parse tree）：
這個測試是通過ANTLRWorks的Interpreter模式來做的。編寫本文的時候，最新版是1.2.2。可以在這 裡獲取。
觀察此解析樹：
輸入進來的源碼是一維的，而現在生成的解析樹已經有了層次結構，變成二維的了。在得到層次結構 後，原本用來標識層次結構的標點符號就變得冗余了，但這棵解析樹仍然含有這些冗余的標點符號。
另外，可以觀察到解析樹裡的許多子樹中每個節點都只有一個子節點；這樣的子樹的中間節點都可以 認為是冗余的。出現這種冗余的原因是：為了描述表達式中運算符的優先級高低，用LL語法需要為每一個 優先級都寫一條規則，每匹配到一個中間規則解析樹裡就多一個中間節點。
這些冗余對後續處理來說都是不利的。為了得到更干淨更便於處理的表示，我們需要消除冗余，把解 析樹轉換為抽象語法樹（abstract syntax tree, AST）。這個時候ANTLR的重寫規則（rewrite rule）就 非常有用了。下一篇就來看看如何應用重寫規則來得到抽象語法樹。
