15

我的任务是使用 JavaCC 为讲师提供的语言制作带有语义分析的自上而下的解析器。我写出了生产规则，没有错误。我完全被困在如何在我的代码中使用 JJTree 并且我在互联网上搜索教程的时间并没有让我到任何地方。只是想知道有人可以花一些时间来解释如何在代码中实现 JJTree 吗？或者，如果有一个隐藏的分步教程，那将是一个很大的帮助！

以下是我的一些生产规则，以防万一。提前致谢！

void program() : {}
{
  (decl())* (function())* main_prog()
}

void decl() #void : {}
{
  (
    var_decl() | const_decl()
   )
}

void var_decl() #void : {}
{
  <VAR> ident_list() <COLON> type()
 (<COMMA> ident_list() <COLON> type())* <SEMIC>
}

void const_decl()  #void : {}
{
  <CONSTANT> identifier() <COLON> type() <EQUAL> expression()
 ( <COMMA> identifier() <COLON> type() <EQUAL > expression())* <SEMIC>
} 

void function() #void : {}
{
  type() identifier() <LBR> param_list() <RBR>
  <CBL>
  (decl())*
  (statement() <SEMIC> )*
  returnRule() (expression() | {} )<SEMIC>
  <CBR>
}
4

2 回答 2

54

使用 JavaCC 创建 AST 看起来很像创建“普通”解析器（在jj文件中定义）。如果你已经有一个有效的语法，它（相对）容易:)

以下是创建 AST 所需的步骤：

  1. 将您的jj语法文件重命名为jjt
  2. 用根标签装饰它（斜体字是我自己的术语......）
  3. 调用jjtree您的jjt语法，这将为您生成一个jj文件
  4. 调用javacc您生成的jj语法
  5. 编译生成的java源文件
  6. 测试一下

这是一个快速的分步教程，假设您使用的是 MacOS 或 *nix，将javacc.jar文件放在与语法文件相同的目录中，java并且javac位于系统的 PATH 中：

1

假设你的jj语法文件被称为TestParser.jj，重命名它：

mv TestParser.jj TestParser.jjt

2

现在是棘手的部分：修饰您的语法，以便创建正确的 AST 结构。您可以通过在它之后（以及在 之前）添加一个后跟一个标识符来装饰AST（或节点，或生产规则（都一样））。在您最初的问题中，您有很多不同的制作，这意味着您正在为不同的制作规则创建相同类型的 AST：这不是您想要的。#:#void

如果您不装饰您的产品，则使用产品的名称作为节点的类型（因此，您可以删除#void）：

void decl() :
{}
{
     var_decl()
  |  const_decl()
}

现在规则只是返回规则var_decl()或返回的任何 AST const_decl()。

现在让我们看一下（简化的）var_decl规则：

void var_decl() #VAR :
{}
{
  <VAR> id() <COL> id() <EQ> expr() <SCOL>
}

void id() #ID :
{}
{
  <ID>
}

void expr() #EXPR :
{}
{
  <ID>
}

我用#VAR类型装饰。现在这意味着该规则将返回以下树结构：

    VAR 
   / | \
  /  |  \
ID  ID  EXPR

如您所见，终端已从 AST 中丢弃！这也意味着idandexpr规则会丢失与<ID>终端匹配的文本。当然，这不是你想要的。对于需要保持终端匹配的内部文本的规则，您需要将.value树的显式设置.image为匹配终端的 ：

void id() #ID :
{Token t;}
{
  t=<ID> {jjtThis.value = t.image;}
}

void expr() #EXPR :
{Token t;}
{
  t=<ID> {jjtThis.value = t.image;}
}

导致输入"var x : int = i;"看起来像这样：

       VAR 
        |
    .---+------.
   /    |       \
  /     |        \
ID["x"] ID["int"] EXPR["i"]

这就是您为 AST 创建适当结构的方式。下面是一个小语法，它是您自己的语法的一个非常简单的版本，包括一个main测试它的小方法：

// TestParser.jjt
PARSER_BEGIN(TestParser)

public class TestParser {
  public static void main(String[] args) throws ParseException {
    TestParser parser = new TestParser(new java.io.StringReader(args[0]));
    SimpleNode root = parser.program();
    root.dump("");
  }
}

PARSER_END(TestParser)

TOKEN :
{
   < OPAR  : "(" > 
 | < CPAR  : ")" >
 | < OBR   : "{" >
 | < CBR   : "}" >
 | < COL   : ":" >
 | < SCOL  : ";" >
 | < COMMA : "," >
 | < VAR   : "var" >
 | < EQ    : "=" > 
 | < CONST : "const" >
 | < ID    : ("_" | <LETTER>) ("_" | <ALPHANUM>)* >
}

TOKEN :
{
   < #DIGIT    : ["0"-"9"] >
 | < #LETTER   : ["a"-"z","A"-"Z"] >
 | < #ALPHANUM : <LETTER> | <DIGIT> >
}

SKIP : { " " | "\t" | "\r" | "\n" }

SimpleNode program() #PROGRAM :
{}
{
  (decl())* (function())* <EOF> {return jjtThis;}
}

void decl() :
{}
{
     var_decl()
  |  const_decl()
}

void var_decl() #VAR :
{}
{
  <VAR> id() <COL> id() <EQ> expr() <SCOL>
}

void const_decl() #CONST :
{}
{
  <CONST> id() <COL> id() <EQ> expr() <SCOL>
}


void function() #FUNCTION :
{}
{
  type() id() <OPAR> params() <CPAR> <OBR> /* ... */ <CBR>
}

void type() #TYPE :
{Token t;}
{
  t=<ID> {jjtThis.value = t.image;}
}

void id() #ID :
{Token t;}
{
  t=<ID> {jjtThis.value = t.image;}
}

void params() #PARAMS :
{}
{
  (param() (<COMMA> param())*)?
}

void param() #PARAM :
{Token t;}
{
  t=<ID> {jjtThis.value = t.image;}
}

void expr() #EXPR :
{Token t;}
{
  t=<ID> {jjtThis.value = t.image;}
}

3

让jjtree类（包含在 中javacc.jar）为您创建一个jj文件：

java -cp javacc.jar jjtree TestParser.jjt

4

上一步已创建文件TestParser.jj（如果一切正常）。让javacc（也存在于javacc.jar）处理它：

java -cp javacc.jar javacc TestParser.jj

5

要编译所有源文件，请执行以下操作：

javac -cp .:javacc.jar *.java

（在 Windows 上，执行javac -cp .;javacc.jar *.java：）

6

关键时刻已经到来：让我们看看一切是否真的有效！让解析器处理输入：

var n : int = I; 

const x : bool = B; 

double f(a,b,c) 
{ 
}

执行以下操作：

java -cp . TestParser "var n : int = I; const x : bool = B; double f(a,b,c) { }"

您应该会在控制台上看到以下内容：

程序
 声明
  VAR
   ID
   ID
   EXPR
 声明
  常数
   ID
   ID
   EXPR
 功能
  类型
  ID
  参数
   参数
   参数
   参数

请注意，您看不到ID' 匹配的文本，但相信我，它们就在那里。该方法dump()根本没有显示它。

高温高压

编辑

对于包含表达式的有效语法，您可以查看我的以下表达式评估器：https ://github.com/bkiers/Curta （语法在 中src/grammar）。您可能想看看如何在二进制表达式的情况下创建根节点。

于 2012-12-17T20:08:47.710 回答
3

这是一个使用 JJTree http://anandsekar.github.io/writing-an-interpretter-using-javacc/的示例

于 2014-08-19T17:22:45.913 回答