Есть ли различия между деревьями синтаксического анализа терминов и деревьями деривации?

AFAIK, "производное дерево" и "дерево синтаксического анализа" одинаковы.

Абстрактное синтаксическое дерево

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

Дерево синтаксического анализа

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

Возьмем, к примеру, источник a = (1 + 2) * 3;. дерево синтаксического анализа может выглядеть так:

    ASSIGNMENT
   / / |      \
  / /  |       \ 
 a = expression ;
       /   \
 expression \ 
   / | \     \
  (  +  )     *
    / \        \
   1   2        3

в то время как абстрактное синтаксическое дерево может выглядеть так:

ASSIGNMENT
  /    \
 a   expression 
      /     \
 expression  *
     |        \ 
     +         3 
    / \
   1   2

Синтаксические деревья Parse / Derivation / Concrete - синонимы одного и того же понятия.

Такие деревья обычно используются только в теоретических дискуссиях, потому что они содержат множество деталей, которые кажутся ненужными для выполнения языковой обработки; в дереве выражения вам действительно нужен узел для представления "(" и другой для представления ")"?

Понятие дерева «абстрактного синтаксиса» - это дерево, которое представляет структуру программы с уровнем детализации, который подходит для обработки на практике; вы обычно не находите узлы для "(...)".

Интересный вопрос: можно ли напрямую вычислить AST из CST? Ответ должен быть положительным, но люди почти никогда этим не занимаются. Что они обычно делают, так это конструируют узлы с «абстрактным синтаксисом» во время работы синтаксического анализатора и используют специальное (процедурное присоединение по сокращению правил) для сборки узлов из дочерних синтаксических анализов с помощью связующего узла для родительского узла. ИМХО, они так поступают, потому что все мы выросли на YACC, и так это традиционно делается. (Мы тоже зажигали огни кремнем.) Есть меньшее оправдание; такой способ дает компилятору-сборщику полный контроль над структурой AST, и он может создать такую, которая будет минимальной с точки зрения дополнительных деталей. Такое специальное дерево невозможно вычислить из CST, за исключением тех же специальных вычислений, которые встроены в действия синтаксического анализатора.

Я использовал другой подход: мои инструменты вычисляют AST непосредственно из CST, буквально путем отбрасывания нерелевантных деталей, например, исключения узлов, которые представляют токены, не несущие ценности (например, этих бессмысленных токенов '(' ')', а также ключевых слов), сжатия строк унарных производств и преобразования вправо или влево деревья, эквивалентные спискам, в узлы реальных списков. Преимущество этого заключается в том, что синтаксический анализатор может вычислять AST непосредственно из правил грамматики. Не возиться с процедурными вложениями. Не пойму неправильно. Больше не нужно беспокоиться о том, что наша грамматика COBOL содержит 3500 правил, и я бы в противном случае Мне нужна процедурная слизь для каждого из них, и что мне приходится менять свою грамматику сотни раз, чтобы сделать ее правильной, и каждый раз возиться с этой слизью. И наши инструменты работают так, как будто они работают непосредственно с CST, что позволяет легко думать о манипуляциях с деревом, особенно если вы смотрите прямо на правила грамматики. (Это также значительно упрощает сопоставление с образцом с использованием поверхностного синтаксиса: для любого фрагмента образца существует соответствующий напрямую вычисляемый AST).

Так что разница между AST и CST реальна с точки зрения полезности. Но я думаю, что их следует рассматривать как просто изоморфные представления.

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

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

Формальное определение синтаксического анализа - это поиск производной для заданной входной последовательности, поэтому неудивительно, что производные и синтаксические деревья - одно и то же.

Конкретные и абстрактные синтаксические деревья отличаются тем, что первое имеет листовой узел для каждого токена во входной последовательности, а второе опускает любые токены, которые могут быть известны путем проверки грамматики. . Поддерево конкретного синтаксиса для if <expr> then <statement> else <statement> end будет иметь листья для if, then, else и end, а абстрактное никто бы не стал. Конкретное синтаксическое дерево для (2+3) будет:

  e
  |
( e )
 /|\        
| | |  
n + n

Абстрактный будет просто:

  +
 | |  
 n n