jjTree解析

这篇文章可以算是这篇小型桌面计算器的实现(javacc) 的续。

 

可以这么说，使用javacc作分析器生成器，如果没有用到jjTree,那么就是对语义分析 的过程理解不够深入。如果用到了jjTree而且用好了，那么对编译原理，BNF等的理解才算是比较到位了。

jjTree中最重要的概念是Node接口,所有的非终结符都可以规约 为一个节点。这个节点一般来讲是实现了Node接口的节点类
其中主要有这样几个方法：

……
  /** This method tells the node to add its argument to the node's
    list of children.  */
  public void jjtAddChild(Node n, int i);

  /** 返回孩子节点，下标从0开始，从左到右 */
  public Node jjtGetChild(int i);

  /** 返回字节点个数 */
  int jjtGetNumChildren();

……

 

在本文所举的例子中，每个节点还要实现这样一个接口中声明的方法：

void interpret()

这个方法中为每个节点具体的计算过程。

 

jjTree处理的脚本(jjTree规则列表)以jjt结尾，这个文件通过jjtree工具可以生成.jj文件，然后用javacc编译.jj文件即可生成分析器生成器的java代码，然后于一些辅助解析的类进行编译，从而最终完成整个脚本引擎。

jjTree有什么用？
这个是最核心的问题了，我们都知道jjTree的作用是为了将终结符 通过规则规约 成非终结符节点 。但是，规约的目的又是什么呢？其实，如果你的目标是简单的行解析器的话，根本不需要jjTree。但是，如果需要做一些比较有规模的脚本解析器，比如支持if,while等代码块的话，就需要解析器将这些临时的状态记录下来，那就必须用到jjTree了。

加入了语法树 之后，解析器就需要做出一些修改了，比如需要加入全局的符号表，堆栈等数据结构，以方便规约出非终结符后再做动作时可以取出这些数据。当然，如果你的脚本引擎支持IO的话，这些全局的流描述符也应该和符号表，堆栈放在一起，比如一个单独的类中。

涉及到使用jjTree的项目，即使是演示目的的，一般也比较大，所以，这篇文章中给出的都是一些片段，如果需要，我可以在blog中做一个小系列来说。

比如，看一个例子：

/** Conditional or expression. */
void ConditionalOrExpression() #void :
{}
{
  ConditionalAndExpression()
  ( "||" ConditionalAndExpression() #OrNode(2) )*
}

 

上边这段中 #void意思为当遇到ConditionalOrExpression规则时，不生成节点(不规约),而#OrNode(2)则表示如果发现有恰好2个ContionalAndExpression()规则，则规约到一个OrNode节点(需要在外部写一个ASTOrNode类)。

而在ASTOrNode类中，会有下面的动作定义

  public void interpret()
  {
     jjtGetChild(0).interpret();

     if (((Boolean)stack[top]).booleanValue())
     {
        stack[top] = new Boolean(true);
        return;
     }

     jjtGetChild(1).interpret();
     stack[--top] = new Boolean(((Boolean)stack[top]).booleanValue() ||
                                ((Boolean)stack[top + 1]).booleanValue());
  }

 

在语法解析时，当规约出非终结符后，设置ASTOrNode父类的children的数组，然后在ASTOrNode先取出这个数组中的第一个Node进行
递归解析，完成后取出第二个Node进行解析，最后，将这两个解析后的结果进行bool的或运算。整个过程很自然，计算过程放在外部的单独
的类中进行。

再看一个例子：

/** A block. */
void Block() :
{}
{
  "{" ( Statement() )* "}"
}

 

用花括号括起来的一些代码表示一个块，怎么解析这个快呢？在ASTBlock中，有这样的运算过程：

  public void interpret()
  {
     int i, k = jjtGetNumChildren();//取出代码块中的代码条数

     for (i = 0; i < k; i++)
        jjtGetChild(i).interpret();//递归解析

  }

 

取出代码块中的代码条数，然后依次执行，如果遇到其他的Node，则递归调用这个Node上的interpret过程，从而执行整个代码块。

希望这篇文章可以说明jjTree的运行机制，但是由于规模所限，有些地方可能还是不太清晰。欢迎留言，我会尽快在blog上写一个小的系列，谢谢！

评论

5 楼 95222 2009-10-20  

    
大哥啊，我遇到jjtree的问题了，求解啊。就是要解析一条字符串，里面有"AND" "OR" "NOT" ，并且有括号，要求有优先级。是搜索用的。
    
我搞了好几天了，就是一点头目都没有，眼看截止日期将要到了，已经上了绝路了，如果没时间给我写个源码，指点一下也感激涕零啊。又或者写个教程普度众生啊   

4 楼 abruzzi 2009-09-15  

风之巽 写道

您好！请问关于符号表的建立有没有相关的例子啊？
最近看论文关于增量编译的，提到了复用子树的概念，就是将上一次分析得到的树中的可复用的结点直接移进解析栈，而不用一个个终结符来分析。。。 
可是javacc中关于jjtree我还是很不了解，想要建立解析表之类的也不知道怎么样开始，能帮忙指点下吗？？谢谢您！

javacc的例子中有一个interpreter，解释一个叫SPL的小语言(也就是我这篇文章给出的例子的来源)，其中用到了符号表，其实就是一个hashtable,当遇到终结符后，将键值对插入其中。其实就是一个全局的表结构，可以从中根据名称取出值来。另，不用这么客气。

3 楼 风之巽 2009-09-15  

您好！请问关于符号表的建立有没有相关的例子啊？
最近看论文关于增量编译的，提到了复用子树的概念，就是将上一次分析得到的树中的可复用的结点直接移进解析栈，而不用一个个终结符来分析。。。 
可是javacc中关于jjtree我还是很不了解，想要建立解析表之类的也不知道怎么样开始，能帮忙指点下吗？？谢谢您！

2 楼 abruzzi 2009-08-15  

952222 写道

  jjTree好难喔。跟普通的jj貌似隔了好几个量级。晕。。。看了良久，不懂。。。

呵呵，jjTree其实就是用于写脚本分析器(包含规约的语言)的时候要用到，如果只是做解析(比如配置文件之类的)就不需要了，其实主要是编译技术方面的原理，看一看语法分析和语义分析部分，应该就好理解了。

1 楼 952222 2009-08-15  

  jjTree好难喔。跟普通的jj貌似隔了好几个量级。晕。。。看了良久，不懂。。。