В чем разница между абстрактным синтаксическим деревом и конкретным синтаксическим деревом?
Я немного читал о том, как работают интерпретаторы / компиляторы, и одна область, в которой я запутался, - это разница между AST и CST. Насколько я понимаю, парсер создает CST, передает его семантическому анализатору, который превращает его в AST. Тем не менее, я понимаю, что семантический анализатор просто обеспечивает соблюдение правил. Я не очень понимаю, почему он будет делать какие-то изменения, чтобы сделать его абстрактным, а не конкретным.
Что-то мне не хватает в семантическом анализаторе, или разница между AST и CST несколько искусственная?
9 ответов
Конкретное синтаксическое дерево представляет исходный текст точно в разобранном виде. В целом, это соответствует контекстно-свободной грамматике, определяющей исходный язык.
Однако конкретная грамматика и дерево имеют много вещей, которые необходимы для однозначного разбора исходного текста, но не вносят вклад в реальное значение. Например, чтобы реализовать приоритет операторов, ваш CFG обычно имеет несколько уровней компонентов выражений (термин, фактор и т. Д.), Причем операторы соединяют их на разных уровнях (вы добавляете термины для получения выражений, термины состоят из факторов, которые могут быть умножены)., так далее.). Однако для интерпретации или компиляции языка это не нужно; вам просто нужны узлы Expression, которые имеют операторы и операнды. Абстрактное синтаксическое дерево является результатом упрощения конкретного синтаксического дерева до тех вещей, которые фактически необходимы для представления смысла программы. Это дерево имеет гораздо более простое определение и поэтому его легче обрабатывать на более поздних этапах выполнения.
Обычно вам не нужно создавать конкретное синтаксическое дерево. Процедуры действий в вашей грамматике YACC (или Antlr, или Menhir, или как угодно...) могут напрямую создавать абстрактное синтаксическое дерево, поэтому конкретное синтаксическое дерево существует только как концептуальная сущность, представляющая структуру синтаксического анализа вашего исходного текста.
Конкретное синтаксическое дерево соответствует синтаксису правил грамматики. Целью абстрактного синтаксического дерева является "простое" представление того, что важно в "синтаксическом дереве".
Реальное значение в AST IMHO состоит в том, что он меньше, чем CST, и, следовательно, занимает меньше времени для обработки. (Вы можете сказать, кого это волнует? Но я работаю с инструментом, в котором одновременно живут десятки миллионов узлов!).
Большинство генераторов синтаксических анализаторов, которые поддерживают создание деревьев синтаксиса, настаивают на том, чтобы вы лично указывали, как именно они создаются, исходя из предположения, что ваши узлы дерева будут "проще", чем CST (и в этом они, как правило, правы, поскольку программисты довольно ленивый). Возможно, это означает, что вам нужно кодировать меньше функций посетителя дерева, и это также ценно в том смысле, что минимизирует энергию разработки. Когда у вас есть 3500 правил (например, для COBOL), это имеет значение. И эта "более простая" сущность приводит к хорошему свойству "малости".
Но наличие таких AST создает проблему, которой не было: она не соответствует грамматике, и теперь вы должны мысленно отслеживать их оба. И когда для грамматики правил 3500 есть 1500 узлов AST, это очень важно. И если грамматика развивается (они всегда происходят!), Теперь у вас есть два гигантских набора вещей, которые нужно синхронизировать.
Другое решение - позволить парсеру просто создавать для вас узлы CST и просто использовать их. Это огромное преимущество при построении грамматик: нет необходимости изобретать 1500 специальных узлов AST для моделирования 3500 правил грамматики. Просто подумайте о том, что дерево изоморфно грамматике. С точки зрения грамматического инженера, это абсолютно бессмысленно, что позволяет ему сосредоточиться на правильной грамматике и взломать ее до глубины души. Возможно, вам нужно написать больше правил для посетителей узла, но этим можно управлять. Подробнее об этом позже.
Что мы делаем с набором инструментов реинжиниринга программного обеспечения DMS, так это автоматически создаем CST на основе результатов процесса анализа (GLR). Затем DMS автоматически создает "сжатый" CST по соображениям эффективности использования пространства за счет исключения терминалов, не несущих значения (ключевые слова, пунктуация), семантически бесполезных унарных производств и формирования списков для пар правил грамматики, которые выглядят как:
L = e ;
L = L e ;
L2 = e2 ;
L2 = L2 ',' e2 ;
и большое разнообразие вариантов таких форм. Вы думаете с точки зрения правил грамматики и виртуального CST; инструмент работает на сжатом представлении. Легко для вашего мозга, быстрее / меньше во время выполнения.
Примечательно, что сжатый CST, построенный таким образом, во многом выглядит как AST, который вы, возможно, спроектировали вручную (см. Ссылку в конце примеров). В частности, сжатый CST не несет никаких узлов, которые являются просто конкретным синтаксисом. Есть небольшие неловкости: например, в то время как конкретные узлы для '(' и ')', классически найденные в подграммах выражений, отсутствуют в дереве, "узел скобок" действительно появляется в сжатом CST и должен обрабатываться. Истинный АСТ не имел бы этого. Это кажется довольно небольшой ценой, чтобы платить за удобство, не нужно указывать конструкцию AST, никогда. И документация для дерева всегда доступна и правильна: грамматика - это документация.
Как нам избежать "лишних посетителей"? Мы не совсем, но DMS предоставляет библиотеку AST, которая обходит AST и прозрачно обрабатывает различия между CST и AST. DMS также предлагает оценщик "грамматики атрибутов" (AGE), который представляет собой метод передачи значений, вычисленных по узлам вверх и вниз по дереву; AGE решает все проблемы представления дерева, поэтому разработчик инструмента заботится только о том, чтобы эффективно писать вычисления непосредственно на самих правилах грамматики. Наконец, DMS также предоставляет шаблоны "поверхностного синтаксиса", которые позволяют фрагментам кода из грамматики использоваться для поиска определенных типов поддеревьев, не зная большинства задействованных типов узлов.
В одном из других ответов говорится, что если вы хотите создавать инструменты, способные регенерировать источник, ваш AST должен соответствовать CST. Это не совсем правильно, но гораздо проще восстановить источник, если у вас есть узлы CST. DMS генерирует большую часть prettyprinter автоматически, потому что имеет доступ к обоим:-}
Итог: AST хороши для малых, как физических, так и концептуальных. Автоматическая конструкция AST из CST обеспечивает оба варианта и позволяет избежать проблемы отслеживания двух разных наборов.
РЕДАКТИРОВАТЬ Март 2015: Ссылка на примеры CST против "AST" построен таким образом
Это основано на грамматике Expression Evaluator Терренса Парра.
Грамматика для этого примера:
grammar Expr002;
options
{
output=AST;
ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}
prog : ( stat )+ ;
stat : expr NEWLINE -> expr
| ID '=' expr NEWLINE -> ^('=' ID expr)
| NEWLINE ->
;
expr : multExpr (( '+'^ | '-'^ ) multExpr)*
;
multExpr
: atom ('*'^ atom)*
;
atom : INT
| ID
| '('! expr ')'!
;
ID : ('a'..'z' | 'A'..'Z' )+ ;
INT : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS : ( ' ' | '\t' )+ { skip(); } ;
вход
x=1
y=2
3*(x+y)
Разбор дерева
Дерево разбора является конкретным представлением входных данных. Дерево разбора сохраняет всю информацию ввода. Пустые поля представляют пробелы, то есть конец строки.
АСТ
AST является абстрактным представлением входных данных. Обратите внимание на то, что в AST нет обозначений, потому что ассоциации выводятся из древовидной структуры.
РЕДАКТИРОВАТЬ
Для более подробного объяснения см. Компиляторы и Генераторы компиляторов pg. 23
Этот пост может быть полезным.
Мне кажется, что AST "выбрасывает" много промежуточной грамматической / структурной информации, которая не способствует семантике. Например, вас не волнует, что 3 - это атом, это термин, это фактор, это... 3 когда вы реализуете выражение возведения в степень или что-то еще.
Конкретное синтаксическое дерево следует правилам грамматики языка. В грамматике "списки выражений" обычно определяются с двумя правилами
- expression_list может быть: expression
- expression_list может быть: expression, expression_list
Следуя буквально, эти два правила придают форму гребня любому списку выражений, который появляется в программе.
Абстрактное синтаксическое дерево находится в форме, удобной для дальнейших манипуляций. Это представляет вещи таким образом, который имеет смысл для кого-то, кто понимает значение программ, а не только как они написаны. Приведенный выше список выражений, который может быть списком аргументов функции, может быть удобно представлен в виде вектора выражений, поскольку для статического анализа лучше иметь явно доступное общее число выражений и иметь возможность доступа к каждому выражению по его выражению. индекс.
Проще говоря, AST содержит только семантику кода, дерево разбора /CST также включает информацию о том, как именно код был написан.
CST(конкретное синтаксическое дерево) - это древовидное представление грамматики (правила написания программы). В зависимости от архитектуры компилятора, он может использоваться анализатором для создания AST.
AST (Абстрактное синтаксическое дерево) - это древовидное представление Parsed source, созданное частью Parser компилятора. Здесь хранится информация о токенах + грамматика.
В зависимости от архитектуры вашего компилятора CST может использоваться для создания AST. Справедливо сказать, что CST развивается в AST. Или AST является более богатым CST.
Больше объяснений можно найти по этой ссылке: http://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees
Конкретное синтаксическое дерево содержит всю информацию, такую как лишние скобки, пробелы и комментарии, абстрактное синтаксическое дерево абстрагируется от этой информации.
NB: достаточно забавно, когда вы реализуете механизм рефакторинга, ваш AST снова будет содержать всю конкретную информацию, но вы будете продолжать называть его AST, потому что это стало стандартным термином в этой области (так что можно сказать, что он имеет назад потерял свое первоначальное значение).
Это разница, которая не имеет значения.
AST обычно объясняется как способ приблизить семантику выражения языка программирования, отбрасывая лексический контент. Например, в контекстно-свободной грамматике вы можете написать следующее правило EBNF
term: atom (('*' | '/') term )*
тогда как в случае AST вы используете только mul_rule и div_rule, которые выражают правильные арифметические операции.
Разве эти правила не могут быть введены в грамматику в первую очередь? Конечно. Вы можете переписать приведенное выше компактное и абстрактное правило, разбив его на более конкретные правила, используемые для имитации упомянутых узлов AST:
term: mul_rule | div_rule
mul_rule: atom ('*' term)*
div_rule: atom ('/' term)*
Теперь, когда вы думаете с точки зрения синтаксического анализа сверху вниз, второй член вводит конфликт FIRST/FIRST между mul_rule и div_rule, с чем парсер LL(1) не может иметь дело. Первая форма правила была левосторонней версией второй, которая эффективно устраняла структуру. Вы должны заплатить приз за использование LL(1) здесь.
Таким образом, AST - это специальное дополнение, используемое для исправления недостатков грамматик и синтаксических анализаторов. Преобразование CST -> AST является ходом рефакторинга. Никто никогда не беспокоился, когда в синтаксическом дереве хранится дополнительная запятая или двоеточие. Напротив, некоторые авторы модифицируют их в AST, потому что им нравится использовать AST для проведения рефакторингов вместо одновременного обслуживания различных деревьев или написания дополнительного механизма вывода. Программисты ленивы по уважительным причинам. На самом деле они хранят четную информацию о строках и столбцах, собранную лексическим анализом в AST для сообщения об ошибках. Действительно очень абстрактно.