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上写一个小的系列，谢谢！

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

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

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