Каково различие между Абстрактным синтаксическим деревом и Деревом синтаксического анализа?

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

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

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

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

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

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

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

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

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

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

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

конкретное синтаксическое дерево соответствует тому, что, согласно правилам грамматики, является синтаксисом. Цель абстрактного синтаксического дерева - иметь "простое" представление того, что важно в "синтаксическом дереве".

Реальная ценность AST IMHO состоит в том, что оно меньше , чем CST, и поэтому обработка занимает меньше времени. (Вы можете сказать, кого это волнует? Но я работаю с инструментом, в котором есть tens of millions of nodes live at once!).

Most parser generators that have any support for building syntax trees insist that you personally specify exactly how they get built under the assumption that your tree nodes will be "simpler" than the CST (and in that, they are generally right, as programmers are pretty lazy). Arguably it means you have to code fewer tree visitor functions, and that's valuable, too, in that it minimizes engineering energy. When you have 3500 rules (e.g., for COBOL) this matters. And this "simpler"ness leads to the good property of "smallness".

But having such ASTs creates a problem that wasn't there: it doesn't match the grammar, and now you have to mentally track both of them. And when there are 1500 AST nodes for a 3500 rule grammar, this matters a lot. And if the grammar evolves (they always do!), now you have two giant sets of things to keep in synch.

Another solution is to let the parser simply build CST nodes for you and just use those. This is a huge advantage when building the grammars: there's no need to invent 1500 special AST nodes to model 3500 grammar rules. Just think about the tree being isomorphic to the grammar. From the point of view of the grammar engineer this is completely brainless, which lets him focus on getting the grammar right and hacking at it to his heart's content. Arguably you have to write more node visitor rules, but that can be managed. More on this later.

What we do with the DMS Software Reengineering Toolkit is to automatically build a CST based on the results of a (GLR) parsing process. DMS then automatically constructs an "compressed" CST for space efficiency reasons, by eliminating non-value carrying terminals (keywords, punctation), semantically useless unary productions, and forming lists for grammar rule pairs that are list like:

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

and a wide variety of variations of such forms. You think in terms of the grammar rules and the virtual CST; the tool operates on the compressed representation. Easy on your brain, faster/smaller at runtime.

Remarkably, the compressed CST built this way looks a lot an AST that you might have designed by hand (see link at end to examples). In particular, the compressed CST doesn't carry any nodes that are just concrete syntax. Есть небольшие неудобства: например, хотя конкретные узлы для '(' и ')', классически встречающиеся в подграмматиках выражений, не находятся в дереве, «узел скобок» действительно появляется в сжатом CST и нужно обрабатывать. У настоящего AST этого не было бы. Похоже, что это довольно небольшая цена за удобство, когда вообще не нужно указывать конструкцию AST. А документация по дереву всегда доступна и правильна: грамматика есть документация.

Как избежать «лишних посетителей»? Мы не совсем, но DMS предоставляет библиотеку AST, которая просматривает AST и прозрачно обрабатывает различия между CST и AST. DMS также предлагает оценщик "грамматики атрибутов" (AGE), который является методом передачи значений вычисленных узлов вверх и вниз по дереву; AGE обрабатывает все проблемы с древовидным представлением, поэтому разработчик инструментов беспокоится только о том, чтобы эффективно писать вычисления непосредственно на самих правилах грамматики. Наконец, DMS также предоставляет шаблоны "поверхностного синтаксиса", которые позволяют фрагментам кода из грамматики использоваться для поиска определенных типов поддеревьев, не зная большинства задействованных типов узлов.

В одном из других ответов говорится, что если вы хотите для создания инструментов, которые могут восстанавливать исходный код, ваш AST должен соответствовать CST. Это не совсем так, но регенерировать источник гораздо проще, если у вас есть узлы CST. DMS генерирует большую часть симпатичного принтера автоматически , потому что имеет доступ к обоим: -}

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

РЕДАКТИРОВАТЬ Март 2015: Ссылка на примеры CST и AST, построенных таким образом