Все существующие программы. Часть 4
Напомню, что цель этого упражнения заключается в создании инструмента, который бы помогал мне тестировать части компилятора. Для тестирования двоичных деревьев, как мы видели, можно генерировать все деревья из одного, двух, трех и т.д. элементов. Этот механизм обладает полезными свойствами. Во-первых, мы знаем, что рассматриваем все без исключения двоичные деревья и любое конкретное дерево мы рано или поздно получим. Во-вторых, вначале мы гарантировано получим деревья меньшего размера; если алгоритм работает для всех деревьев размером 5 и меньше, значит, он работает для всех деревьев. И в-третьих, ни при каких обстоятельствах алгоритм не будет выполняться бесконечно; можно не беспокоиться о бесконечных циклах. Нужно беспокоиться о комбинаторном взрыве, поскольку существует множество деревьев, но каждое дерево может быть получено за конечное время. Было бы неплохо получить аналогичные возможности для кода, который бы генерировал каждое выражение для определенной грамматики.
Очевидным решением в лоб этой задачи является создание анализатора грамматики. Т.е. генерируем все строки из одного элемента, разбираем ее и отбрасываем те строки, которые мы не можем корректно разобрать. Затем генерируем все возможные строки из двух элементов и т.д. Недостаток этого подхода заключается в том, что скажем, для генерации строки class c : b { }, даже если вы ограничитесь алфавитными символами нижнего регистра, пробелами и знаками пунктуации, вам придется сгенерировать и разобрать около триллиона триллионов строк, большая часть из которых не будет являться программами, как например, aaaaaaaaaaaa},c. Этот метод слишком медленный.
Более разумным способом будет сгенерировать все строки, которые состоят из одного терминального символа, разобрать их, отбросить некорректные, сгенерировать все строки из двух терминальных символов, и т.д. Т.е. начать с разбора a, class, { и т.д. Этот путь значительно лучше; он потребует всего лишь около миллиона шагов, чтобы получить class c : b { }. Но он все еще слишком медленный и нам, к тому же, придется написать анализатор. Было бы значительно лучше не генерировать некорректные программы вовсе.
А что, если бы у нас был способ сказать «сгенерируй все корректные программы с одним терминальным символом; хорошо, теперь сгенерируй мне все программы с двумя терминальными символами» и т.д.? Т.е. не нужно создавать кандидаты, а потом их проверять, просто создавай все корректные кандидаты. Это будет работать. Но как это сделать?
Давайте вернемся к нашей первой задаче: генерации строк для всех возможных двоичных деревьев. Грамматика для того языка была следующей:
T: x | ( T T )
Мы можем воспользоваться тем же механизмом, который использовали до этого! Помните, перед генерацией всех двоичных деревьев из четырех элементов мы сказали, что эти деревья выглядят так:
{все двоичные деревья размером 0} за которыми следуют {все двоичные деревья размером 3}
{все двоичные деревья размером 1} за которыми следуют {все двоичные деревья размером 2}
и т.д. Т.е. все строковые представления двоичных деревьев, скажем, из восьми терминальных символов:
( {все строки с 0 терминальных символов } {все строки с 6 терминальными символами } )
( {все строки с 1 терминальным символом } {все строки с 5 терминальными символами } )
и т.д. Т.е. мы берем два терминальных символа для окружающих скобок, и затем находим все комбинации, которые приведут к шести дополнительным комбинациям внутри скобок. Мы явно сводим задачу размера k к нескольким задачам, размера, меньшего, чем k-1, так что это отличный способ для рекурсивного решения. Так ведь?
В следующий раз: Я прав или я где-то допустил логическую ошибку?