Ответ 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 - это абстрактное представление ввода. Обратите внимание, что в АСТ нет парен, потому что ассоциации выводятся из древовидной структуры.

ИЗМЕНИТЬ

Для более подробного объяснения см. Компиляторы и генераторы компилятора P.D. Терри стр. 23. Также см. Авторов домашняя страница для получения дополнительных элементов, таких как исходный код.

Ответ 2

Здесь объясняется деревья синтаксического анализа (конкретные деревья синтаксиса, CST) и абстрактные деревья синтаксиса (AST), в контексте построения компилятора. Они аналогичные структуры данных, но они построены по-разному и используются для разных задач.

Дерево раскроя

Деревья анализа обычно генерируются как следующий шаг после лексического анализа (который превращает исходный код в ряд токенов, которые можно рассматривать как значимые единицы, а не только последовательность символов).

Они представляют собой древовидные структуры данных, которые показывают, как вводимая строка терминалов (токенов исходного кода) была сгенерирована грамматикой соответствующего языка. Корень дерева разбора является самым общим символом грамматики - стартовым символом (например, оператором), а внутренние узлы представляют собой нетерминальные символы, которые символ начала расширяется до (может включать в себя сам стартовый символ), например выражение, утверждение, термин, вызов функции. Листы - это терминалы грамматики, фактические символы, которые отображаются как идентификаторы, ключевые слова и константы в строке ввода/ввода, например. для, 9, , если и т.д.

В то время как синтаксический анализ компилятора также выполняет различные проверки, чтобы обеспечить корректность отчетов о синтаксисе и синтаксических ошибках, можно вставить в код парсера.

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

Здесь представлено графическое представление дерева разбора для выражения 9 - 5 + 2 (обратите внимание на размещение терминалов в дереве и фактических символов из строки выражения):

Абстрактные деревья синтаксиса

АСТ представляют собой синтаксическую структуру некоторого кода. Деревья программных конструкций, таких как выражения, операторы управления потоками и т.д., Сгруппированы в операторы (внутренние узлы) и операнды (листья). Например, дерево синтаксиса для выражения i + 9 будет иметь оператор + как root, переменную i как оператор, оставшийся слева, и число 9 как правильный ребенок.

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

Обратите внимание, что сами операторы являются конструкциями программирования на данном языке и не должны быть действительными вычислительными операторами (например, + is): циклы for также будут обрабатываться таким образом. Например, у вас может быть дерево синтаксиса, такое как for [ expr, expr, expr, stmnt ] (представленное inline), где for - оператор, а элементы внутри квадратных скобок - его дочерние элементы (представляющие синтаксис C for), также составленные из операторов и т.д.

АСТ обычно генерируются компиляторами в синтаксическом анализе (синтаксическая) фаза, а также используются позже для семантического анализа, промежуточного представления, генерации кода и т.д.

Здесь графическое представление AST:

Ответ 3

AST описывает исходный код концептуально, он не должен содержать все синтаксические элементы, необходимые для синтаксического анализа некоторого исходного кода (фигурные скобки, ключевые слова, скобки и т.д.).

Дерево разбора более подробно описывает исходный код.

В АСТ node для оператора IF может содержать только трех детей:

• Состояние
• Если Case
• Else Case

Для C-подобного языка Parse Tree должно содержать узлы для ключевого слова "if", скобки, фигурные скобки.

Ответ 4

Я нашел это в Интернете, может быть, полезно:

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