ну вот как раз дерево и буду строить

пока что все ещё не понимаю для чего оно нужно

type program у меня чтобы хранить распаршенную программу

В нём по 1 конструктору на языковую фичу

ну так это +- описание грамматики, разве нет?

Нет! Это описание типа дерева.

Просто, как бы это сказать, я понимаю, что после С# нечто короче 2х экранов не воспринимается, как описание типа, но это именно оно и есть

как такая нотация называется?

это не к Роману вопрос

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

Алгебраический тип это, обычный, в F#

спасибо

это я понимаю, я разбил текст на токены, определил First Follow, далее сканируя токены буду строить AST.

Затем AST отправлю семантическому анализатору

смотри, все просто

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

Парсер описывает конкретное синтаксические дерево, которое просто показывает, как исходный код был распаршен. Там удобное представление, чтобы получить его из парсера, но не самое удобное, чтобы с ним работать.

В простых случаях cst (конкретное) и ast (абстраткное) можно не разделять, если парсер достаточно гибкий, чтобы сразу строить ast. На каких-нибудь генераторах имхо это делать сложно, на комбинаторах просто

Значит парсер строит конкретное дерево, которое потом конвертируется а абстратное дерево. Потом мы с ним работаем, например строим из него абстрактное дерево другого языка (при трансляции), или промежуточное, которое потом в таргетное дерево.

Дерево вот как раз легко описывается в фп языках (но не обязательно только в фп) через adt, как вот на скрине выше. Это не грамматика, это определение типов.

type expr =
 | val of int
 | plus of expr * expr

1 + (2 + 3)

выглядит как

let x : expr = plus (val 1) (plus (val 2) (val 3))
в аст (и мб с отдельным конструктором скобок в cst)

да и не только в фп япах. хотяя.... я не хочу начинать споры о том, что это фп фича или нет. но  в расте все также можно описать с помощью enum

но с учетом того, что у меня нисходящий анализатор и продукции я разворачиваю, а не сворачиваю разве не так построиться дерево?

вся программа  у меня это тоже продукция, которая состоит из не терминалов, которые тоже продукции

Да какая разница-то? Один чёрт парсер строит из потока слов - дерево.

да, я согласен. Вроде я это даже указал

я вот на плюсах пишу... 😰
плакот хочица

такс, я  с помощью enum  описываю типы токенов, но это врядли оно