你好 Sablecc

我最近對 SableCC 進行了一些小嘗試。花了一點功夫才讓「Hello World」風格的剖析器運作起來，因此我想在此記錄一下我讓它運作的步驟。我不是說這是最好的方法，但如果你想嘗試看看，這可能會有幫助。

SableCC 是 Java 環境的編譯器編譯器工具。它處理 LALR(1) 文法（對於記得文法類別的人來說）。換句話說，它是一個自底向上的剖析器（不像 JavaCC 和 Antlr 是自頂向下的）。

與大多數編譯器編譯器工具一樣，你可以在文法檔案中定義語言的文法，並執行編譯器編譯器來產生此語言的剖析器。由於這是 hello-world 範例，我的語言是一個極簡語言，只是為了讓編譯器編譯器運作。語言只是一個項目清單，如下所示

item camera
item laser

其中「item」是一個關鍵字，第二個字是一個名稱。我希望剖析器將它轉換成 Configuration 類別的實例，其中包含一個項目清單。

public class Configuration {
  private Map<String, Item> items = new HashMap<String, Item>();
  public Item getItem(String key) {
    return items.get(key);
  }
  public void addItem(Item arg) {
    items.put(arg.getName(), arg);
  }
public class Item {
  private String name;
  public Item(String name) {
     this.name = name;
   }

我先前展示的輸入應該被讀取，以通過以下測試。

    @Test public void itemsAddedToItemList() {
      Reader input = null;
      try {
        input = new FileReader("rules.txt");
      } catch (FileNotFoundException e) {
        throw new RuntimeException(e);
      }
      Configuration config = CatalogParser.parse(input);
      assertNotNull(config.getItem("camera"));
      assertNotNull(config.getItem("laser"));
    }

當然，對這種情況使用編譯器編譯器是完全殺雞用牛刀，但 hello-world 範例的重點是在簡單情況下讓環境運作，這樣你才能在基礎運作的情況下轉到有趣的案例。每當我嘗試新的技術時，我總是想先讓類似這樣的東西運作，然後再深入探討有趣的方面。

使用編譯器編譯器會讓建置程序變得更複雜一點。你必須先對語法檔案執行編譯器編譯器以產生剖析器，然後編譯自訂程式碼和產生的剖析器以建立整體程式，然後執行（並測試它）。因此，在這個時候，我無法只在 IntelliJ 中完成所有事情，實際上必須組合一個 ant 檔案。我已經有一段時間沒有組合 ant 檔案了，所以花了一點時間才重新記起如何使用 ant 語言。為了執行 SableCC，我使用了 Java 任務

   <property name = "gendir" value = "gen"/>
   <target name = "gen" >
      <mkdir dir="${gendir}"/>
      <java jar = "lib/sablecc.jar" fork = "true" failonerror="true">
         <arg value = "-d"/>
         <arg value = "${gendir}"/>
         <arg value = "catalog.sable"/>
      </java>
    </target>

我將程式碼產生到 gen 目錄中，以將它與我在 src 和 test 目錄中自行編寫的程式碼分開。然後使用 javac 任務將所有內容編譯在一起。

 <property name = "builddir" value = "classes/production/sable"/>
  <path id="classpath">
       <fileset dir = "lib">
           <include name = "*.jar"/>
       </fileset>
       <pathelement path = "${builddir}"/>
  </path>
  <target name = "compile" depends = "gen, copyDats">
    <mkdir dir="${builddir}"/>
    <javac destdir="${builddir}" classpathref="classpath">
      <src path = "src"/>
      <src path = "${gendir}"/>
      <src path = "test"/>
    </javac>
  </target>

除了編譯之外，我還必須將兩個剖析器資料檔移到建置目錄中。資料包含用於剖析器和詞法分析器的表格。建置目錄以我擁有的方式嵌套，因此它將與 IntelliJ 完美地搭配運作。（我真的很應該將測試分隔到一個單獨的輸出目錄中，但我當時感到很懶惰。）

  <target name = "copyDats">
      <mkdir dir="${builddir}"/>
      <copy todir = "${builddir}">
        <fileset dir = "${gendir}" includes = "**/lexer.dat"/>
        <fileset dir = "${gendir}" includes = "**/parser.dat"/>
      </copy>
    </target>

然後我有一個測試任務來執行測試。

  <target name = "test" depends="compile">
     <junit haltonfailure = "on">
      <formatter type="brief"/>
      <classpath refid = "classpath"/>
      <batchtest todir="${builddir}" >
        <fileset dir = "test" includes = "**/*Tester.java"/>
      </batchtest>
     </junit>
   </target>

為了讓剖析器啟動並執行，我需要使用 SableCC 的語法語法定義簡單語言的語法。

Package catalogParser;

Tokens
  itemdef = 'item';
  string = ['a' .. 'z'] +;
  blank = (' ' | 13 | 10)+;
  
Ignored Tokens
    blank;

Productions
  configuration =
    item *
  ;
  item = 
    itemdef string
  ;

與大多數編譯器編譯器一樣，SableCC 將工作拆分為詞法分析器和剖析器。詞法分析器讀入字元並將它們分塊為由語法檔案的 Tokens 區段定義的代碼。在這種情況下，它非常簡單：字串是小寫字母，關鍵字 item 是它自己的代碼。我也定義了空白是什麼，並在 Ignores 子句中告訴詞法分析器將它丟棄。

然後，詞法分析器會將 itemdef 和 string 代碼串流提供給剖析器。剖析器使用兩個產生式來處理這個問題。它將組態描述為多個項目，每個項目為一個 itemdef 和一個字串（用於其名稱）。

這定義了輸入的語法，但沒有說明如何從輸入取得我的組態和項目物件。為了執行這個動作，我需要撰寫一些程式碼來對應我已剖析的內容和我想建立的物件。在大多數編譯器編譯器中，我透過將動作嵌入語法中來執行這個動作。然而，SableCC 以另一種方式運作。它會自動建立剖析樹，然後提供一個訪客給我來遍歷這個剖析樹。然後，我可以對訪客進行子類別化以執行有趣的動作。在這種情況下，當我遍歷剖析樹時，我取得剖析樹上的每個項目節點，並將它轉換成模型中的真實項目。

public class CatalogParser extends DepthFirstAdapter {
  private Configuration result;
  public void outAItem(AItem itemNode) {
    System.out.println("found item");
    result.addItem(new Item(itemNode.getString().toString().trim()));
  }

剖析樹使用命名慣例將語法繫結到在樹中建立的物件。因此，語法會建立稱為 AItem 的節點，以符合語法中的項目產生式。方法 outAItem 會在訪客離開項目節點時呼叫，並允許我存取項目上的任何內容，在這種情況下為基礎字串代碼。然後，我可以使用該字串作為名稱在我的模型中建立項目。

最後一段程式碼是用於執行檔案解析器，我透過將目錄解析器設為命令物件來執行。

  public static Configuration parse(Reader input) {
    Configuration result = new Configuration();
    new CatalogParser(input, result).run();
    return result;
  }
  public CatalogParser(Reader input, Configuration result) {
    this.input = input;
    this.result = result;
  }
  public void run() {
    try {
      createParser(input).parse().apply(this);
    } catch (Exception e) {
      throw new RuntimeException(e);
     }
  }
  private Parser createParser(Reader input) {
    return new Parser(new Lexer(new PushbackReader(input)));
  }

這就是讓它運作的基本原理。到目前為止，我尚未深入探討，因此我對 SableCC 的想法有點初步，但這個部落格的重點就是寫出半成形的思考。

SableCC 的使用有點尷尬。除了作者的論文之外，幾乎沒有文件。幸運的是，這篇論文比我見過許多其他論文都容易理解，所以我能夠找出如何讓事情運作。在工作期間，我在語法中犯了一個錯誤，發現很難獲得診斷。錯誤訊息沒有提供太多資訊，我訴諸於偵錯程式和列印陳述式，這些陳述式位於產生的解析器程式碼中。幸運的是，問題出在標記化中，因此我透過查看詞法分析器的輸出，了解到我的錯誤。LALR 解析器出了名的難以理解，所以我很高興我不用深入探討。Antlr 在這方面表現得更好。遞迴下降解析器較容易理解，而且有一本Antlr 書籍正在製作中，這應該對我探索它很有幫助。

到目前為止，我還沒有被移除解析器動作並自動產生解析樹的方法說服。由於它是一個解析樹，您必須在它上面執行才能做任何有用的事情。Nat Pryce 讓我瞭解樹狀轉換規則在最新的 SableCC 中，由於它定義了抽象語法樹，而不是解析樹，因此看起來更有用。您仍然必須在它上面執行才能在網域模型中建立物件，但執行起來更容易。（最新版本的 Antlr 具有類似的功能。）樹狀執行的優點之一是，如果我對樹狀執行器進行變更，我就不需要重新產生，這讓我可以在 IntelliJ 中執行。然而，Antlr 具有 AntlrWorks，它可以插入 IntelliJ，看起來非常好。