LR (1) разобрать прямо на абстрактное синтаксическое дерево

Question

Итак, я попросил question закрыть это недавно и получил очень хороший ответ. Однако описанные выше шаги больше напоминают шаги для создания конкретного дерева синтаксиса.

Каждое уменьшение процесса разбора LR соответствует внутреннему узлу в дереве разбора. Сокращаемое правило является внутренним узлом AST , а элементы, выпадающие из стека, соответствуют дочерним элементам , что является внутренним узлом. Элемент, введенный для goto, соответствует внутреннему узлу , тогда как те, которые сдвинуты действиями сдвига, соответствуют листьям (жетонам) АСТ.

Сложив все это вместе, вы можете легко построить AST, создав новый внутренний узел каждый раз, когда выполняете сокращение, и подключайте все вместе. ~ Крис Додд

Я знаю, что дерево разбора подразумевается шагами, предпринятыми однако я не хочу, чтобы в явном виде построить дерево синтаксического разбора. И, генерируя узел, каждая редукция кажется, что это приведет ко всему дереву синтаксического анализа. Я считал, что я создаю узел только в том случае, если видится определенное состояние. Однако похоже, что это не сработает должным образом.

Answer 1

Вам не нужно построить узел на каждый сокращение, а узлы вы делаете строить не нужно включать каждый символ снижается. Также не нужно уменьшать символы в том же порядке, что и синтаксический анализ.

Во многих случаях 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); } 

АСТ построен в качестве смыслового значения не-терминалов. Ожидается, что функции new_*_node возвратят вновь выделенный узел указанного типа. (Здесь мы предполагаем, что существует некоторый механизм вывода из указателя, какой тип узла он есть. Например, можно было бы использовать подтипирование и виртуальные функции.)

В Yacc (и аналогичных синтаксических анализаторах) каждый символ (терминальный или нетерминальный) имеет ассоциированное «значение», и каждое производство имеет связанное с ним действие, которое выполняется, когда производство уменьшается. Действие для производства может присваивать значение «значение» нетерминала. Действие может использовать «значения» компонентов правой стороны, поскольку каждый из них либо является терминалом (значение которого задано сканером), либо не-терминал, который уже был уменьшен. По сути, это S-attributed grammar.

Некоторые из приведенных выше сокращений вообще не проявляются в AST. В частности, сокращения единиц (expr:term и term:factor) просто проходят через AST для правой стороны. Точно так же сокращение скобок term:'(' expr ')' просто проходит через AST для expr, в результате чего скобки эффективно исчезают из AST. (Это неверно на всех языках, на некоторых языках, по-видимому, избыточные круглые скобки действительно влияют на семантику, и вам нужно создать узел AST для записи факта.)

В Yacc, $$ = $1 является действием уменьшения по умолчанию, если никаких действий не указано, и поскольку большинство сокращений единиц исключено из AST, они обычно отображаются без действий сокращения. Я сделал их явным для дидактических целей; на практике вы не должны этого делать.