Да, но меня смущает, как PEG-парсеры подходят к проблеме неоднозначности.

Ну, когда мы сопоставляем AST-узлы по шаблонам, то упорядоченный выбор ведь не кажется чем-то искусственным?

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

Как именно AST сопоставляется шаблонам — это личное дело архитекторов программы. В ANTLR пытались родить формализм для этой трансформации, но отказались от него.  А синтаксический разбор — это другое дело, тут есть классические формальные методы, и PEG/GLR их упраздняют. Хорошо ли это, я не уверен.

PEG это легкая декларативная надстройка над обычным рекурсивным спуском. Важно, что с одним формализмом PEG можно и синтаксическим разбором заниматься, и преобразованиями программ на уровне AST. В результате получается удивительно компактный «швейцарский нож» для задач компиляции.

Тогда, скорее всего — просто визитором. (Это на вопрос как parse tree перегонять в AST.)

Да, конечно, это понятно. Но вот тривиальный смешной пример: что произойдёт если PEG-у скормить ту же левую рекурсию? (Я не знаю, как поведут себя самые продвинутые из реализаций генераторов, но догадываюсь, что случится во всех остальных.)

Самый очевидный способ — добавить запоминание для поддержки левой рекурсии. Это давно уже используется в популярных PEG-инструментах.

Не могу навскидку представить, как это может помочь, но подумаю-почитаю.

Спасибо. Тогда остаётся (для меня) вопрос неоднозначности и производительности.

Ну, я бы, например, был более озабочен вопросами преобразования программ средствами PEG :) PEG для синтаксического анализа — штука и так известная и проверенная.

Всё зависит от области применения, наверное.

Возможно. Или причина в том, что на тему PEG для AST есть только 2-3 академических статьи, да пара малоизвестных/забытых инструментов :)

И что произойдет?

Не знаю. В наивных реализациях — переполнение стека во время парсинга, например.

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

Но, как правильно уже было замечено ранее, часто полезно осуществить предварительный разбор сначала для обобщенного-relaxed варианта грамматики, в затем уточняющую трансляцию (и часто не одну) провести уже на уровне абстрактного синтаксиса. И здесь «классические формальные методы» уже не помогут.

Не помогут. Но (занудствую последний раз) если можно разделить формализуемое и неформализуемое и повластвовать, то почему бы и не разделить?

Я просто предлагаю заранее не опускать руки (читай: переходить на шаблон посетителя и проч.) :)

Резонно.