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

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

Возможно есть какая-нибудь книга где рассматривается что-то похожее на мой велосипед?

вспомнил книгу: https://www.amazon.com/Engineering-Compiler-Keith-Cooper/dp/012088478X

в ней должно быть

скриншот выше был из нее

Насколько я навскидку могу прикинуть:
Это таки обход в глубину, где при подъеме вы матрешки схлопываете.
Это можно понять по скрину что я кинул. Все узлы пустышки содержат только одного ребенка.
Потому при рекурсивном подъеме вы их закономерно посетите один раз.
Т.е. к примеру встретили узел умножения у которого один ребенок (хотя должно быть очевидно два),
вот и заменяете его на ребенка и т.д. рекурсивно. Вроде так

В старом ANTLR (в ANTLR я некомпетентен и сейчас начну врать) была подсистема для трансформации parse tree в AST, где можно было задать грамматику, очень похожую на оригинальную LL(k). В новом, кажется, это всё выкинули, но что-то интересное точно было.

Да, память не обманула, "tree parsers" в ANTLR 2.

Красивые term rewrite и все дела: https://www.antlr2.org/doc/sor.html

никогда мне это не нравилось, я всегда руками писал :)

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

Системы переписывания действительно красивые. Но вот уровень старого ANTLR легко перекрывается использованием языка с встроенной поддержкой сопоставления с образцом.

Честно говоря, мне нечего возразить: я отказался от ANTLR, когда он назывался PCCTS, и отстал от LL-жизни 😊

Да, поэтому в новом все это прописывается в коде внутри листенеров, а в парсере устанавливается BuildParseTree = false

Забыл сказать еще одну вещь - я пишу генератор парсеров просто на макросах в языке, так что он выглядит как обычная библиотека. И в таком случае можно говорить уже про API для генератора парсеров. И "даем грамматику, получаем дерево" выглядит гораздо лучше чем рассовывание кусочков кода по какому-то DSL. Это уже делали конкретной реализации но все же решил уточнить.

Чет не вижу, и что-то вообще сейчас задумался а существует ли он в вакууме.
Этож надо алгоритму и описание AST какое-то скормить, и подсказать как преобразовывать.
Универсального рецепта наверно нет.

ааа, я тоже помню это слово :)

🍺

на самом деле рекурсивный парсер вполне можно в таком стиле писать, c макросами/библиотекой тем более красиво будет

Самый простой и красивый способ — использование PEG. И на уровне текста, и на уровне термов-деревьев.

Так Вы накаком языке пишите-то?