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

Question

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

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

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

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

Answer 1

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

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

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