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

В проекте Grammatical Framework это является одной из центральных идей: есть один центральный модуль абстрактного синтаксиса и N модулей конкретного синтаксиса для всех поддерживаемых языков, задающих правила линеаризации, которые используются как для разбора, так и для "синтеза" текста.

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