Какая польза от абстрактных синтаксических деревьев?

Question

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

Почему полезны AST?

Answer 1

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

Затем логикой можно манипулировать более согласованным и удобным способом из POV бэкэнда, который может (и для всего, кроме Лиспса;) сильно отличаться от того, как мы пишем конкретный синтаксис.

Answer 2

Основным преимуществом использования AST является то, что вы отделяете логику анализа и проверки от части реализации. Интерпретаторы, реализованные как AST, действительно легче понять и поддерживать. Если у вас есть проблема с анализом какого-то странного синтаксиса, вы смотрите на анализатор AST, если кусочки кода не дают ожидаемых результатов, чем вы смотрите на код, который интерпретирует AST.

Другим большим преимуществом является то, что синтаксис требует «упреждающего просмотра», например, если ваш синтаксис позволяет использовать подпрограмму до ее определения, то тривиально проверить существование подпрограммы при использовании AST - это гораздо сложнее с анализатором «на лету».

Answer 3

Вам нужны «деревья синтаксиса» для представления структуры большинства языков программирования, чтобы выполнить анализ или преобразование документов, содержащих текст на языке программирования. (Вы можете увидеть некоторые причудливые примеры этого в моей биографии).

Является ли это дерево абстрактным (AST) или конкретным (CST) - вопрос вкуса, удобства и инженерного пота. Термин CST специально используется для описания деривационного дерева разбора, когда грамматика используется для деконструкции исходного кода; обычно он содержит элементы дерева для множества конкретных синтаксисов, таких как точки с запятой в выражении оператора. AST означает «что-то более простое, чем CST», например, оставляя узлы дерева точек с запятой, потому что они не сильно влияют на анализ программы, и, таким образом, написание анализаторов, обрабатывающих AST, требует меньше концептуальных и инженерных усилий, чем написание того же анализатора на CST. Лучший способ понять это - осознать, что AST обычно является изоморфным эквивалентом CST, то есть вы должны иметь возможность регенерировать CST из него. Если вы хотите преобразовать исходный текст и восстановить его, то CST часто является лучшим выбором, поскольку он теряет меньше информации из исходной программы (и мой модный пример использует этот подход).

Я думаю, вы найдете SO SO обсуждение абстрактных и конкретных синтаксических деревьев довольно полезным.

Answer 4

Как правило, вы собираетесь анализировать код в какой-либо форме AST, это может быть более или менее формальной моделью. Итак, я думаю, что Кирк Волл понял, что его комментарий выше заключается в том, что когда вы анализируете язык, вы очень часто используете синтаксический анализатор для создания некоторой модели данных необработанного содержимого того, что вы читаете, обычно организованного в виде дерева , Таким образом, по этому определению AST трудно избежать, если вы не делаете очень простой переводчик.

Я часто использую ANTLR для разбора сложных языков, и в этом контексте есть немного более конкретное значение AST. ANTLR имеет удобный способ генерирования AST в грамматике синтаксического анализатора, используя довольно простые действия. Затем вы пишете, как правило, гораздо более простой синтаксический анализатор для этого AST, с которым вы можете работать как гораздо более простая версия языка, который вы обрабатываете. Является ли дополнительная работа по созданию двух синтаксических анализаторов чистым преимуществом, зависит от сложности языка и того, что вы планируете делать с ним после его анализа.

Хорошая книга на эту тему, на которую вы, возможно, захотите взглянуть, - «Шаблоны языковой реализации», автор Терренс Парр, автор ANTLR. Он обращается к этой теме довольно тщательно. Тем не менее, я не получал AST, пока не начал их использовать, так что (как обычно) - лучший способ их понять.