ANTLR 3 樹重寫規則深度解析：從解析樹到抽象語法樹

背景

上篇定義了 Jerry 語言基礎詞法/語法，使用 ANTLRWorks 測試生成具體語法樹（Parse Tree），節點過多含標點、關鍵字等雜訊。本篇引入樹重寫規則，將其精簡為抽象語法樹（AST）。

啟用 AST 生成選項

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

虛構 Token 定義

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

這些 Token 不存在於輸入文本，僅作為 AST 節點類型標識，便於後續 Tree Grammar 匹配。

兩種重寫語法形式

1. 行內運算子（Inline Operators）

• ^：標記為當前子樹根節點
• !：排除，不出現在 AST 中

範例：

whileStatement : WHILE^ LPAREN! expression RPAREN! statement;

生成：^(WHILE expression statement)

2. 顯式重寫規則（Explicit Rewrite Rules）

語法：原規則 -> ^(ROOT child1 child2 ...)

範例：

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

優勢：結構一目瞭然，適合複雜重組。

關鍵規則實作解析

表達式優先級與左結合

ANTLR 禁用左遞歸，採用迴圈模擬左結合：

additiveExpression
  : multiplicativeExpression (additiveOperator^ multiplicativeExpression)* ;

additiveOperator^ 使每個運算符成為新子樹根，左操作數為前一子樹，右操作數為下一 multiplicativeExpression，自然形成左結合 AST。

變量聲明（最複雜）

C 風格聲明：int a, b[10], c = 5; 類型資訊分散。重寫規則需處理：

• 簡單/陣列類型
• 有/無初始化
• 多變量以逗號分隔

使用 $variableDeclaration 引用前一分支生成的樹，追加新變量節點：

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)
    | ... 類似四種情況 ...
    )
  )*
  SEMICOLON
;

塊語句支援空塊

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

測試驅動程式

public class TestJerry {
  public static void main(String[] args) throws Exception {
    ANTLRInputStream input = new ANTLRInputStream(System.in);
    JerryLexer lexer = new JerryLexer(input);
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    JerryParser parser = new JerryParser(tokens);
    parser.program(); // 內部嵌入動作列印 AST
  }
}

編譯執行

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

AST 輸出範例（格式化後）

(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) arr (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)))

核心收穫

• AST 節點類型 = 語義分類：VAR_DECL, UNARY_MINUS, BLOCK 等讓後續處理按語義分派，而非語法結構。
• 重寫規則是「編譯器前端」的核心：將解析器關注的「語法結構」轉換為語義分析器關注的「抽象結構」。
• 虛構 Token 設計原則：每種語義結構一個唯一根 Token，Tree Grammar 可單一 Lookahead 決策。
• 行內 vs 顯式重寫：簡單結構用行內運算子（簡潔）；複雜重組用顯式規則（清晰）。

下一篇將展示基於此 AST 的 Tree Grammar 實作，完成型別檢查、符號表建立、中間代碼生成等語義分析階段。