如何在语法上实现JJTree [英] How to implement JJTree on grammar

查看：224 发布时间：2016/12/22 20:54:27 java parsing compiler-construction abstract-syntax-tree javacc

本文介绍了如何在语法上实现JJTree的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有一个任务，使用JavaCC来做一个自顶向下的语法分析器，语义分析由讲师提供的语言。我有生产规则写出来没有错误。
我完全停留在如何使用JJTree的我的代码和我的时间在搜索互联网的教程没有得到我在任何地方。
只是想知道有人可能花一些时间来解释如何在代码中实现JJTree吗？
或者如果有一个隐藏的分步教程，那里将是一个很大的帮助！

这里有一些我的生产规则，帮帮我。
提前感谢！

  void program（）：{} 
 {
 （））*（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 
< CBR> 
}

解决方案

使用JavaCC创建AST很像创建一个正常解析器（在 jj 文件中定义）。如果你已经有一个工作语法，它是（相对）容易：）

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

将 jj 语法文件重命名为 jjt

使用根标签装饰（斜体字是我自己的术语...）

invoke jjt 语法中的 jjtree ，将生成 jj 为您 c> jj 语法

  > 
 编译生成的 java 源文件
 
 测试

 
 
 这里有一个快速的分步教程，假设你使用MacOS或* nix，有 javacc.jar 文件在您的语法文件相同的目录中，并且 java 和 javac 位于系统的路径： / p> 
 
 
 1 
 
 
 假设您的 jj 语法档 TestParser.jj ，重命名为：
  mv TestParser.jj TestParser。 jjt 
  
 
 
 
 2 
 
 
  ：装饰您的语法，以便创建正确的AST结构。您可以通过添加一个＃后面跟随一个标识符（以及之前的值）来装饰AST（或节点或生产规则：）。在你的原始问题中，你在不同的作品中有很多 #void ，这意味着你为不同的生产规则创建相同类型的AST：这不是你想要的。
 
 
 如果您不装饰生产，生产的名称将用作节点的类型（因此，您可以删除 #void ）：
  $ b {} 
 {
 var_decl（）
 | const_decl（）
}

现在规则只返回AST < c> var_decl（）或 const_decl（）。

查看（简化） var_decl 规则：

  void var_decl #VAR：
 {} 
 {
< VAR> id（）< COL> id（）< EQ> expr（）< SCOL> 
} 
 
 void id（）#ID：
 {} 
 {
< ID> 
} 
 
 void expr（）#EXPR：
 {} 
 {
< ID> $ V $ <$> $ V $ <$> 
 
 
 
 
 $ b $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ code>类型。现在这意味着此规则将返回以下树结构：
  VAR 
 / | \ 
 / | \ 
 ID ID EXPR 
  
如您所见，终端从AST ！这也意味着 id 和 expr 规则使它们的< ID> / code>终端匹配。当然，这不是你想要的。对于需要保持内部文本与终端匹配的规则，您需要明确地将树的 .value 设置为 .image 匹配的终端：
  void id（）#ID：
 {Token t;} 
 {
t =< ID> {jjtThis.value = t.image;} 
} 
 
 void expr（）#EXPR：
 {Token t;} 
 {
t = ; ID> {jjtThis.value = t.image;} 
} 
  
 $ c>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> > 
} 
 
跳过：{| \t| \r| \ n} 
 
 SimpleNode程序（）#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：
 {} 
 {
 < 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 
  
 
 
 < h1> 5  
 
 
要编译所有源文件，请执行：
  javac -cp：：javacc.jar * .java 
    code> javac -cp。; javacc.jar * .java ）
 
 
  6 
 
 
 真理的时刻到来了：让我们看看一切是否真的奏效！让解析器处理输入：
  var n：int = I; 
 
 const x：bool = B; 
 
 double f（a，b，c）
 {
} 
  
 
 b $ b 
执行以下命令：
  java -cp。 TestParservar n：int = I; const x：bool = B; double f（a，b，c）{}
  
，您应该会在控制台上看到以下内容：
程序
 decl 
 VAR 
 ID 
 ID 
 EXPR 
 decl 
 CONST 
 ID 
 ID 
 EXPR 
功能
 TYPE 
 ID 
 PARAMS 
 PARAM 
 PARAM 
 PARAM 
 
请注意，看到文本 ID 的匹配，但相信我，他们在那里。  dump（）根本不显示。
 
 
  HTH 
 
 
  EDIT 
 
 
 对于包含表达式的工作语法，您可以查看下列表达式求值器：https://github.com/bkiers/Curta （语法位于 src / grammar ）。您可能想要了解如何在二进制表达式的情况下创建根节点。
 
I have an assignment to use JavaCC to make a Top-Down Parser with Semantic Analysis for a language supplied by the lecturer. I have the production rules written out and no errors.
I'm completely stuck on how to use JJTree for my code and my hours of scouring the internet for tutorials hasn't gotten me anywhere.
Just wondering could anyone take some time out to explain how to implement JJTree in the code?
Or if there's a hidden step-by-step tutorial out there somewhere that would be a great help!

Here are some of my production rules in case they help.
Thanks in advance!
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>
}

 解决方案 
Creating an AST using JavaCC looks a lot like creating a "normal" parser (defined in a jj file). If you already have a working grammar, it's (relatively) easy :)

Here are the steps needed to create an AST:

rename your jj grammar file to jjt
decorate it with root-labels (the italic words are my own terminology...)
invoke jjtree on your jjt grammar, which will generate a jj file for you
invoke javacc on your generated jj grammar
compile the generated java source files
test it
Here's a quick step-by-step tutorial, assuming you're using MacOS or *nix, have the javacc.jar file in the same directory as your grammar file(s) and java and javac are on your system's PATH:

1

Assuming your jj grammar file is called TestParser.jj, rename it:
mv TestParser.jj TestParser.jjt


2

Now the tricky part: decorating your grammar so that the proper AST structure is created. You decorate an AST (or node, or production rule (all the same)) by adding a # followed by an identifier after it (and before the :). In your original question, you have a lot of #void in different productions, meaning you're creating the same type of AST's for different production rules: this is not what you want.

If you don't decorate your production, the name of the production is used as the type of the node (so, you can remove the #void):
void decl() :
{}
{
     var_decl()
  |  const_decl()
}
Now the rule simply returns whatever AST the rule var_decl() or const_decl() returned.

Let's now have a look at the (simplified) var_decl rule:
void var_decl() #VAR :
{}
{
  <VAR> id() <COL> id() <EQ> expr() <SCOL>
}

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

void expr() #EXPR :
{}
{
  <ID>
}
which I decorated with the #VAR type. This now means that this rule will return the following tree structure:
    VAR 
   / | \
  /  |  \
ID  ID  EXPR
As you can see, the terminals are discarded from the AST! This also means that the id and expr rules loose the text their <ID> terminal matched. Of course, this is not what you want. For the rules that need to keep the inner text the terminal matched, you need to explicitly set the .value of the tree to the .image of the matched terminal:
void id() #ID :
{Token t;}
{
  t=<ID> {jjtThis.value = t.image;}
}

void expr() #EXPR :
{Token t;}
{
  t=<ID> {jjtThis.value = t.image;}
}
causing the input "var x : int = i;" to look like this:
       VAR 
        |
    .---+------.
   /    |       \
  /     |        \
ID["x"] ID["int"] EXPR["i"]
This is how you create a proper structure for your AST. Below follows a small grammar that is a very simple version of your own grammar including a small main method to test it all:
// 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

Let the jjtree class (included in javacc.jar) create a jj file for you:
java -cp javacc.jar jjtree TestParser.jjt


4

The previous step has created the file TestParser.jj (if everything went okay). Let javacc (also present in javacc.jar) process it:
java -cp javacc.jar javacc TestParser.jj


5

To compile all source files, do: 
javac -cp .:javacc.jar *.java
(on Windows, do: javac -cp .;javacc.jar *.java)

6

The moment of truth has arrived: let's see if everything actually works! To let the parser process the input:
var n : int = I; 

const x : bool = B; 

double f(a,b,c) 
{ 
}
execute the following:
java -cp . TestParser "var n : int = I; const x : bool = B; double f(a,b,c) { }"
and you should see the following being printed on your console:
PROGRAM
 decl
  VAR
   ID
   ID
   EXPR
 decl
  CONST
   ID
   ID
   EXPR
 FUNCTION
  TYPE
  ID
  PARAMS
   PARAM
   PARAM
   PARAM
Note that you don't see the text the ID's matched, but believe me, they're there. The method dump() simply does not show it.

HTH

EDIT

For a working grammar including expressions, you could have a look at the following expression evaluator of mine: https://github.com/bkiers/Curta (the grammar is in src/grammar). You might want to have a look at how to create root-nodes in case of binary expressions.

                        这篇关于如何在语法上实现JJTree的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文

`3`

4

6

EDIT

1

2

3

4

5

6

EDIT

如何在语法上实现JJTree [英] How to implement JJTree on grammar

问题描述

1

2

相关文章

Java开发最新文章

热门教程

热门工具

登录关闭

如何在语法上实现JJTree [英] How to implement JJTree on grammar

问题描述

1

2

3

4

6

EDIT

1

2

3

4

5

6

EDIT

相关文章

Java开发最新文章

热门教程

热门工具

登录 关闭

`3`

登录关闭