Есть ли различия между терминами разбора деревьев и деривационных деревьев? - PullRequest
8 голосов
/ 20 апреля 2011

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

Ответы [ 3 ]

8 голосов
/ 20 апреля 2011

AFAIK, "дерево деривации" и "дерево разбора" совпадают.

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

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

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

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

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

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

в то время как абстрактное синтаксическое дерево 1026 * может выглядеть следующим образом:

ASSIGNMENT
  /    \
 a   expression 
      /     \
 expression  *
     |        \ 
     +         3 
    / \
   1   2
3 голосов
/ 29 апреля 2011

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

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

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

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

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

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

  +
 | |  
 n n
3 голосов
/ 20 апреля 2011

Все синтаксические деревья разбора / деривации / конкретного синтаксиса являются синонимами одного и того же понятия.

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

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

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

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

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

...