Hello Cup
2007 年 5 月 13 日
當我探索用於外部 DomainSpecificLanguage 的剖析器產生器工具時，我說過 HelloAntlr 和 HelloSablecc。如果你花很多時間查看剖析器產生器，你不能真的避免查看舊的中堅份子 lex 和 yacc（或它們的 gnu 對應版本 flex 和 bison）。我想探索 lex 和 yacc 的運作方式，但我的 C 已經太生疏了。正如 Erich Gamma 所說的，我太懶得倒自己的垃圾。幸運的是，有一個適用於 Java 的 yaccish 系統實作，這正是我需要的。
Java 實作，就像經典的 lex 和 yacc，是兩個獨立的工具：JFlex 和 CUP。儘管它們是分開開發的，但它們確實提供掛鉤以一起工作。
就像我之前的這方面的文章一樣，這是一個過於簡單的範例，只是為了讓工具運作。我取得一個輸入檔案，其中寫著
item camera item laser
並使用下列模型將它們轉換為組態中的項目物件
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"));
}
第一個問題只是讓建置開始進行。就像我之前的範例一樣，我想取得語法輸入檔案，並將詞法分析器和剖析器產生到 gen 目錄中。與我之前的範例不同，我沒有直接在 ant 中執行此操作，而是使用 ant 呼叫 ruby 腳本。
--- build.xml
<target name = "gen" >
<exec executable="ruby" failonerror="true">
<arg line = "gen.rb"/>
</exec>
</target>
--- gen.rb
require 'fileutils'
include FileUtils
system "java -cp lib/JFlex.jar JFlex.Main -d gen/parser src/parser/catalog.l"
system "java -jar lib/java-cup-11a.jar src/parser/catalog.y"
%w[parser.java sym.java].each {|f| mv f, 'gen/parser'}
是的，我知道這是一個漫長的路徑，但由於有許多原始檔，我正在 FlexibleAntlrGeneration 中使用該方法來執行我的產生，而且我無法在 ant 中對其進行排序。
（當我最近參加 CITCON 時，我驚訝地發現人們對 ant 的滿意度遠高於我的預期。脾氣暴躁的我認為這是斯德哥爾摩症候群的案例。即使脾氣不那麼暴躁，我也在關注 Raven 和 BuildR 等事項，它們現在有一些文件。我已經準備好放棄 ant 了。）
你會注意到 CUP 將其輸出檔案放在目前的目錄中，而且我看不出如何覆寫該行為。因此，我產生它們並使用一個獨立的指令將它們移動。
一旦我產生程式碼，我便使用 ant 編譯和測試它。
<target name = "compile" depends = "gen">
<mkdir dir="${dir.build}"/>
<javac destdir="${dir.build}" classpathref="path.compile">
<src path = "${dir.src}"/>
<src path = "${dir.gen}"/>
<src path = "${dir.test}"/>
</javac>
</target>
<target name = "test" depends="compile">
<junit haltonfailure = "on" printsummary="on">
<formatter type="brief"/>
<classpath refid = "path.compile"/>
<batchtest todir="${dir.build}" >
<fileset dir = "test" includes = "**/*Test.java"/>
</batchtest>
</junit>
</target>
Lex 和 yacc 將詞法分析器和語法分析器分開成不同的檔案。每個檔案獨立產生，並在編譯期間合併。我將從詞法分析器檔案 (catalog.l) 開始。開啟宣告輸出檔案的套件並匯入。
package parser; import java_cup.runtime.*;
JFlex 使用 %% 標記將檔案分成區段。第二個區段包含各種宣告。第一個位元組命名輸出類別，並告訴它與 CUP 介接。
%% %class Lexer %cup
下一個位元組是摺疊到詞法分析器的程式碼。在此，我定義一個函式來建立 Symbol 物件 - 再次連結到 CUP。
%{
private Symbol symbol(int type) {
return new Symbol(type, yytext());
}
%}
Symbol 類別在 CUP 中定義，並且是其執行時期 jar 的一部分。有各種建構函式，採用關於符號及其位置的各種資訊。
接下來是定義單字和空白字元的巨集。
Word = [:jletter:]* WS = [ \t\r\n]
最後一個區段是實際的詞法分析器規則。我定義一個用於傳回項目關鍵字，另一個用於傳回簡單單字給語法分析器。
%%
"item" {return symbol(sym.K_ITEM);}
{Word} {return symbol(sym.WORD);}
{WS} {/* ignore */}
因此，詞法分析器會傳送 K_ITEM 和 WORD 權杖串流給語法分析器。我在 catalog.y 中定義語法分析器。它再次從套件和匯入宣告開始。
package parser; import java_cup.runtime.*; import model.*;
我將資料剖析成組態物件，因此我需要宣告一個放置該結果的地方。這段程式碼再次直接複製到語法分析器物件中。
parser code {: Configuration result = new Configuration(); :}
使用 CUP，我需要定義所有將在製程中使用的規則元素。
terminal K_ITEM; terminal String WORD; non terminal catalog, item;
終端機是我從詞法分析器取得的權杖，非終端機是我自己建立的規則。如果我想從權杖取得酬載，我需要宣告其類型，因此 WORD 是字串。
目錄是項目的清單。與 antlr 或 sablecc 不同，我這裡沒有 EBNF，因此我無法說 item*，而是需要一個遞迴規則。
catalog ::= item | item catalog;
項目規則本身包含嵌入式動作，將項目放入組態中。
item ::= K_ITEM WORD:w {: parser.result.addItem(new Item(w)); :}
;
這裡要注意一個小問題，動作被放入語法分析器物件的單獨類別中，因此為了取得我先前定義的結果欄位，我必須使用動作物件的 parser 欄位。我也應該提到，一旦我進一步執行此動作，我便開始使用 EmbedmentHelper 來保持動作程式碼簡單。
以前使用過 yacc 的人可能會注意到，我可以標籤規則的元素，以便在動作中參考它們，而不是 yacc 中使用的 $1、$2 約定。類似地，如果規則傳回值，CUP 會使用 RESULT 而不是 $$。
我對 lex 和 yacc 的記憶已經模糊了，但這些工具似乎很能模仿它們的使用風格。到目前為止，我最大的抱怨是錯誤處理，這比 antlr 讓我更費心。到目前為止，我的感覺是，如果你不熟悉解析器產生器，那麼 antlr 是更好的選擇（特別是因為它的書）。但是，如果你熟悉 lex 和 yacc，那麼這兩者足夠相似，可以建立在這些知識之上。