ANTLR 3 語法開發實戰（三）：優化 AST 結構與切換 CSharp2 目標

本篇目標

1. 調整樹重寫規則，生成更易於 Tree Grammar 解析的 AST
2. 將生成目標從 Java 切換至 CSharp2，引入 .NET 生態

切換 CSharp2 目標步驟

1. 下載 ANTLR 3.1.1 CSharp Runtime** (Antlr3.Runtime.dll)
2. Grammar 選項：language = CSharp2;
3. 嵌入動作語法調整：
   System.out.println → Console.WriteLine
toStringTree → ToStringTree
clear → Clear
4. 編譯參考：Antlr3.Runtime.dll + Antlr3.Utility.dll + StringTemplate.dll

AST 結構優化核心：降低 Lookahead 需求

ANTLR 以深度優先遍歷 AST，可視為一維 Token 流：

ROOT → DOWN → child1 → child2 → ... → UP → ...

Tree Grammar 中的 ^( ... ) 隱含 DOWN/UP。Lookahead 數直接影響生成代碼複雜度（每多一層巢狀 if-else）。

優化前：variableDeclaration 產生單一 VAR_DECL 根節點，類型資訊包含在子樹

// Tree Grammar 需 3 步 lookahead 區分分支
type : ^(SIMPLE_TYPE INT) | ^(SIMPLE_TYPE REAL) | ^(ARRAY_TYPE INT Integer+) | ^(ARRAY_TYPE REAL Integer+);

優化後：拆分為四種獨立虛構 Token 根節點

tokens {
  SIMPLE_VAR_DECL; SIMPLE_VAR_DECL_INIT;
  ARRAY_VAR_DECL; ARRAY_VAR_DECL_INIT;
  // ...
}

重寫規則範例：

variableDeclaration
: typeSpecifier
  ( id1=Identifier
    (   -> ^(SIMPLE_VAR_DECL[$id1, "VarDecl"] ^(typeSpecifier) $id1)
    |   EQ expression -> ^(SIMPLE_VAR_DECL_INIT[$id1, "VarDeclInit"] ^(typeSpecifier) $id1 expression)
    |   (LBRACK Integer RBRACK)+ -> ^(ARRAY_VAR_DECL[$id1, "VarDecl"] ^(typeSpecifier Integer+) $id1)
    |   (LBRACK Integer RBRACK)+ EQ arrayLiteral -> ^(ARRAY_VAR_DECL_INIT[$id1, "VarDeclInit"] ^(typeSpecifier Integer+) $id1 arrayLiteral)
    )
  )
  ( COMMA id2=Identifier
    (   -> $variableDeclaration ^(SIMPLE_VAR_DECL[$id2, "VarDecl"] ^(typeSpecifier) $id2)
    |   EQ exp=expression -> $variableDeclaration ^(SIMPLE_VAR_DECL_INIT[$id2, "VarDeclInit"] ^(typeSpecifier) $id2 $exp)
    |   (LBRACK dim1+=Integer RBRACK)+ -> $variableDeclaration ^(ARRAY_VAR_DECL[$id2, "VarDecl"] ^(typeSpecifier $dim1+) $id2)
    |   (LBRACK dim2+=Integer RBRACK)+ EQ al=arrayLiteral -> $variableDeclaration ^(ARRAY_VAR_DECL_INIT[$id2, "VarDeclInit"] ^(typeSpecifier $dim2+) $id2 $al)
    )
    { if ($dim1!=null) $dim1.Clear(); if ($dim2!=null) $dim2.Clear(); }
  )*
  SEMICOLON
;

優化後 Tree Grammar 變簡單

simpleType : INT | REAL;           // 1 lookahead
arrayType  : ^(INT Integer+) | ^(REAL Integer+); // 1 lookahead

保留 Token 位置資訊

原寫法丟失位置：

MINUS primaryExpression -> ^(UNARY_MINUS primaryExpression)

改為繼承來源 Token 屬性：

MINUS primaryExpression -> ^(UNARY_MINUS[$MINUS] primaryExpression)

後續錯誤報告、IDE 高亮可精準定位至原始碼位置。

完整 Grammar (Jerry.g)

grammar Jerry;
options { language = CSharp2; output = AST; ASTLabelType = CommonTree; }
tokens {
  SIMPLE_VAR_DECL; SIMPLE_VAR_DECL_INIT; ARRAY_VAR_DECL; ARRAY_VAR_DECL_INIT;
  ARRAY_LITERAL; SIMPLE_VAR_ACCESS; ARRAY_VAR_ACCESS; UNARY_MINUS;
  BLOCK; EMPTY_BLOCK; EXPR_STMT;
}
// parser rules ... (詳見原文完整列表)
// lexer rules ... (標準運算子、關鍵字、識別字、常數、空白、註解)

C# 測試驅動程式

using System; using System.IO;
using Antlr.Runtime; using Antlr.Runtime.Tree; using Antlr.Utility.Tree;

sealed class TestJerryAst {
  static void Main(string[] args) {
    bool genDot = false; string srcFile;
    // 參數解析 -dot srcFile
    var input = new ANTLRReaderStream(File.OpenText(srcFile));
    var lexer = new JerryLexer(input);
    var tokens = new CommonTokenStream(lexer);
    var parser = new JerryParser(tokens);
    var ast = (CommonTree) parser.program().Tree;

    if (genDot) {
      var dotgen = new DOTTreeGenerator();
      Console.WriteLine(dotgen.ToDOT(ast));
    } else {
      Console.WriteLine(ast.ToStringTree());
    }
  }
}

測試樣本與輸出

輸入 Jerry 代碼：

int i = 1, j;
int x = i + 2 * 3 - 4 / (6 - -7);
int arr[2][3] = {{0,1,2},{3,4,6}};
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 PNG)：

設計原則總結

• AST 節點類型即文法分支決策依據：讓根節點 Token 直接語義化，Tree Grammar 可單一 Lookahead 決策。
• 語言設計啟示：關鍵字前綴（如 var, function）使 LL(1) 解析成為可能；C 風格聲明（類型在前、修飾在後）天然需要更多 Lookahead。
• 工具鏈：ANTLRWorks 編輯 → 生成代碼 → C# 編譯 → DOT 視覺化驗證，形成完整開發迴路。

下一篇將展示針對此 AST 的 Tree Grammar 實作，完成語義分析與解譯器/編譯器前端構建。