Все существующие программы. Часть 1
Теперь мы умеем перечислять все двоичные и все произвольные деревья определенного размера, и, следовательно, мы можем перечислить их все. Точка. Мы можем перечислить все деревья из одного узла, все деревья из двух узлов и т.д. Это очень полезно для генерации тестовых данных для алгоритмов, оперирующих деревьями. Однако, я также пишу алгоритмы, которые работают с программами; компилятор, конечно же, забит алгоритмами, которые работают с частями программ. Можем ли мы использовать те же самые механизмы для автоматической генерации тестовых данных для компилятора?
Кажется вполне возможным, что мы будем в состоянии это сделать. Я выбрал мою нотацию для произвольных деревьев как последовательность вложенных фигурных скобок специально. Если мы возьмем одну из таких строк, скажем {{}{{}}}, и с помощью поиска и замены заменим первую { на “class A {”, и каждую последующую на “class B {” и так далее мы получим следующий код (с добавленными пробелами):
class A
{
class B { }
class C { class D { } }
}
Т.е. мы можем использовать наш генератор двоичных деревьев для генерации всех возможных вложенностей классов внеся лишь незначительные модификации в код, печатающий строковое представление дерева.
Но мы можем пойти далее. Я хочу выяснить, сможем ли мы создать более общий механизм генерации всех членов определенного языка программирования.
Для этого сегодня я собираюсь начать описание невероятно мощного инструмента проектирования языков программирования, контекстно-независимую грамматику (Context Free Grammar) или сокращенно – CFG.
Думаю, что проще всего начать с примера. Вот CFG для некоторых простых повествовательных высказываний на английском языке:
SENTENCE: SUBJECT VERB OBJECT
SUBJECT: ARTICLE ADJECTIVE NOUN
OBJECT: ARTICLE ADJECTIVE NOUN
ARTICLE: a | one | the
NOUN: dog | man
ADJECTIVE: fat | short
VERB: chases | bites
Идея заключается в том, что каждый раз, когда вы встречаете слово слева от двоеточия, вы можете заменить его словами справа от двоеточия. Давайте, например, начнем с SENTENCE. В этом случае существует только одна корректная замена: SUBJECT VERB OBJECT. Теперь мы выполняем замену для SUBJECT. Опять-таки, существует только одна корректная замена; тогда мы получим: ARTICLE ADJECTIVE NOUN VERB OBJECT. Затем мы выполним замену для ARTICLE. На этот раз у нас появится три возможных варианта; например, выберем “the”. Итак, мы получим: the ADJECTIVE NOUN VERB OBJECT. Теперь сделаем выбор для ADJECTIVE и получим, например, the fat NOUN VERB OBJECT. Продолжая в том же духе, пока не останется больше возможных замен, мы получим что-то вроде the fat man bites the short dog.
Давайте добавим немного формализма: слова, написанные ЗАГЛАВНЫМИ БУКВАМИ, называются «нетерминальными», поскольку до тех пор, пока у вас будет хотя бы одно такое слово, вы еще не завершили работу. Другие слова называются «терминальными»; их дальнейшая замена невозможна. Формально грамматика состоит из (1) набора отдельных терминальных и нетерминальных символов, (2) набора правил преобразования каждого нетерминального символа в набор корректных замен, и (3) начального нетерминального символа (SENTENCE в качестве начального символа в нашем примере). Но вместо того, чтобы его вычислять, мы просто будем начинать с первого символа.
Обычная проблема, с которой сталкивается разработчик компилятора, противоположна описанному только что процессу. Т.е. файл содержит только терминальные символы (the short dog chases the fat man) и задача состоит в обратном: определить, какие точно правила использовались для создания этого выражения; проделать путь к самому началу и в случае неудачи выдать разумное сообщение об ошибке, которое будет описывать причину. Это называется «разбор кода» (parsing the code). Неудивительно, что это является весьма непростым процессом для некоторых грамматик; приведенная здесь грамматика относительно проста для анализа. К счастью, в этой серии статей я не буду рассказывать о малоприятных деталях построения анализаторов; мы хотим использовать CFG для генерации корректных программ, а не для их разбора, так что мы сосредоточимся именно на этом.
Дела с CFG становятся интереснее, когда появляется рекурсия. Рассмотрим эту простую грамматику, всего лишь с двумя правилами, двумя нетерминальными и двумя терминальными символами:
S: { X } | { }
X: X X | { X } | { }
Начальный символ – S. Давайте сделаем замену на { X }. У нас есть три возможных замены для X, давайте выберем первый вариант, в этом случае получим { X X }. (Обратите внимание, что в отличие от нашего первого примера грамматики, мы можем получать выражения произвольной длины! В предыдущей грамматике, независимо от действий вы обязательно получите семь терминальных слов.) Продолжая в том же духе, мы получим { { } X }, затем { { } { X } }, а затем { { } { { } } } и все.
Мы явно получили грамматику для всех возможных произвольных деревьев, так что находимся на правильном пути. Если мы сможем найти способ перечисления всех членов этой грамматики, значит мы в отличной форме.
В следующий раз: суммирование приводит к неоднозначности.