如何使用 JJTree 构建抽象语法树？

Question

构建AST和添加children到树时，有什么区别：

void NonTerminal #Nonterminal: { Token t;}
{
    t = <MULTIPLY> OtherNonTerminal() {jjtThis.value = t.image;} #Multiply
}

和：

void NonTerminal : { Token t;}
{
    t = <MULTIPLY> OtherNonTerminal() {jjtThis.value = t.image;} #Multiply(2)
}

注：

<MULTIPLY : "*">

有什么主要区别吗？它们的工作方式是否相同？

还有另一种构建此生产规则树的方法：

void NonTerminal() : { Token t; }
{
    t = <MULTIPLY> OtherNonTerminal() { jjtThis.value = t.image; } #Mult(2)
|   t = <DIVIDE> OtherNonTerminal() { jjtThis.value = t.image; } #Div(2)
|   {}
}

像这样：

void NonTerminal() #Nonterminal(2) : { Token t; }
{
    (t = <MULTIPLY> OtherNonTerminal() | t = <DIVIDE> OtherNonTerminal() | {}) {jjtThis.value = t.image;}
}

Answer 1

这个问题的答案是肯定的，有区别。

JAVACC 或 JJTREE 语法在不同的步骤中进行编译过程。

词法分析，其中收集单个字符并尝试使用 TOKEN、SPECIAL_TOKEN、MORE 和 SKIP 部分中提供的正则表达式构建标记。每次成功的词法分析后都会生成一个标记。
语法分析，其中这些标记将被安排在一个名为语法树的树中，其中包含终端节点和非终端节点，并提供 production rules。收集词法分析生成的每一个 Token，语法分析试图从中验证语法。

NON-TERMINAL Node : Indicates other production rule.

TERMINAL Node : Indicates the token or data node.

区别就在这里，

语法验证成功后，我们需要一个有用的表单来使用它。更有用的表示是树表示，我们已经将生成的语法树作为语法分析的一部分，可以对其进行修改以从中获取有用的树，这就是 JJTree 重命名和创建有用的树结构使用的地方#NODE_NAME 生产规则中的语法。

编辑如下评论

Multiply(2) 表示只有两个 Children 如果你的操作是 A*B，这才有意义，如果您正在执行 A*B*C 并使用 #Multiply(2) 那么树将像

          Multiply
        /          \
  Multiply           C
    /  \
  A     B

如果您正在执行 A*B*C 并使用#Multiply，那么树将像

   Multiply    Multiply      Multiply
      |            |             | 
      A            B             C

基本上#Multiply 和#Multiply(2) 之间的区别是 Multiply(2) 将等待生成节点的两个令牌，如果只发现一个令牌抛出异常，#Multiply 将在产生式规则匹配。

Answer 2

第一种情况

void NonTerminal #Nonterminal: { Token t;}
{
    t = <MULTIPLY>
    OtherNonTerminal() {jjtThis.value = t.image;}
    #Multiply
}

Multiply 节点将在其节点作用域内将所有压入堆栈的节点作为子节点，不包括在作用域结束之前弹出的任何节点。在这种情况下，这意味着在解析 OtherNonTerminal.

期间所有节点都被推送而不是弹出

在第二个例子中

void NonTerminal #void : { Token t;}
{
    t = <MULTIPLY>
    OtherNonTerminal() {jjtThis.value = t.image;} 
    #Multiply(2)
}

Multiply 节点将从堆栈中获取两个顶部节点作为其子节点。

所以可能是有区别的。

另一个区别是第二个示例没有指定与 Nonterminal 关联的节点。

在第一种情况下，这棵树将被推送

        Nonterminal
             |
          Multiply
              |
All nodes pushed (but not popped) during the parsing of OtherNonterminal

在第二种情况下，OtherNonterminal 的解析将执行它的操作（弹出和推送节点），然后弹出两个节点并推送这棵树

     Multiply
      |     |
  A child  Another child

对于第二个问题。之间的区别

void NonTerminal() #void : { Token t; }
{
    t = <MULTIPLY>
    OtherNonTerminal()
    { jjtThis.value = t.image; }
    #Mult(2)
|
    t = <DIVIDE>
    OtherNonTerminal()
    { jjtThis.value = t.image; }
    #Div(2)
|
    {}
}

和

void NonTerminal() #Nonterminal(2) : {
    Token t; }
{
    ( t = <MULTIPLY> OtherNonTerminal()
    | t = <DIVIDE> OtherNonTerminal()
    | {}
    )
    {jjtThis.value = t.image;}
}

是第一个匹配空序列时不建节点

在下一个标记不是 * 或 / 的情况下考虑第二种方式。你会得到

      Nonterminal
      /        \
  Some node    Some other node
  don't want   you don't want

我真的很惊讶第二个甚至通过了 Java 编译器，因为对 t 的引用可能是一个未初始化的变量。

如何使用 JJTree 构建抽象语法树？

How Do I Build an Abstract Syntax Tree with JJTree?

java

compiler-construction

parsing

javacc

abstract-syntax-tree