Все существующие программы. Часть 8
Хорошо, давайте начнем с начала. Предположим, что у нас есть строка, которая содержит грамматику, уже переписанную в нашей «удобной» форме, которая содержит в точности два терма для каждого правила подстановки. Мы можем легко написать анализатор для разбора этой строки. Я создам ассоциативный массив, который будет содержать соответствие каждого правила со списком двухсимвольной подстановки. Итак, грамматика имеет вид:
S: N NIL | S P
P: + N
N: 1 NIL | 2 NIL | 3 NIL
, которая преобразуется к ассоциативному массиву:
S –> { (N, NIL), (S, P) }
P –> { (+, N) }
N –> { (1, NIL), (2, NIL), (3 NIL) }
И мы получим:
sealed class Grammar
{
private Dictionary<string, List<Tuple<string, string>>> rules;
public Grammar(string g)
{
rules = new Dictionary<string, List<Tuple<string, string>>>();
foreach (string s in g.Split(new[] { '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries))
{
int i = s.IndexOf(':');
var name = s.Substring(0, i).Trim();
var list = new List<Tuple<string, string>>();
foreach (var o in s.Substring(i + 1).Split('|'))
{
var words = o.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
Debug.Assert(words.Length == 2);
list.Add(Tuple.Create(words[0], words[1]));
}
rules.Add(name, list);
}
}
Просто здорово.
Теперь нам нужен способ сказать: «По указанному символу и точному количеству замен, выполненных для получения этого символа, получить все возможные результаты в виде строк терминальных символов». Мы можем внести простые изменения в наш алгоритм перебора двоичных деревьев.
Прежде всего, рассмотрим простейшие случаи: если нас просят сделать 0 замен, то существует три варианта. Если у нас нетерминальный символ, результата не существует, поскольку нам понадобится как минимум еще одна замена. Если у нас есть обычный терминальный символ, мы возвращаем именно его. И у нас может быть NIL, напомню, что это специальный нетерминальный символ, идентичный пустой строке.
Если нам нужно выполнить замену, тогда мы можем иметь дело либо с терминальным, либо с нетерминальным символом. Если у нас имеется терминальный символ, тогда результат получить мы не можем, поскольку мы не можем замещать терминальные символы. Если нам нужно выполнить замену нетерминального символа, тогда это явно не базовый случай и нам нужно выполнить эту же операцию рекурсивно.
private static string[] empty = { };
public IEnumerable<string> All(string symbol, int substitutions)
{
bool terminal = !rules.ContainsKey(symbol);
if (substitutions == 0)
{
// Замен больше нет; лучше бы это был терминальный символ.
if (terminal)
return new string[] { symbol == "NIL" ? "" : symbol + " " };
return empty;
}
// Выполняем замены; лучше бы это был нетерминальный символ.
if (terminal)
return empty;
return from r in rules[symbol]
from i in Enumerable.Range(0, substitutions)
from left in All(r.Item1, i)
from right in All(r.Item2, substitutions - i - 1)
select left + right;
}
Давайте проверим этот код. Вот грамматика, которая содержит два символа на одну подстановку для языка «со всеми соответствующими комбинациями круглых, квадратных и фигурных скобок, а также символов «больше/меньше»:
const string parengrammar = @"
S: S S | ( PARENEND | [ BRACKETEND | { BRACEEND | < ANGLEEND
PARENEND: S ) | NIL )
BRACKETEND: S ] | NIL ]
BRACEEND: S } | NIL }
ANGLEEND: S > | NIL >
";
static void Main()
{
Grammar g = new Grammar(parengrammar);
for (int i = 1; i < 5; ++i)
{
Console.WriteLine(i);
foreach (var s in g.All("S", i))
Console.WriteLine(s);
}
}
И конечно же, вывод результатов будет таким:
1
2
( )
[ ]
{ }
< >
3
4
( ( ) )
( [ ] )
( { } )
( < > )
[ ( ) ]
[ [ ] ]
[ { } ]
[ < > ]
{ ( ) }
{ [ ] }
{ { } }
{ < > }
< ( ) >
< [ ] >
< { } >
< < > >
Обратите внимание, что это не все варианты строк из четырех символов; здесь представлены строки, которые требуют четырех замен. Строка ( ) ( ) не входит в этот список, поскольку она требует пяти замен для ее вывода.
Попробуйте запустить эту программу для одиннадцати, двенадцати, тринадцати и т.д. замен. Не заметили ничего странного? Конечно же, на экран выводится все большее и большее количество строк. Но есть еще один момент, на который стоит обратить внимание, такое чувство, что выполнение становится все медленнее… и медленнее… и медленнее.
В следующий раз: Безумие!