Путаница по поводу абстрактного форматирования объявления функций AST

Работаю над реализацией языка программирования на C++, подхожу к стадии генерации AST.

Я хотел бы использовать трехэтапную процедуру:

  1. Распознать тип утверждения;
  2. Отделите токены от выражения в lvalues ​​rvalues ​​и узлах как временные и локальные AST;
  3. Разработайте и добавьте его в глобальный AST.

Вот что это даст, например, для объявления переменной:

var MyVar : integer = 8 + 2;

Временная форма (rvalues/node/lvalues):

left:
    -left:
         "MyVar"
    -node:
         ":"
    -right:
         "integer"
node:
     "="
right:
    -left:
         "8"
    -node:
         "+"
    -right:
         "2"

Представлен в виде классического AST:

           "="
          /   \
         /     \
        /       \
      ":"       "+"
     /   \     /   \
    /     \  "8"   "2"
   /       \
"MyVar" "integer"

Затем временное дерево добавляется к глобальному дереву с указанием типа объявления:

    [EXP]
      |
   VarDecl
      |
   { ... }

Это работает для всего, кроме объявлений функций и вызовов функций:

func add(a : integer, b : integer) : integer;

add(8, 2);

Действительно, для этого типа выражений нет узлов, чтобы отличить lvalue от rvalue. Я также понятия не имею, как представить параметры функции. Я думал о чем-то вроде этого:

left:
    "add"
    params:
        [
         -left:
              "a"
         -node:
              ":"
         -right:
               "integer"
        ]
        [
         -left:
              "b"
         -node:
              ":"
         -right:
               "integer"
        ]
node:
    ":"
right:
    "integer"

То же самое для вызова:

left:
    "add"
params:
    [
      "8"
    ]
    [
     "2"
    ]

Но я чувствую, что логики не останется, если я это сделаю.

Итак, мне было интересно, нет ли способа сделать то, что было близко к моему, чтобы улучшить его, или если мое нужно было полностью пересмотреть.

PS: я новичок в области абстрактного синтаксического анализа и деревьев, но я прочитал много документов и руководств по этой теме.


c++ abstract-syntax-tree compiler-construction language-theory
person Foxy    schedule 13.08.2018    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Во-первых, я бы порекомендовал изучить bison/flex для C++ или другой генератор синтаксических анализаторов, так как вы можете легче группировать операторы в древовидную структуру.

Для вашей проблемы с функциональными параметрами AST — это не просто правый узел слева. Вы можете иметь несколько (> 2) ветвей под узлом и думать об этих ветвях как о своих грамматических выражениях, а не о буквальных символах. Здесь помогает лексер, поскольку вы можете абстрагировать символы в токены, а синтаксический анализатор абстрагирует токены в грамматические структуры. В общем, что-то вроде a : integer должно быть абстрагировано в структуру грамматики, возможно, что-то, что называется типизированным объявлением.

Так что func add(a : integer, b : integer) : integer; действительно

func identifier(params) : returnType

и узлы в AST могут отслеживать конкретную информацию.

А именно, ваш AST должен использовать «символы» или «токены», но вместо этого внутренние узлы должны быть абстракциями грамматических конструкций языка. В частности, для списка параметров я бы рекомендовал его как список типизированных объявлений, разделенных запятыми, тогда узел params будет иметь список узлов объявлений для дочерних элементов.

Кроме того, из вашего заявления о добавлении оператора в глобальное дерево может быть полезнее думать об этом как о добавлении оператора в глобальный список AST.

В любом случае, странный ответ, надеюсь, помог.

person Garrigan Stafford    schedule 13.08.2018
comment
Это мне очень помогло, спасибо. Так что, если я правильно понимаю, на узел может быть не более двух дочерних элементов. Из чего следует, что тоже может быть только один (но не 0?). Чтобы ответить на ваш вопрос, мой лексер возвращает токены с лексической идентичностью (число, объявление переменной, строка, ...), что позволит лучше анализировать. Я лучше понял, как использовать параметр functions в качестве токена в AST; Спасибо за все! - person Foxy; 13.08.2018
comment
Детей может быть много, AST зависит от структуры грамматики. Рассмотрим тернарный оператор x = (y==2) ? 2 : 3. У нас есть верхний узел TernaryStaement с дочерними элементами dst(Var), condition(expr), trueResult(expr), falseResult(Expr) - person Garrigan Stafford; 13.08.2018
comment
Да, я об этом не подумал. Придется еще поработать над такой моделью, спасибо. - person Foxy; 13.08.2018