如何在语法上实现JJTree

Question

我有一个任务是使用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>
}

Answer 1

使用JavaCC创建AST看起来很像创建"普通"解析器(在jj文件中定义).如果你已经有一个工作语法,它(相对)容易:)

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

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

这是一个快速的分步教程,假设你正在使用MacOS或*nix,将javacc.jar文件放在与语法文件相同的目录中,java并且javac在你的系统的路径上:

1

假设您的jj语法文件被调用TestParser.jj,请将其重命名为:

mv TestParser.jj TestParser.jjt

2

现在是棘手的部分:装饰你的语法,以便创建适当的AST结构.您通过在其之后(以及之前)添加一个后跟标识符来装饰 AST(或节点或生产规则(全部相同)).在您的原始问题中,您有很多不同的产品,这意味着您为不同的生产规则创建了相同类型的AST:这不是您想要的.#:#void

如果您没有装饰您的作品,则将作品的名称用作节点的类型(因此,您可以删除#void):

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

现在规则只返回规则var_decl()或const_decl()返回的AST .

现在让我们看看(简化)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丢弃!这也意味着id和expr规则松散了<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

五

要编译所有源文件,请执行:

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) { }"

并且您应该在控制台上看到以下内容:

PROGRAM
 decl
  VAR
   ID
   ID
   EXPR
 decl
  CONST
   ID
   ID
   EXPR
 FUNCTION
  TYPE
  ID
  PARAMS
   PARAM
   PARAM
   PARAM

请注意,你没有看到ID匹配的文字,但请相信我,他们在那里.该方法dump()根本没有显示出来.

HTH

编辑

对于包含表达式的工作语法,您可以查看我的以下表达式求值程序:https://github.com/bkiers/Curta(语法在src/grammar).您可能想要了解如何在二进制表达式的情况下创建根节点.