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

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

Что-то мне не хватает в семантическом анализаторе, или разница между AST и CST несколько искусственная?

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

Однако конкретная грамматика и дерево имеют много вещей, которые необходимы для однозначного анализа исходного текста, но не влияют на фактическое значение. Например, для реализации приоритета операторов ваш CFG обычно имеет несколько уровней компонентов выражения (термин, фактор и т. Д.), С операторами, соединяющими их на разных уровнях (вы добавляете термины, чтобы получить выражения, термины состоят из факторов, необязательно кратных , и т.д.). Однако для реальной интерпретации или компиляции языка вам это не нужно; вам просто нужны узлы Expression, у которых есть операторы и операнды. Абстрактное синтаксическое дерево является результатом упрощения конкретного синтаксического дерева до того, что действительно необходимо для представления смысла программы. Это дерево имеет гораздо более простое определение и поэтому его легче обрабатывать на более поздних этапах выполнения.

Обычно вам не нужно создавать конкретное синтаксическое дерево. Подпрограммы действий в вашей грамматике YACC (или Antlr, или Menhir, или что-то еще ...) могут напрямую строить абстрактное синтаксическое дерево, поэтому конкретное синтаксическое дерево существует только как концептуальный объект, представляющий структуру синтаксического анализа вашего исходного текста.

Синтаксис конкретное дерево соответствует тому , что грамматика правила говорят синтаксис. Назначение абстрактного синтаксического дерева состоит в том, чтобы иметь «простое» представление того, что важно в «синтаксическом дереве».

Реальная ценность в АСТ ИМХО в том, что она меньше чем CST, и поэтому требует меньше времени для обработки. (Вы можете сказать, кого это волнует? Но я работаю с инструментом, в котором у нас одновременно живут десятки миллионов узлов!).

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

Но наличие таких AST создает проблему, которой не было: они не соответствуют грамматике, и теперь вы должны мысленно отслеживать их оба. И когда есть 1500 узлов AST для грамматики 3500 правил, это имеет большое значение. И если грамматика будет развиваться (а они всегда!), Теперь у вас есть два гигантских набора вещей, которые нужно синхронизировать.

Другое решение - позволить парсеру просто создавать для вас узлы CST и просто использовать их. Это огромное преимущество при построении грамматик: нет необходимости изобретать 1500 специальных узлов AST для моделирования 3500 грамматических правил. Только представьте, что дерево изоморфно грамматике. С точки зрения инженера-грамматика это совершенно безмозглый процесс, что позволяет ему сосредоточиться на правильной грамматике и взламывать ее сколько душе угодно. Возможно, вам придется написать больше правил для посетителей узла, но этим можно управлять. Подробнее об этом позже.

Что мы делаем с DMS Software Reengineering Toolkit, так это автоматически создаем CST на основе результатов процесса синтаксического анализа (GLR). Затем DMS автоматически создает "сжатый" CST из соображений экономии места, удаляя терминалы, не несущие значений (ключевые слова, знаки препинания), семантически бесполезные унарные продукты и формируя списки для пар грамматических правил, которые имеют список вроде:

    L = e ;
    L = L e ;
    L2 = e2 ;
    L2 = L2  ','  e2 ;

и самые разнообразные вариации таких форм. Вы думаете о правилах грамматики и виртуальном CST; инструмент работает со сжатым представлением. Легко для вашего мозга, быстрее / меньше во время выполнения.

Примечательно, что сжатый CST, созданный таким образом, очень похож на AST, который вы, возможно, создали вручную (см. Ссылку в конце примеров). В частности, сжатый CST не содержит узлов с конкретным синтаксисом. Есть небольшие неудобства: например, хотя конкретные узлы для '(' и ')', классически встречающиеся в подграмматиках выражений, не находятся в дереве, «узел скобок» действительно появляется в сжатом CST и требует обработки. У настоящего AST этого не было бы. Похоже, что это довольно небольшая цена за удобство, когда вообще не нужно указывать конструкцию 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 - это абстрактное представление ввода. Обратите внимание, что парные скобки отсутствуют в AST, поскольку ассоциации выводятся из древовидной структуры.

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

Для более подробного объяснения см. Компиляторы и генераторы компиляторов стр. 23

Это сообщение в блоге может быть полезным.

Мне кажется, что AST «отбрасывает» много промежуточной грамматической / структурной информации, которая не способствовала бы семантике. Например, вас не волнует, что 3 - это атом, это термин, это фактор, это .... Вам просто важно, чтобы это было, 3когда вы реализуете выражение возведения в степень или что-то еще.

Синтаксическое дерево бетона следует правилам грамматики языка. В грамматике "списки выражений" обычно определяются двумя правилами.

• список_выражений может быть: выражение
• список_выражений может быть: выражение, список_выражений

Буквальное соблюдение этих двух правил придает форму гребешка любому списку выражений, который появляется в программе.

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

Просто AST содержит только семантику кода, дерево синтаксического анализа / CST также включает информацию о том, как именно был написан код.

Конкретное дерево синтаксиса содержит всю информацию, такую ​​как лишние круглые скобки, пробелы и комментарии, абстрактное дерево синтаксиса абстрагируется от этой информации.

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)*

Теперь, когда вы думаете о нисходящем синтаксическом анализе, второй член вводит ПЕРВЫЙ / ПЕРВЫЙ конфликт между mul_rule и div_rule. чем синтаксический анализатор LL (1) не может справиться. Первая форма правила была лево-факторизованной версией второй, которая эффективно устраняла структуру. Вы должны заплатить приз за использование LL (1) здесь.

Таким образом, AST - это специальное дополнение, используемое для исправления недостатков грамматик и синтаксических анализаторов. Преобразование CST -> AST - это рефакторинг. Никого не беспокоит, когда в синтаксическом дереве хранится дополнительная запятая или двоеточие. Напротив, некоторые авторы модернизируют их в AST, потому что им нравится использовать AST для выполнения рефакторинга вместо одновременного обслуживания различных деревьев или написания дополнительного механизма вывода. Программисты ленивы по уважительным причинам. Фактически, они хранят информацию о строках и столбцах, собранную с помощью лексического анализа в AST, для сообщения об ошибках. Действительно, очень абстрактно.

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

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

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

Дополнительные объяснения можно найти по этой ссылке: http://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees#id6