Путаница по поводу абстрактного форматирования объявления функций AST
Я работаю над реализацией языка программирования в C ++, я перехожу к стадии генерации AST.
Я хотел бы использовать трехэтапную процедуру:
- Распознать тип заявления;
- Отделите токены от выражения в lvalues rvalues и узлах как временные и локальные AST;
- Дизайн и добавить его в глобальный AST.
Вот что это даст для объявления переменной, например:
var MyVar : integer = 8 + 2;
Временная форма (rvalues / node / lvalues):
left:
-left:
"MyVar"-node:
":"-right:
"integer"node:
"="right:
-left:
"8"-node:
"+"-right:
"2"Представлен как классический АСТ:
"="/ \
/ \
/ \
":" "+"/ \ / \
/ \ "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: я довольно новичок в области абстрактного синтаксического анализа и деревьев, но я прочитал много документов и учебников по этой теме.
Решение
Во-первых, я бы порекомендовал изучить bison / flex для C ++ или другого генератора синтаксических анализаторов, поскольку вы можете легче сгруппировать операторы в древовидную структуру.
Для вашей проблемы с параметром функции AST — это не просто левый правый узел. Вы можете иметь несколько (> 2) ветвей под узлом и думать об этих ветвях как об их грамматических выражениях вместо буквенных символов. Вот где помогает лексер, поскольку вы можете абстрагировать символы в токены, тогда парсер будет абстрагировать токены в грамматические структуры. В общем что-нибудь вроде a : integer должны быть абстрагированы в грамматическую структуру, возможно, в то, что называется типизированным объявлением.
Так func add(a : integer, b : integer) : integer; действительно
func identifier(params) : returnType
и узлы в AST могут отслеживать конкретную информацию.
А именно, ваш AST должен использовать «символы» или «жетоны», но вместо этого внутренние узлы должны быть абстракциями грамматических конструкций языка. Специально для списка параметров я бы рекомендовал его как список разделенных запятыми типизированных объявлений, тогда у узла params будет список узлов объявлений для дочерних элементов.
Также из вашего заявления о добавлении оператора в глобальное дерево может быть более полезно думать о нем как о добавлении оператора в глобальный список AST.
В любом случае странный ответ, надеюсь, это помогло.
Другие решения
Других решений пока нет …