Вы можете сделать это, используя парсер, превратив его в генератор.
Сначала создайте рекурсивный парсер для вашего языка.( См. Мой SO-ответ о том, как это сделать ). пауза пока вы читаете это .... Теперь я предполагаю, что вы понимаете, как это сделать.
Вы заметите, что такой парсер полон вызовов из функции парсера для одной грамматикиПравило, к другим функциям для других правил грамматики или примитивных сопоставителей токенов.
То, что вы хотите сделать, - это изменить каждый вызов, чтобы решить, что он вернет "true" с некоторой низкой вероятностью, если в функции еще есть какая-то альтернатива, до того, как будет выполнен вызов.Если для вызова принимается ложное решение, управление просто переходит к другой части синтаксического анализатора.если вызов решает, что истина, он фактически делает вызов;вызываемый объект должен теперь действовать так, чтобы он возвращал true и генерировал соответствующий исходный код.В какой-то момент это заставит вызов читателя токена вернуть true;считыватель токенов заменяется функцией печати, которая генерирует случайный токен.На самом деле, когда вы делаете это, звонки, чтобы решить, правда ли что-то, теперь просто становятся звонками;нам больше не нужен статус возврата, потому что вызываемая функция должна возвращать true.Это меняет наши функции-возврат-bools на процедуры-возврат-пустота.См. Пример ниже ..
Давайте попробуем пример с этой простой грамматикой для простого языка программирования p :
p = s ;
s = v '=' e ;
s = 'if' e 'then' s ;
e = v ;
e = v '+' n ;
ОК, наш анализатор рекурсивного спуска для p (я не парень из Python, так что это psuedocode):
function p() { return s(); } // no alternatives
function s() { if v()
then if match("=")
then return e()
else return false;
else if match("if")
then if e()
then if match("then")
then return s()
else return false;
else return false;
else return false;
}
function e() { if v()
then if match ("+")
then if n()
else return true
else return false
}
function v() { return match_variable_name(); }
function n() { return match_integer_constant(); }
ОК, теперь давайте заставим вызовы решать, будут ли они успешными, используя функцию подбрасывания монетыслучайным образом возвращает истину или ложь.Любая конструкция формы:
if <testsomething> then <action x> else <action y>
превращается в:
if flip() then { <testsomething> <action x> } else <action y>
, а любая конструкция формы:
if <testsomething> then <action x> else return false
превращается в
{ <testsomething>; <action x> }
, потому что он должен завершиться успешно, если мы хотим создать анализируемые программы.
Если testsomething - это вызов функции для другого правила грамматики, мы оставляем его в покое.Вызовы функций для совпадений примитивных токенов превращаются в операторы print: если testsomething равно «match (Q)», то замените его на «print (Q)»;это то, что фактически генерирует часть программы.
procedure p() { s(); } // no choice, this has to succeed
procedure s() { if flip() // flip == true --> v must succeed
then { v();
print("=") // because if no match, procedure fails
e();
}
else { print("if") // if we get here, must succeed
e();
print("then"); // because match("then") must succeed
s();
}
}
procedure e() { v(); // because there are no alternatives
if flip() then { print("+");
n();
}
else { }
}
procedure v() { print_variable_name(); }
procedure n() { print_integer_constant(); }
Обратите внимание, что распознаватели токенов для имен переменных и целочисленных констант теперь становятся процедурами печати, которые печатают случайные имена / константы переменных.По сути, это просто нажатие кнопки «flip» в этих процедурах.
Теперь это может печатать произвольно длинные программы, потому что flip может заставить s повторно вызывать себя.Если сальто 50-50, ваши шансы на 10 рекурсий в 1 на 1000, так что, вероятно, все в порядке.Тем не менее, вы можете решить смещать каждый отдельный бросок, чтобы выбрать более короткую фразу, основанную на размере сгенерированного результата или глубине любой рекурсии.
Теперь, что это не будет делать вВ общем случае производят семантически правильных программ.Это потому, что наш парсер "не зависит от контекста";нет ограничений на одну часть сгенерированного кода, навязанную другими частями.Например, если ваш язык должен был объявить переменную перед ее использованием, эта схема не гарантирует, что объявление для random-var-X будет создано до того, как randome-var-X появится в выражении.
Нет простого способа исправить это, потому что семантика языка не гарантируется быть «легкой».Просто показывает, что анализ программы («технически простой») и проверка правильности семантики («произвольно сложная», рассмотрим C ++), приводит к любой столь же сложной проблеме генерации случайной программы, которая не нарушает семантику языка.