Без перебора с возвратом. Часть 1
В нескольких статьях, опубликованных в этом году, я говорил об алгоритме «перебора с возвратом» (backtracking algorithm); в последний раз я упоминал о нем в серии статей, посвященных решению головоломок Судоку с помощью перебора с возвратами (и более общей задачи раскраски графов). Идея алгоритма перебора с возвратом очень проста и эффективна: если возникает необходимость выбора, просто переберите все возможные варианты. Если все они не верны, вернитесь назад к последнему выбору и попробуйте другой вариант. Алгоритмы перебора с возвратами, по сути, являются поиском в глубину (depth-first search) пространства возможных решений.
А что если пространство решений велико? Количество вариантов расположения 9 цифр в 81 позиции сопоставимо с числом протонов во Вселенной; мы не можем проверить все. Причина, по которой перебор с возвратом назад работает так быстро для головоломок Судоку, заключается в том, что практически каждое предположение устраняет множество ветвей в дереве решений. Если вы предполагаете, что первое поле содержит 1, то вам не нужно рассматривать вариант, когда второе поле тоже содержит 1; вы можете просто отбросить эту ветвь и никогда ее не анализировать. А поскольку сама по себе эта отброшенная ветвь является ОГРОМНОЙ, то это является отличной стратегией! (Существуют патологические случаи этого алгоритма, но на практике он достаточно быстр.)
Алгоритмы перебора с возвратом назад хорошо работают во многих ситуациях, но мы сознательно избегали их при проектировании языка C# (за несколькими исключениями).
Например, не существует алгоритма перебора с возвратом назад, который бы пересекал «фазы» компиляции в C# (*). Когда мы начинаем работу с некоторым кодом, то первое, что делаем – разбиваем его на лексемы или токены. Это сродни поиску слов в предложении путем поиска пробелов и знаков пунктуации. Затем мы выполняем грамматический (синтаксический) анализ потока токенов, а после этого – семантический анализ результатов грамматического анализа. Если в процессе выполнения одного из этих этапов мы получаем ошибку, то никогда не возвращаемся к предыдущему этапу с просьбой выполнить анализ еще раз. Предположим у нас есть следующий нелепый код:
x = j+++++1;
Лексически – это корректный C# код. Лексический анализатор является «жадным»; он старается создать токены максимального размера в конкретных условиях. Так что он разбивает этот код на токены следующим образом:
x , = , j , ++ , ++ , + , 1 , ;
Теперь грамматический анализатор принимает этот набор токенов и говорит «это выражение содержит два идентификатора, одну константу и четыре оператора; в какой последовательности мне их выполнить?» Грамматический анализатор использует правила приоритетов и ассоциативности и получает следующее:
x=(((j++)++)+1);
Т.е. этот код означает «вычислить x, затем инкрементировать j, затем инкрементировать предыдущий результат, затем прибавить 1 к предыдущему результаты, затем присвоить предыдущий результат переменной x, готово».
Семантический анализатор проверяет этот код, чтобы удостовериться, что он имеет смысл. Но это не так, поскольку результатом выполнения j++ является значение, а не переменная, а последующий оператор ++ требует переменную. Семантический анализатор выдает ошибку, и программа не компилируется.
Если бы у нас был компилятор с перебором с возвратами, то семантический анализатор мог бы сообщить синтаксическому анализатору (parser) «нет, ты сделал что-то не то, дай мне другое дерево разбора, если оно существует».
Предположим, синтаксический анализатор работает именно таким образом. Он может сказать, что «ну, возможно последний + был не бинарным оператором, а унарным оператором +, который применяется к 1, хм, но в этом случае мы получим подряд два выражения, следующих одно за другим, между которыми отсутствует оператор. То же самое будет, если второй оператор ++ применяется к +1 вместо j++. Так что, нет, другого варианта разбора здесь нет. Так что возвращаемся к лексическому анализатору и просим его найти другое решение.
Лексический анализатор может сказать, «хорошо, если тебе не нравится этот вариант, тогда возможно мое предположение о том, что второе выражение ++ было оператором ++ оказалось неверным. Тогда попробуй такой вариант»:
x , = , j , ++ , + , ++ , 1 , ;
Тогда синтаксический анализатор скажет, «хорошо»; если токены разбиты именно таким образом, тогда грамматический анализ дает следующий результат:
x=((j++)+(++1));
С точки зрения семантического анализатора этот код также неверен, на этот раз, потому что вы не можете использовать оператор ++ с константами. Итак, семантический анализатор сообщит синтаксическому анализатору, что этот код также неверен, и парсер передаст это сообщение лексическому анализатору. Лексический анализатор скажет «ну, возможно и не было никакого второго оператора ++, возможно, должно быть что-то такое»:
x , = , j , ++ , +, + , + , 1 , ;
На что синтаксический анализатор ответит: «ага, я понял, что это такое; это два унарных оператора и оператор сложения»:
x=((j++)+(+(+1)));
А семантический анализатор ответит: «ну наконец-то! Вот с этим я могу работать».
Но мы так не поступаем. Это глупый пример, но вы должны увидеть две серьезные проблемы в таком подходе.
Во-первых, хотя в большинстве случаев лексический разбор является однозначным, в некоторых патологических случаях существует потенциально огромное множество путей разбития простой программы на лексемы. Простое определение границ лексем между пятью знаками + дает 8 вариантов; это количество увеличивается экспоненциально. И хотя в большинстве случаев лексический разбор однозначен, в случае неоднозначности пространство решения может быть просто огромным, так что лучше всегда анализировать «жадным образом» (greedy) и никогда не возвращаться назад. Если программа не проходит грамматический анализ из-за неподходящей лексической структуры лучше всегда потребовать от пользователя исправить это.
Второй серьезной проблемой является то, что в случае поиска назад невозможно определить, какой из вариантов лучше. Два из этих восьми вариантов проходят семантический анализ: один из них мы только что нашли, а вот второй: x=(j+(+(+(+(+1))))); Как определить, какой из этих двух вариантов имел в виду пользователь, когда писал это странное выражение? Помните, что мы не хотим здесь найти решение для головоломок Судоку, когда любая заданная комбинация чисел такая же бессмысленная, как и следующая; мы хотим получить IL-код, который должен означать именно то, что задумывал пользователь! Один из этих вариантов изменяет значение переменной j, а второй нет, так что между этими вариантами есть существенное различие. C# не является языком типа «догадайся, что я имел ввиду», он является языком типа «сделай то, что я тебе велел» (**). Если сказанное вами является неоднозначным, то мы должны сообщить вам об этом.
В следующий раз мы вернемся к этому разговору и посмотрим на то, что алгоритм разрешения имен (name resolution algorithm) также не использует поиск назад.
(*) В отличие от JScript. В спецификации ECMAScript говорится, что существует лексическая неоднозначность с символом /; это может быть комментарий в виде // или /* или */, или простой оператор деления, или оператор /=, или начало или окончание регулярного выражения. Кое-что из этого пересекается; в спецификации сказано, что корректный результат разбора является таким, который выдает грамматически разумную программу!
(**) Опять-таки, в отличие от JScript.