В чем разница между деревьями разбора и абстрактными синтаксическими деревьями? - PullRequest
Новая
       78

В чем разница между деревьями разбора и абстрактными синтаксическими деревьями?

45 голосов
/ 11 мая 2011

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

Я искал в интернете и обнаружил, что деревья синтаксического анализа также называются конкретными синтаксическими деревьями (CST).

Ответы [ 5 ]

29 голосов
/ 16 апреля 2012

Это основано на грамматике выражений Терренса Парр.

Грамматика для этого примера: 

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(); } ;

Input 

x=1
y=2
3*(x+y)

Дерево разбора

Дерево разбора является конкретным представлением входных данных. Дерево разбора сохраняет всю информацию ввода. Пустые поля представляют пробелы, то есть конец строки.

Parse Tree

АСТ

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

AST

РЕДАКТИРОВАТЬ

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

14 голосов
/ 13 октября 2014

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

Деревья разбора

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

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

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

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

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

enter image description here

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

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

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

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

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

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

enter image description here

5 голосов
/ 11 мая 2011

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

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

В AST узел для оператора IF может содержать только трех дочерних элементов:

  • Состояние
  • Если дело
  • Остальное дело

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

3 голосов
/ 30 января 2015

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

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

0 голосов
/ 19 мая 2018

Википедия говорит

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

В ответе на Quora говорится

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

Объединяя два приведенных выше определения,

Abstract Syntax Tree логически описывает дерево разбора. Он не должен содержать все синтаксические конструкции, необходимые для анализа некоторого исходного кода (пробелы, скобки, ключевые слова, скобки и т. Д.). Вот почему Parse Tree также называется Concrete Syntax Tree, а AST называется Syntax Tree. Выход синтаксического анализатора, таким образом, фактически является синтаксическим деревом.

...