Как создать абстрактное синтаксическое дерево с помощью JJTree? - PullRequest
Новая
       59

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

0 голосов
/ 16 ноября 2018

При создании 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;}
}

Ответы [ 2 ]

0 голосов
/ 18 ноября 2018

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

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

0 голосов
/ 17 ноября 2018

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

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

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

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

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

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

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

После успешной проверки синтаксиса нам потребовалась полезная форма для его использования.Более полезным представлением является представление дерева, у нас уже есть синтаксическое дерево, сгенерированное как часть синтаксического анализа, которое можно изменить, чтобы извлечь из него полезное дерево, вот где 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 будет генерировать узлы как и когдаПравило производства получило соответствие.

...