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

Question

Исходный код программы на C может быть проанализирован в соответствии с грамматикой C (описанной в CFG) и в конечном итоге превращен во многие AST. Я рассматриваю, существует ли такой инструмент: он может сделать обратное, сначала случайным образом генерируя много AST, которые включают токены, которые не имеют конкретных значений строки, только типы токенов, согласно CFG, затем генерируют конкретный токены в соответствии с определениями токенов в регулярном выражении.

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

Есть ли какой-нибудь инструмент, который может это сделать?

Answer 1

«Язык генерации данных» DGL делает это с добавленной способностью взвешивать вероятности продукций в грамматике, которая выводится.

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

Answer 2

Учитывая неконтекстную грамматику языка, можно генерировать случайную строку, которая соответствует грамматике .

Например, генератор синтаксического анализатора nearley включает реализацию "unparser" , которая может генерировать строки из грамматики.

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

Answer 3

проблема со случайной генерацией состоит в том, что для многих CFG ожидаемая длина выходной строки бесконечна (имеется простое вычисление ожидаемой длины с использованием генерирующих функций, соответствующих нетерминальным символам, и уравнений, соответствующих правилам грамматика); Вы должны контролировать относительные вероятности производства определенными способами, чтобы гарантировать конвергенцию; например, иногда взвешивания каждого производственного правила для нетерминального символа обратно пропорционально длине его RHS достаточно

На эту тему можно найти гораздо больше: Ноам Хомский, Марсель-Поль Ш \ '{u} tzenberger, `` Алгебраическая теория контекстно-свободных языков' ', с. \ 118-161 в P. Braffort и D. Hirschberg (eds.), Компьютерное программирование и формальное Системы, Северная Голландия (1963) (см. статью в Википедии по теореме перечисления Хомского – Шютценбергера)

Answer 4

Если у вас есть модель грамматики в нормализованной форме (все правила, как это):

 LHS = RHS1 RHS2 ...  RHSn ;

и язык prettyprinter (например, AST для преобразования текста), вы можете довольно легко создать один из них.

Просто начните с символа цели в виде дерева юнитов.

  Repeat until no nonterminals are left:
    Pick a nonterminal N in the tree;
       Expand by adding children for the right hand side of any rule
       whose left-hand side matches the nonterminal N

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

Сложность описанного выше алгоритма состоит в том, что он явно не завершается. Что вы на самом деле хотите сделать, так это выбрать некоторое ограничение на размер вашего дерева и запускать алгоритм до тех пор, пока все нетерминалы не исчезнут или вы не превысите этот предел. В последнем случае вернитесь назад, отмените последнюю замену и попробуйте что-нибудь еще. Это дает вам ограниченный поиск в глубину для поиска AST вашего определенного размера.

Тогда распечатайте результат. Это красивая часть , которую трудно понять.

[Вы можете собрать все эти вещи самостоятельно, включая симпатичный принтер, но это довольно трудоемкий труд. Я создаю инструменты, которые включают весь этот механизм непосредственно в параметризованном языке; смотри мою биографию].

Противная проблема даже с хорошо сформированными AST заключается в том, что они могут быть бессмысленными; вы можете создать объявление целого числа X и присвоить ему строковое литеральное значение для языка, который этого не допускает. Возможно, вы можете устранить некоторые простые проблемы, но семантика языка может быть невероятно сложной, рассмотрим C ++ в качестве примера. Гарантировать, что вы получите семантически значимую программу, чрезвычайно сложно; по сути, вы должны проанализировать полученный текст и выполнить разрешение и проверку имени и типа. Для C ++ вам нужен полный интерфейс C ++.