#compiler-construction #abstract-syntax-tree #parse-tree
#построение компилятора #терминология #теория компилятора #абстрактное синтаксическое дерево #дерево синтаксического анализа
Вопрос:
Генерируются ли они на разных этапах процесса компиляции? Или это просто разные названия одного и того же?
Комментарии:
1. Дерево синтаксического анализа — это результат вашей грамматики с ее артефактами (вы можете написать бесконечное количество грамматик для одного и того же языка), AST максимально приближает дерево синтаксического анализа к языку. Несколько грамматик для одного и того же языка дадут разные деревья синтаксического анализа, но должны приводить к одному и тому же AST. (вы также можете свести разные сценарии (разные деревья синтаксического анализа из одной и той же грамматики) к одному и тому же AST)
Ответ №1:
Это основано на грамматике 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 — это абстрактное представление входных данных. Обратите внимание, что в AST отсутствуют скобки, поскольку ассоциации выводятся из древовидной структуры.
Для более подробного объяснения см. Компиляторы и генераторы компиляторов, стр. 23
или Абстрактные синтаксические деревья на стр. 21 в Синтаксисе и семантике языков программирования
Комментарии:
1. Как вы выводите AST из дерева синтаксического анализа? Каков метод упрощения дерева синтаксического анализа в AST?
2. Не существует конкретного алгоритма для получения AST из дерева синтаксического анализа. То, что входит в AST, является скорее личным предпочтением, но должно содержать достаточно информации для выполнения задачи. Я исключил скобки из AST с помощью ANTLR ! оператор в грамматике, поскольку они не нужны, но по умолчанию ANTLR включил бы их. Я думаю, что дерево синтаксического анализа предоставляет вам все, нужно вам это или нет, а AST — это абсолютный минимум. Помните, что вы будете часто обходить деревья, поэтому размер имеет значение.
3. Вы имеете в виду, как CST (конкретное синтаксическое дерево) против AST (абстрактное синтаксическое дерево)?
4. Семантические действия / правила, встроенные в синтаксические файлы синтаксического анализатора или генератора синтаксических анализаторов, являются обычным способом семантического анализа и создания AST, в то время как дерево синтаксического анализа редко, если вообще когда-либо, создается или используется пользовательским кодом, за исключением, возможно, проверки корректности синтаксического анализатора.
5. Представляющий интерес: абстрактный семантический граф
Ответ №2:
Вот объяснение деревьев синтаксического анализа (конкретных синтаксических деревьев, CSTS) и абстрактных синтаксических деревьев (ASTS) в контексте построения компилятора. Это похожие структуры данных, но они сконструированы по-разному и используются для разных задач.
Деревья синтаксического анализа
Деревья синтаксического анализа обычно генерируются как следующий шаг после лексического анализа (который превращает исходный код в серию токенов, которые можно рассматривать как значимые единицы, в отличие от просто последовательности символов).
Они представляют собой древовидные структуры данных, которые показывают, как входная строка терминалов (токены исходного кода) была сгенерирована грамматикой рассматриваемого языка. Корень дерева синтаксического анализа — это самый общий символ грамматики — начальный символ (например, оператор), а внутренние узлы представляют собой нетерминальные символы, до которых расширяется начальный символ (может включать сам начальный символ), такие как выражение, оператор, термин, вызов функции. Листья — это терминалы грамматики, фактические символы, которые отображаются как идентификаторы, ключевые слова и константы в языке / строке ввода, например, for, 9, if и т.д.
Во время синтаксического анализа компилятор также выполняет различные проверки для обеспечения правильности синтаксиса — и отчеты о синтаксических ошибках могут быть встроены в код синтаксического анализа.
Они могут использоваться для синтаксически ориентированного перевода с помощью синтаксически ориентированных определений или схем перевода, для простых задач, таких как преобразование инфиксного выражения в постфиксное.
Вот графическое представление дерева синтаксического анализа для выражения 9 - 5 2 (обратите внимание на размещение терминалов в дереве и фактические символы из строки выражения):
Абстрактные синтаксические деревья
ASTS представляют синтаксическую структуру некоторого кода. Деревья программных конструкций, таких как выражения, инструкции управления потоком и т.д., сгруппированы в операторы (внутренние узлы) и операнды (листья). Например, синтаксическое дерево для выражения i 9 будет иметь оператор в качестве корневого, переменную i в качестве левого дочернего элемента оператора и число 9 в качестве правого дочернего элемента.
Разница здесь в том, что нетерминалы и терминалы не играют роли, поскольку ASTS имеют дело не с грамматиками и генерацией строк, а с программными конструкциями, и, таким образом, они представляют отношения между такими конструкциями, а не способы, которыми они генерируются грамматикой.
Обратите внимание, что сами операторы являются программными конструкциями на данном языке и не обязательно должны быть фактическими вычислительными операторами (такими как is): for циклы также будут обрабатываться таким образом. Например, у вас может быть такое синтаксическое дерево, как for [ expr, expr, expr, stmnt ] (представленное встроенным), где for является оператором, а элементы внутри квадратных скобок являются его дочерними элементами (представляющими for синтаксис C) — также состоящими из операторов и т.д.
ASTS обычно генерируются компиляторами также на этапе синтаксического анализа (parsing) и используются позже для семантического анализа, промежуточного представления, генерации кода и т.д.
Вот графическое представление AST:
Комментарии:
1. Хотелось бы, чтобы ваш ответ был принятым. Это намного более подробно и лучше объясняется.
2. @Salil спасибо!:) Я также писал об этих вещах в своем блоге: flowing.systems/tag /mcd
3. Есть ли какой-либо автор, который впервые определил дерево синтаксического анализа?
Ответ №3:
Насколько я понимаю, AST больше фокусируется на абстрактных связях между компонентами исходного кода, в то время как дерево синтаксического анализа фокусируется на фактической реализации грамматики, используемой языком, включая придирчивые детали. Это определенно не одно и то же, поскольку другой термин для «дерева синтаксического анализа» — «конкретное синтаксическое дерево».
Комментарии:
1. Ссылка не указывает на правильную информацию
2. Спасибо @HrishikeshDevhare. Я только что удалил это, поскольку больше нет смысла его хранить.
Ответ №4:
В книге по DSL Мартина Фаулера это прекрасно объясняется. AST содержит только все «полезные» элементы, которые будут использоваться для дальнейшей обработки, в то время как дерево синтаксического анализа содержит все артефакты (пробелы, скобки, …) из исходного документа, который вы анализируете
Ответ №5:
AST описывает исходный код концептуально, ему не обязательно содержать все синтаксические элементы, необходимые для анализа некоторого исходного кода (фигурные скобки, ключевые слова, скобки и т.д.).
Дерево синтаксического анализа более точно представляет исходный код.
В AST узел для оператора IF может содержать только три дочерних элемента:
- Условие
- В случае
- Другой случай
Для C-подобного языка дерево синтаксического анализа должно было бы содержать узлы для ключевого слова ‘if’, круглых скобок, а также.
Ответ №6:
В Википедии говорится
Деревья синтаксического анализа конкретно отражают синтаксис языка ввода, что отличает их от абстрактных синтаксических деревьев, используемых в компьютерном программировании.
В ответе на Quora говорится
Дерево синтаксического анализа — это запись правил (и токенов), используемых для сопоставления некоторого входного текста, тогда как синтаксическое дерево записывает структуру входных данных и нечувствительно к грамматике, которая его создала.
Объединение двух приведенных выше определений,
Abstract Syntax Tree Логически описывает дерево синтаксического анализа. Ему не обязательно содержать все синтаксические конструкции, необходимые для анализа некоторого исходного кода (пробелы, фигурные скобки, ключевые слова, скобки и т.д.). Вот почему Parse Tree также вызывается Concrete Syntax Tree , когда вызывается AST Syntax Tree . Таким образом, результатом синтаксического анализатора фактически является синтаксическое дерево.
Ответ №7:
Возьмем возраст присвоения pascal: = 42;
Синтаксическое дерево будет выглядеть точно так же, как исходный код. Ниже я заключаю узлы в квадратные скобки. [Возраст][:=][42][;]
Абстрактное дерево выглядело бы следующим образом [=][Возраст][42]
Назначение становится узлом с 2 элементами, возрастом и 42. Идея в том, что вы можете выполнить назначение.
Также обратите внимание, что синтаксис pascal исчезает. Таким образом, возможно, чтобы несколько языков генерировали один и тот же AST. Это полезно для межъязыковых скриптовых движков.
Ответ №8:
В дереве синтаксического анализа внутренние узлы не являются терминальными, листья являются терминальными. В синтаксическом дереве внутренними узлами являются операторы, листьями — операнды.