Как построить абстрактное синтаксическое дерево с помощью JJTree?

Question

При создании AST и добавлении дочерних элементов в дерево, в чем разница между:

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

В первом случае

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 является потенциально неинициализированной переменной.

Answer 2

Ответ на этот вопрос: да, есть разница.

Грамматика JAVACC или JJTREE выполняет процесс компиляции в несколько этапов.

1. Лексический анализ, где собираются отдельные персонажи и пытаются создать токен с помощью регулярного выражения, приведенного в TOKEN, SPECIAL_TOKEN, MORE а также SKIP разделы. После каждого успешного Лексического анализа будет сгенерирован токен.

2. Синтаксический анализ, где эти токены будут расположены в дереве под названием Синтаксическое дерево с терминальными и нетерминальными узлами с production rules предоставлена. Собирая каждый токен, сгенерированный из лексического анализа, анализ синтаксиса пытается проверить синтаксис из него.

   Нетерминальный узел: указывает другое производственное правило.

   TERMINAL Node: указывает токен или узел данных.

А вот и разница,

3. После успешной проверки синтаксиса нам понадобилась полезная форма для ее использования. Более полезным представлением является представление дерева, у нас уже есть синтаксическое дерево, сгенерированное как часть анализа синтаксиса, которое можно изменить, чтобы извлечь из него полезное дерево, здесь JJTree входит в рисунок для переименования и создания полезной структуры дерева. Синтаксис #NODE_NAME в производственных правилах.

Отредактируйте комментарий, как показано ниже

Умножение (2) указывает только на двух дочерних элементов. Это имеет смысл, если ваша операция 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 будет генерировать узлы по мере того, как производственное правило будет найдено.