Все существующие программы. Часть 6
Работая над механизмом перечисления результатов работы различных грамматик мы столкнулись с проблемой, связанной с тем, что рекурсия не сводит задачу к задаче меньшего объема. Нам нужно найти способ свести задачу к меньшей задаче, при этом гарантируя, что перебираем все возможные программы, определенные некоторой грамматикой.
Я уже говорил ранее, что существует два типа грамматик: неоднозначная и однозначная. Мы предпочитаем однозначные грамматики, поскольку у них есть отличное свойство, что каждая возможная программа, которая соответствует этой грамматике имеет только один левосторонний вариант разбора. Вспомните наш пример грамматики для генерации сумм:
S: N | S + N
N: 1 | 2 | 3
левосторонний вывод 1 + 2 + 3 будет таким:
S
S + N
S + N + N
N + N + N
1 + N + N
1 + 2 + N
1 + 2 + 3
Это единственный способ создания строки 1 + 2 + 3 с помощью левосторонних замен в этой грамматике. Обратите внимание, что эта замена состоит из семи строк.
Хмм. Это единственный путь, который дает эту строку и он состоит из семи шагов. Поскольку грамматика является однозначной, каждая строка в языке грамматики ассоциирована с конкретным целочисленным значением, которое является количеством строк уникального вывода. И здесь должно существовать конечное число программ, которые требуют семь замен, поскольку всегда существует конечное число возможных левосторонних замен на каждом шаге вывода.
Ага! вместо анализа длины конечной строки мы должны анализировать длину вывода, требуемую для получения этой строки. Т.е. мы можем перечислить все строки терминальных символов определенной грамматики путем перечисления всех строк, которые требуют одной замены, затем всех строк, которые требуют двух замен, затем всех строк, которые требуют трех замен … и т.д.
Опять-таки, я хочу получить краткую нотацию для «всех строк терминальных символов, чей вывод начинался из строки нетерминальных символов X и который состоял в точности из n шагов». Я обозначу это как X[n]. И опять-таки, для обозначения «комбинации все строк вида X, требующие n замен, за которыми следуют строками вида Y, требующие m замен», я буду использовать нотацию вида X[n]Y[m].
Давайте снова рассмотрим нашу модифицированную арифметическую грамматику.
S: N | S P
P: + N
N: 1 | 2 | 3
Как мы можем сказать «получить все строки вида S, которые получены в точности после пяти замен»? Т.е. S[5]. Мы делаем одну замену, чтобы получить N или S P. У нас остается еще четыре замены, которые мы можем выполнить для каждой из двух возможных исходных замен. Решение сводится к набору строк, полученных путем объединения N[4], S[4]P[0], S[3]P[1], S[2]P[2], S[1]P[3] и S[0]P[4].
Помните, что нам нужно выполнение трех условий для получения рабочего рекурсивного решения: уменьшение размера задачи , комбинация решений подзадач и тривиальный базовый случай.
На этот раз мы действительно уменьшаем задачу; каждая подзадача на каждом последующем шаге требует строго меньшего количества замен. Наше решение явно является объединением решений подзадач. Есть ли у нас тривиальный базовый случай?
Да. Во-первых, мы знаем, что S[0] и P[0] не содержат строк, поскольку S и P являются нетерминальными символами; они всегда требуют по крайней мере одну замену, для получения строки терминальных символов. Мы можем решить эту задачу очень просто: таких строк существовать не должно. И во-вторых, предположим мы пытаемся решить задачу P[2]. Решения задачи P[2] – это объединение +[1]N[0] и +[0]N[1]. Мы знаем, что N[0] является пустым набором, поскольку “не существует замен этого нетерминального символа». Мы также знаем, что +[1] является пустой строкой, поскольку существует «только одна замена этого терминального символа», но замена терминальных символов невозможна. И мы знаем, что +[0] является строкой +, поскольку «не существует замены этого терминального символа», результатом которой является терминальный символ.
Мы забыли одну вещь, NIL, это особый случай, который не создает ни терминальные, ни нетерминальные символы. Об этом случае легко позаботиться; мы просто определим NIL[0], как набор, содержащий только пустую строку, и NIL[n], для n не равного нулю, как пустой набор; не существует строк, которые являются результатом множества замен символа NIL. (Опять-таки, это неотъемлемое свойство NIL, которое является лишь искусственным способом записи терминального символа, являющегося пустой строкой; по-другому можно сказать, что NIL – это нетерминальный символ и определить NIL[1] как набор, который содержит только пустую строку, а это значит, что NIL[n] является пустым набором для всех других значений n. На самом деле не имеет значения, какое мы выберем определение, пока мы будем делать что-то последовательно.)
В следующий раз: перепишем грамматику для упрощения.