Какой самый простой пример объясняет разницу между деревьями разбора и деревьями абстрактного синтаксиса?

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

У меня сложилось впечатление, что и дерево синтаксического анализа, и абстрактное синтаксическое дерево создаются на этапе синтаксического анализа. Тогда кто-то может объяснить, почему они разные?

Дерево разбора также известно как конкретное синтаксическое дерево.

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

Например выражение: (2 + 5) * 8

Бетон выглядит так

  ( 2  + 5 )  * 8
  |  \ | / |  | |
  |   \|/  |  | |
   \___|__/   | |
       \______|/

В то время как абстрактное дерево имеет:

2  5 
 \/   
  +  8
   \/
   *

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

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

Например, следующий язык:

prog:
      definition 
    | definition ';' prog
    ;

definition: .....

может быть представлен в виде списка определений. (Nitpickers укажет, что список является вырожденным деревом, но в любом случае.)

Во-вторых, нет необходимости держать дерево синтаксического анализа (или какую-либо структуру данных, возвращенную анализатором). Напротив, компиляторы обычно конструируются как последовательность проходов, которые преобразуют результаты предыдущего прохода. Следовательно, общая компоновка компилятора может быть такой:

parser :: String             -> Maybe [Definitions]      -- parser
pass1  :: [Definitions]      -> Maybe DesugaredProg      -- desugarer
pass2  :: DesugaredProg      -> Maybe TypedProg          -- type checker
pass3  :: TypedProg          -> Maybe AbstractTargetLang -- code generation
pass4  :: AbstractTargetLang -> Maybe String             -- pretty printer

compiler :: String           -> Maybe String    -- transform source code to target code
compiler source = do
   defs  <- parser source
   desug <- pass1 defs
   typed <- pass2 desug
   targt <- pass3 typed
   pass4 targt

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