Как свести мое дерево синтаксического анализа к абстрактному синтаксическому дереву?

Каковы общие стратегии для сведения дерева синтаксического анализа (т. е. конкретного синтаксического дерева) к абстрактному синтаксическому дереву?

Например, у меня есть следующее грамматическое правило:

statement_list : statement
               | statement_list statement

который, если оставить его в виде дерева синтаксического анализа, будет генерировать разветвленный вывод, который выглядит как

program
        statement_list
                statement_list
                        statement
                                definition
                                        p_type
                                        assignment
                statement
                        definition
        statement
                assign
                        assignment

Если я объединим дочерние элементы каждого узла (поскольку список операторов не имеет внутреннего значения после синтаксического анализа), я могу добиться следующего

program
        definition
                p_type
                assignment
        definition
        assign
                assignment

Это сработало хорошо, однако я не знаю никаких «правил» для этого. Существуют ли определенные правила грамматики, которые я должен упростить? Это вопрос ощущения или есть более механистический процесс?


parsing abstract-syntax-tree compiler-construction grammar concrete-syntax-tree
person sdasdadas    schedule 30.07.2013    source источник
comment
Вы можете пойти на мягкий внешний вид, но это в основном много работы. Вы можете сделать это по существу механически, удалив узлы, которые можно регенерировать с помощью грамматики. См. stackoverflow.com/a/1916687/120163.   -  person Ira Baxter    schedule 16.07.2014

Ответы (1)


arrow_upward
5
arrow_downward

Дело не в "ощущении". Абстрактное синтаксическое дерево зависит от значения (семантики) того, что было проанализировано, и я думаю, что это будут правила:

  1. Удалите узлы для токенов, которые не добавляют смысла. Это промежуточные ключевые слова (например, «тогда»), разделители (например, запятая) и скобки (например, круглые скобки).
  2. Продвиньте значимые токены (например, «если»), чтобы они были родительскими для других токенов в том же правиле.

Нет единого рецепта. Это зависит от того, что означают фразы на целевом языке.

person Apalala    schedule 31.07.2013
comment
Я ценю ответ, но мне кажется, что вы сами себе противоречите. Вы говорите, что это не вопрос «ощущения», но ваши правила зависят от языка. Если бы были какие-то показатели, то я бы согласился, что это не вопрос ощущений, но в нынешнем виде это определенно так. - person sdasdadas; 01.08.2013
comment
Я в любой момент признаю, что дизайн (в частности, языковой дизайн) — это 50/50 разработка/ощущение. Это хорошо? - person Apalala; 01.08.2013
comment
Да, конечно, извините - я забыл вернуться к этому вопросу. Спасибо за помощь. - person sdasdadas; 03.08.2013