javacc 教程6 jjtree

我们知道JavaCC是一种编译器开发工具，主要用于解析输入文本并生成与其语法结构相对应的语法树。JavaCC生成的语法树是一种较低级别的抽象，需要开发人员自行定义和实现对其的处理和操作。而JJTree是JavaCC的一个扩展，提供了一种更高级别的抽象。相对于JavaCC，JJTree生成的语法树节点包含属性和方法，可以更方便地构建和处理语法树，尤其是对于复杂的语法结构和语法树节点操作需求。

我们先看下面的示例：

PARSER_BEGIN(Eg1)
package com.github.gambo.javacc.jjtree.eg1;
/** An Arithmetic Grammar. */
public class Eg1 {

  /** Main entry point. */
  public static void main(String args[]) {
    System.out.println("Reading from standard input...");
    Eg1 t = new Eg1(System.in);
    try {
      SimpleNode n = t.Start();
      n.dump("");
      System.out.println("Thank you.");
    } catch (Exception e) {
      System.out.println("Oops.");
      System.out.println(e.getMessage());
      e.printStackTrace();
    }
  }
}

PARSER_END(Eg1)


SKIP :
{
  " "
| "\t"
| "\n"
| "\r"
| <"//" (~["\n","\r"])* ("\n"|"\r"|"\r\n")>
| <"/*" (~["*"])* "*" (~["/"] (~["*"])* "*")* "/">
}

TOKEN : /* LITERALS */
{
  < INTEGER_LITERAL:
        <DECIMAL_LITERAL> (["l","L"])?
      | <HEX_LITERAL> (["l","L"])?
      | <OCTAL_LITERAL> (["l","L"])?
  >
|
  < #DECIMAL_LITERAL: ["1"-"9"] (["0"-"9"])* >
|
  < #HEX_LITERAL: "0" ["x","X"] (["0"-"9","a"-"f","A"-"F"])+ >
|
  < #OCTAL_LITERAL: "0" (["0"-"7"])* >
}

TOKEN : /* IDENTIFIERS */
{
  < IDENTIFIER: <LETTER> (<LETTER>|<DIGIT>)* >
|
  < #LETTER: ["_","a"-"z","A"-"Z"] >
|
  < #DIGIT: ["0"-"9"] >
}

/** Main production. */
SimpleNode Start() : {}
{
  Expression() ";"
  { return jjtThis; }
}

/** An Expression. */
void Expression() : {}
{
  AdditiveExpression()
}

/** An Additive Expression. */
void AdditiveExpression() : {}
{
  MultiplicativeExpression() ( ( "+" | "-" ) MultiplicativeExpression() )*
}

/** A Multiplicative Expression. */
void MultiplicativeExpression() : {}
{
  UnaryExpression() ( ( "*" | "/" | "%" ) UnaryExpression() )*
}

/** A Unary Expression. */
void UnaryExpression() : {}
{
  "(" Expression() ")" | Identifier() | Integer()
}

/** An Identifier. */
void Identifier() : {}
{
  <IDENTIFIER>
}

/** An Integer. */
void Integer() : {}
{
  <INTEGER_LITERAL>
}

这是一个解析算数表达式的语法文件，相比之前的javacc语法文件，增加了通过SimpleNode 的dump方法发打印语法树的层次结构。

我们可以看一下ant的构建配置：|

  <target name="eg1" description="Builds example 'eg1'">
    <delete dir="${build.home}/jjtree"/>
    <mkdir dir="${build.home}/jjtree"/>
    <copy file="eg1.jjt" todir="${build.home}/jjtree"/>
    <jjtree target="eg1.jjt" outputdirectory="${build.home}/jjtree" javacchome="${javacc.home}"/>
    <javacc target="${build.home}/jjtree/eg1.jj" outputdirectory="${build.home}/jjtree" javacchome="${javacc.home}"/>
    <javac deprecation="false" srcdir="${build.home}/jjtree" destdir="${build.class.home}" includeantruntime='false'/>
    <echo message="*******"/>
    <echo message="******* Now cd into the eg1 directory and run 'java Eg1' ******"/>
    <echo message="*******"/>
  </target>

可以看到先通过jjtree命令生成xxx.jj文件，再通过javacc命令生成构建java代码。最终生成的文件如下：

运行Eg1的main方法然后输入(a + b) * (c + 1); 注意一定要输入分号,运行结果：

Reading from standard input...
(a + b) * (c + 1);
Start
 Expression
  AdditiveExpression
   MultiplicativeExpression
    UnaryExpression
     Expression
      AdditiveExpression
       MultiplicativeExpression
        UnaryExpression
         Identifier
       MultiplicativeExpression
        UnaryExpression
         Identifier
    UnaryExpression
     Expression
      AdditiveExpression
       MultiplicativeExpression
        UnaryExpression
         Identifier
       MultiplicativeExpression
        UnaryExpression
         Integer
Thank you.

可以看到其按照产生式的调用顺序生成了层级结构。
 

Node

默认情况下，JJTree生成代码来为每个非终结符构造解析树节点。我们也可以修改此行为，使某些非终结符不生成节点， 或者为产生式扩展的一部分节点。

JJTree 定义了一个所有解析树节点必须实现的 Java 接口 `Node`。该接口提供了一些方法：为当前节点添加父节点, 和添加子节点，并检索他们。在我们生成的代码里又存在一个名为Node的interface，其结构如下：

public interface Node {

  // 此方法在节点成为当前节点后调用。它表明当前节点现在可以添加子节点。
  public void jjtOpen();

  // 子节点添加完毕后，将调用此方法。
  public void jjtClose();

  //这对方法分别用于设置节点的父节点和获取节点的父节点
  public void jjtSetParent(Node n);
  public Node jjtGetParent();

  //方法将指定的节点添加到当前节点的子节点列表中
  public void jjtAddChild(Node n, int i);

  //获取指定索引的子节点
  public Node jjtGetChild(int i);

  //获取子节点的数量
  public int jjtGetNumChildren();

  public int getId();
}

我们可以实现一个SimpleNode.class 实现了Node接口，我们可以自己实现它 如果它不存在，则由JJTree自动生成。 我们可以将这个类用作节点实现的模板或父类，也可以对他进行修改。 SimpleNode 还提供了一个基本机制，用于递归的转储节点及其子节点。我们可以观察一下生成的SimpleNode的dump方法。

  public void dump(String prefix) {
    System.out.println(toString(prefix));
    if (children != null) {
      for (int i = 0; i < children.length; ++i) {
        SimpleNode n = (SimpleNode)children[i];
        if (n != null) {
          n.dump(prefix + " ");
        }
      }
    }
  }

这也是我们在main函数中执行性dump方法后会打印层级结构的原因。

定义节点的名称和条件

我们观察一下上面的运行结果，一个简单的算术表达式生成了20多个节点，实际上很多中间的过度节点是不必要生成的，比如UnaryExpression，express等，我们希望只生成和算术表达式直接相关的节点。并且节点名称都以产生式名称命名，无法直观的分辨出哪个是加号节点哪个是乘号节点，总的来说可读性不高。

我们把上面的例子改进一下：

options {
  MULTI=true;
  KEEP_LINE_COLUMN = false;
}

PARSER_BEGIN(Eg2)
package com.github.gambo.javacc.jjtree.eg2;
/** An Arithmetic Grammar. */
public class Eg2 {

  /** Main entry point. */
  public static void main(String args[]) {
    System.out.println("Reading from standard input...");
    Eg2 t = new Eg2(System.in);
    try {
      ASTStart n = t.Start();
      n.dump("");
      System.out.println("Thank you.");
    } catch (Exception e) {
      System.out.println("Oops.");
      System.out.println(e.getMessage());
      e.printStackTrace();
    }
  }
}

PARSER_END(Eg2)


SKIP :
{
  " "
| "\t"
| "\n"
| "\r"
| <"//" (~["\n","\r"])* ("\n"|"\r"|"\r\n")>
| <"/*" (~["*"])* "*" (~["/"] (~["*"])* "*")* "/">
}

TOKEN : /* LITERALS */
{
  <  INTEGER_LITERAL:
        <DECIMAL_LITERAL> (["l","L"])?
      | <HEX_LITERAL> (["l","L"])?
      | <OCTAL_LITERAL> (["l","L"])?
  >
|
  < #DECIMAL_LITERAL: ["1"-"9"] (["0"-"9"])* >
|
  < #HEX_LITERAL: "0" ["x","X"] (["0"-"9","a"-"f","A"-"F"])+ >
|
  < #OCTAL_LITERAL: "0" (["0"-"7"])* >
}

TOKEN : /* IDENTIFIERS */
{
  < IDENTIFIER: <LETTER> (<LETTER>|<DIGIT>)* >
|
  < #LETTER: ["_","a"-"z","A"-"Z"] >
|
  < #DIGIT: ["0"-"9"] >
}

/** Main production. */
ASTStart Start() : {}
{
  Expression() ";"
  { return jjtThis; }
}

/** An Expression. */
void Expression() #void : {}
{
  AdditiveExpression()
}

/** An Additive Expression. */
void AdditiveExpression() #void : {}
{
  (
    MultiplicativeExpression() ( ( "+" | "-" ) MultiplicativeExpression() )*
  ) #Add(>1)
}

/** A Multiplicative Expression. */
void MultiplicativeExpression() #void : {}
{
  (
    UnaryExpression() ( ( "*" | "/" | "%" ) UnaryExpression() )*
  ) #Mult(>1)
}

/** A Unary Expression. */
void UnaryExpression() #void : {}
{
  "(" Expression() ")" | MyID() | Integer()
}

/** An Identifier. */
void MyID() :
{
  Token t;
}
{
  t=<IDENTIFIER>
  {
    jjtThis.setName(t.image);
  }
}

/** An Integer. */
void Integer() : {}
{
  <INTEGER_LITERAL>
}

输入同样的表达式(a + b) * (c + 1);运行结果如下：

Reading from standard input...
(a + b) * (c + 1);
Start
 Mult
  Add
   Identifier: a
   Identifier: b
  Add
   Identifier: c
   Integer
Thank you.

相比上一个jjtree语法文件这里的改动并不大，我们逐一了解一下：

void Expression() #void : {}
{
  AdditiveExpression()
}

这里比之前多了个#void，如果想要禁止当前的产生式生成一个节点，可以使用这个语法。

void AdditiveExpression() #void : {}
{
  (
    MultiplicativeExpression() ( ( "+" | "-" ) MultiplicativeExpression() )*
  ) #Add(>1)
}

这个产生式表示若干个乘法表达式相加减，这里的#Add充当后缀操作符，其作用域是紧接在前面的扩展单元（这里代表前面小括号里面的表达式）。

#Add(>1)则是条件节点的写法，当且仅当条件求值为' true '时，构造当前节点及其子结点. 如果计算结果为' false '，则不构造当前节点及其子节点。如果#Add后面没有任何条件则代表#Add(true)，而#Add(>1)则是#Add(jjtree.arity() > 1)的简写，jjtree.arity()则代表和获取当前节点范围内压入节点堆栈的节点数，可以简单的理解为Add节点有没有子节点生成。jjtree的class结构我们会在后面补充。
 

void MyID() :
{
  Token t;
}
{
  t=<IDENTIFIER>
  {
    jjtThis.setName(t.image);
  }
}

这里是自定义节点的一个应用，用于将解析到的token字符作为节点名称打印出来，jjtThis.setName(t.image);代表设置当前节点的name，这里可以看下如何对SimpleNode进行拓展。

package com.github.gambo.javacc.jjtree;

/**
 * An ID.
 */
public class ASTMyID extends SimpleNode {
  private String name;

  /**
   * Constructor.
   * @param id the id
   */
  public ASTMyID(int id) {
    super(id);
  }


  /**
   * Set the name.
   * @param n the name
   */
  public void setName(String n) {
    name = n;
  }

  /**
   * {@inheritDoc}
   * @see org.javacc.examples.jjtree.eg2.SimpleNode#toString()
   */
  public String toString() {
    return "Identifier: " + name;
  }

}

对比上面节点树的打印，用法一目了然！注意自定义节点的class名称以AST作为前缀，以及我们在语法文件中对此节点的引用名称ASTxxx，xxx作为节点引用。 

上面的例子我们为了避免节点的产生在好几个产生式的后面加上了#void，实际上这样的动作是可以作为默认行为进行配置的，我们可以在文件头的options区域增加配置

NODE_DEFAULT_VOID=true

这样所有的产生式均不会产生节点，如果需要某些产生式生成节点，则在后面加上#xxx，具体代码如下：

options {
  MULTI=true;
  NODE_DEFAULT_VOID=true;
}

PARSER_BEGIN(Eg)
package com.github.gambo.javacc.jjtree;
/** An Arithmetic Grammar. */
public class Eg {
  /** Main entry point. */
  public static void main(String args[]) {
    System.out.println("Reading from standard input...");
    Eg t = new Eg(System.in);
    try {
      ASTStart n = t.Start();
      n.dump("");
      System.out.println("Thank you.");
    } catch (Exception e) {
      System.out.println("Oops.");
      System.out.println(e.getMessage());
      e.printStackTrace();
    }
  }
}

PARSER_END(Eg)


SKIP :
{
  " "
| "\t"
| "\n"
| "\r"
| <"//" (~["\n","\r"])* ("\n"|"\r"|"\r\n")>
| <"/*" (~["*"])* "*" (~["/"] (~["*"])* "*")* "/">
}

TOKEN : /* LITERALS */
{
  < INTEGER_LITERAL:
        <DECIMAL_LITERAL> (["l","L"])?
      | <HEX_LITERAL> (["l","L"])?
      | <OCTAL_LITERAL> (["l","L"])?
  >
|
  < #DECIMAL_LITERAL: ["1"-"9"] (["0"-"9"])* >
|
  < #HEX_LITERAL: "0" ["x","X"] (["0"-"9","a"-"f","A"-"F"])+ >
|
  < #OCTAL_LITERAL: "0" (["0"-"7"])* >
}

TOKEN : /* IDENTIFIERS */
{
  < IDENTIFIER: <LETTER> (<LETTER>|<DIGIT>)* >
|
  < #LETTER: ["_","a"-"z","A"-"Z"] >
|
  < #DIGIT: ["0"-"9"] >
}

/** Main production. */
ASTStart Start() #Start : {}
{
  Expression() ";"
  { return jjtThis; }
}

/** An Expression. */
void Expression() : {}
{
  AdditiveExpression()
}

/** An Additive Expression. */
void AdditiveExpression() : {}
{
  (
    MultiplicativeExpression() ( ( "+" | "-" ) MultiplicativeExpression() )*
  ) #Add(>1)
}

/** A Multiplicative Expression. */
void MultiplicativeExpression() : {}
{
  (
    UnaryExpression() ( ( "*" | "/" | "%" ) UnaryExpression() )*
  ) #Mult(>1)
}

/** A Unary Expression. */
void UnaryExpression() : {}
{
  "(" Expression() ")" | Identifier() | Integer()
}

/** An Identifier. */
void Identifier() #MyID :
{
  Token t;
}
{
  t=<IDENTIFIER>
  {
    jjtThis.setName(t.image);
  }
}

/** An Integer. */
void Integer() #Integer : {}
{
  <INTEGER_LITERAL>
}

Visitor 

前面的示例中我们通过simpleNode中的dump方法来打印节点树，通过修改相关节点的toString方法来输出相应节点的名称，然而这并不是一个优雅的做法。一个好的程序设计应当是职责单一，操作分离的。对于本章的例子，不管是什么样的节点，其节点类应当更加专注于自身的业务逻辑，对于节点树的访问，应当从节点本身分离出去，由外部来进行定义。jjtree为我们提供的Visitor 则可以满足这一要求。

Visitor 模式允许开发者定义一个访问者对象，该对象可以遍历语法树中的节点并在不修改原有节点代码的情况下添加新的操作或功能。

我们对上面的代码做一些修改：

options {
  MULTI=true;
  VISITOR=true;
  NODE_DEFAULT_VOID=true;
}

PARSER_BEGIN(Eg2)
package com.github.gambo.javacc.jjtree;

/** An Arithmetic Grammar. */
public class Eg2 {

  /** Main entry point. */
  public static void main(String args[]) {
    System.out.println("Reading from standard input...");
    Eg2 t = new Eg2(System.in);
    try {
      ASTStart n = t.Start();
      Eg2Visitor v = new Eg2DumpVisitor();
      n.jjtAccept(v, null);
      System.out.println("Thank you.");
    } catch (Exception e) {
      System.out.println("Oops.");
      System.out.println(e.getMessage());
      e.printStackTrace();
    }
  }
}

PARSER_END(Eg2)


SKIP :
{
  " "
| "\t"
| "\n"
| "\r"
| <"//" (~["\n","\r"])* ("\n"|"\r"|"\r\n")>
| <"/*" (~["*"])* "*" (~["/"] (~["*"])* "*")* "/">
}

TOKEN : /* LITERALS */
{
  < INTEGER_LITERAL:
        <DECIMAL_LITERAL> (["l","L"])?
      | <HEX_LITERAL> (["l","L"])?
      | <OCTAL_LITERAL> (["l","L"])?
  >
|
  < #DECIMAL_LITERAL: ["1"-"9"] (["0"-"9"])* >
|
  < #HEX_LITERAL: "0" ["x","X"] (["0"-"9","a"-"f","A"-"F"])+ >
|
  < #OCTAL_LITERAL: "0" (["0"-"7"])* >
}

TOKEN : /* IDENTIFIERS */
{
  < IDENTIFIER: <LETTER> (<LETTER>|<DIGIT>)* >
|
  < #LETTER: ["_","a"-"z","A"-"Z"] >
|
  < #DIGIT: ["0"-"9"] >
}

/** Main production. */
ASTStart Start() #Start : {}
{
  Expression() ";"
  { return jjtThis; }
}


/** An Expression. */
void Expression() : {}
{
  AdditiveExpression()
}

/** An Additive Expression. */
void AdditiveExpression() : {}
{
  (
    MultiplicativeExpression() ( ( "+" | "-" ) MultiplicativeExpression() )*
  ) #Add(>1)
}

/** A Multiplicative Expression. */
void MultiplicativeExpression() : {}
{
  (
    UnaryExpression() ( ( "*" | "/" | "%" ) UnaryExpression() )*
  ) #Mult(>1)
}

/** A Unary Expression. */
void UnaryExpression() : {}
{
  "(" Expression() ")" | Identifier() | Integer()
}

/** An Identifier. */
void Identifier() #MyOtherID :
{
  Token t;
}
{
  t=<IDENTIFIER>
  {
    jjtThis.setName(t.image);
  }
}

/** An Integer. */
void Integer() #Integer : {}
{
  <INTEGER_LITERAL>
}

首先option区域中的VISITOR=true;代表开启访问者模式，此时JJTree将在它生成的所有节点类中插入一个' jjtAccept() '方法，并生成一个可以实现并传递给节点接受的访问者接口。我们可以观察一下生成的代码。

生成的Visitor接口如下：
 

package com.github.gambo.javacc.jjtree;

public interface Eg2Visitor
{
  public Object visit(SimpleNode node, Object data);
  public Object visit(ASTStart node, Object data);
  public Object visit(ASTAdd node, Object data);
  public Object visit(ASTMult node, Object data);
  public Object visit(ASTMyOtherID node, Object data);
  public Object visit(ASTInteger node, Object data);
}

可以看到对所有非#voild节点都生成了相应的visit方法，接下来我们看一下Visitor的实现：

package com.github.gambo.javacc.jjtree;

public class Eg2DumpVisitor implements Eg2Visitor
{
  private int indent = 0;

  private String indentString() {
    StringBuffer sb = new StringBuffer();
    for (int i = 0; i < indent; ++i) {
      sb.append(' ');
    }
    return sb.toString();
  }

  public Object visit(SimpleNode node, Object data) {
    System.out.println(indentString() + node +
                   ": acceptor not unimplemented in subclass?");
    ++indent;
    data = node.childrenAccept(this, data);
    --indent;
    return data;
  }

  public Object visit(ASTStart node, Object data) {
    System.out.println(indentString() + node);
    ++indent;
    data = node.childrenAccept(this, data);
    --indent;
    return data;
  }

  public Object visit(ASTAdd node, Object data) {
    System.out.println(indentString() + node);
    ++indent;
    data = node.childrenAccept(this, data);
    --indent;
    return data;
  }

  public Object visit(ASTMult node, Object data) {
    System.out.println(indentString() + node);
    ++indent;
    data = node.childrenAccept(this, data);
    --indent;
    return data;
  }

  public Object visit(ASTMyOtherID node, Object data) {
    System.out.println(indentString() +"Identifier:"+ node.getName());
    ++indent;
    data = node.childrenAccept(this, data);
    --indent;
    return data;
  }

  public Object visit(ASTInteger node, Object data) {
    System.out.println(indentString() + node);
    ++indent;
    data = node.childrenAccept(this, data);
    --indent;
    return data;
  }
}

/*end*/

可以看到现在的节点树打印由每个节点的visit的方法中实现 。

data = node.childrenAccept(this, data);这行代码，代表调用当前节点子节点jjAccept方法，从而触发子节点visit的方法：

  public Object jjtAccept(Eg2Visitor visitor, Object data){
    return visitor.visit(this, data);
  }

  /** Accept the visitor. **/
  public Object childrenAccept(Eg2Visitor visitor, Object data){
    if (children != null) {
      for (int i = 0; i < children.length; ++i) {
        children[i].jjtAccept(visitor, data);
      }
    }
    return data;
  }

本文的入门示例改自源码中的example，后续的章节我们会使用jjtree演示一些更加深入的案例。

文中示例代码 ：GitHub - ziyiyu/javacc-tutorial: javacc教程