你好，杯子

2007年5月13日

当我探索用于外部领域特定语言的解析器生成器工具时，我已经说过HelloAntlr和HelloSablecc。如果你花很多时间研究解析器生成器，你不可能不关注那些老牌的工具，比如lex 和 yacc（或者它们的 GNU 版本 flex 和 bison）。我想探索 lex 和 yacc 的工作方式，但我的 C 语言已经生疏了。正如 Erich Gamma 所说，我已经懒得自己清理垃圾了。幸运的是，有一个 Java 版本的 yacc 系统，这正是我需要的。

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 关键字，另一个规则将简单单词返回给解析器。

%%
"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 规则本身包含将项目放入配置中的嵌入式操作。

item ::= K_ITEM WORD:w {: parser.result.addItem(new Item(w)); :}
          ;

这里需要注意的一个小问题是，操作被放入一个与解析器对象不同的类中，因此要访问之前定义的 result 字段，我必须使用操作对象的 parser 字段。我还应该提到，一旦我在这方面做得更多，我就会开始使用 EmbedmentHelper 来保持操作代码的简单性。

使用过 yacc 的人可能会注意到，我可以标记规则的元素，以便在操作中引用它们，而不是 yacc 中使用的 $1、$2 约定。类似地，如果规则返回一个值，CUP 使用 RESULT 而不是 $$。

我对 lex 和 yacc 的记忆很模糊，但这些工具似乎很好地模仿了使用它们的方式。到目前为止，我最大的抱怨是错误处理，它给我带来的麻烦比 antlr 多得多。到目前为止，我的感觉是，如果你不熟悉解析器生成器，那么 antlr 是更好的选择（尤其是由于它的书）。但是，如果你熟悉 lex 和 yacc，那么这两个工具足够相似，可以让你利用这些知识。