Alexey Veselovsky писал(а):
Для синтаксического анализа имеется вполне вменяемая теория, есть и всякие утилиты помогающие в создании синтаксических анализаторов (тот же lex/yacc например).
А есть ли что-то для обратной задачи? Т.е. синтаксического синтезатора. Т.е. нечто позволяющее генерировать гарантированно валидный текст с т.з. вот этой вот грамматики.
Очень необычное название термина. Как раз недавно появилась
публикация, использующая похожую формулировку. А вообще, если я правильно представляю, задача разбора (parsing) потока токенов отличается от его генерации: в первом случае мы имеем поток, в котором, по большому счету, может быть всё, что угодно. Во втором же — абстрактное синтаксическое дерево, процесс получения из которого символьной презентации сводится к его линеаризации.
В проекте Grammatical Framework это является одной из центральных идей: есть один центральный модуль абстрактного синтаксиса и N модулей конкретного синтаксиса для всех поддерживаемых языков, задающих правила линеаризации, которые используются как для разбора, так и для "синтеза" текста.
Если же в вопросе имелась ввиду генерация произвольных текстов программ (например, для тест-вариантов),
здесь есть неплохой обзор работ по этой теме, начиная ещё с 70-х годов.