Вам не нужно создавать узел для каждого сокращения, а узлы, которые вы создаете, не должны включать каждый уменьшаемый символ. Также нет необходимости, чтобы сокращенные символы отображались в том же порядке, что и синтаксический анализ.
Во многих случаях AST представляет собой упрощение полного дерева синтаксического анализа, соответствующее приведенному выше.
Простой пример для грамматики выражений с использованием генератора синтаксического анализатора, подобного yacc:
expr: term { $$ = $1; /* see below */ }
| expr '+' term { $$ = new_sum_node($1, $3); }
term: factor { $$ = $1; /* see below */ }
| term '*' factor { $$ = new_product_node($1, $3); }
factor: '(' expr ')' { $$ = $2; /* See below */ }
| ID { $$ = new_variable_node($1); }
| NUMBER { $$ = new_literal_node($1); }
AST строится как семантическое значение нетерминалов. Ожидается, что функции new_*_node вернут вновь выделенный узел указанного типа. (Здесь мы предполагаем, что существует какой-то механизм для определения типа узла по указателю. Например, можно было бы использовать подтипы и виртуальные функции.)
В Yacc (и подобных генераторах синтаксических анализаторов) каждый символ (терминальный или нетерминальный) имеет связанное «значение», и у каждой продукции есть связанное действие, которое выполняется при сокращении продукции. Действие по производству может присваивать «стоимость» нетерминала, подлежащего сокращению. Действие может использовать «значения» компонентов правой части, поскольку каждый из них является либо терминалом (значение которого было установлено сканером), либо нетерминалом, который уже был уменьшен. По сути, это S-атрибутивная грамматика.
Некоторые из вышеперечисленных снижений вообще не проявляются в AST. В частности, единичные сокращения (expr:term и term:factor) просто проходят через AST для правой части. Точно так же сокращение скобок term:'(' expr ')' просто проходит через AST для expr, в результате чего скобки фактически исчезают из AST. (Это верно не для всех языков; в некоторых языках явно избыточные круглые скобки на самом деле влияют на семантику, и вам нужно создать узел AST, чтобы записать этот факт.)
В Yacc $$ = $1 является действием сокращения по умолчанию, если никакое действие не указано, и, поскольку большинство сокращений единиц исключаются из AST, они обычно отображаются без действий сокращения. Я сделал их явными в дидактических целях; на практике этого делать не следует.
person
rici
schedule
27.05.2015
