Сверху вниз и снизу вверх. Часть II

UPDATE 10-10-2010:
Cм. также
Оптимистический и пессимистический взгляд на жизнь
Сверху вниз и снизу вверх. Часть I
BFS and DFS - поиск в ширину и глубину Сверху вниз и снизу вверх. Часть III (продолжение)
END OF UPDATE.
UPDATE 17-10-2010:
Testing first - сначала тестировать Сверху вниз и снизу вверх. Часть IV
END OF UPDATE

Примеры использования этих подходов в программировании.
2. Parsing - синтаксический анализ

Парсинг (синтаксический анализ) - это процесс анализа входящей последовательности (такой как чтение с файла или клавиатуры) для определения её грамматической структуры. Этот метод используется в анализе как естественных так и компьютерных языков, как, например, в компиляторе.

Синтаксический анализа снизу-вверх - это стратегия анализа неизвестных отношений данных, которая пытается найти самый фундаментальные единицы, сначала, а затем вывести из них структуру высшего порядка. Парсер сверху-вних, с другой стороны, выдвигает в качестве гипотезы структура общего дерева разбора а затем, рассматривает, подходят ли известные фундаментальные структуры под гипотезу.

Пример парсера снизу-вверх Все мы помним как мы разбирали в школе предложение. Возьмём в качестве примера английское предложение "I love you". Сначала мы находим подлежащее и сказуемое, это наши фундаментальные единицы, а затем остальные члены предложения. В английском языке подлежащие обычно первое слово. В нашем примере, подлежащие это "I" - я. Сказуемое в английском языке, следует сразу или почти сразу после подлежащего. И действительно, "love" - люблю. Слово "you" после сказуемого, значит оно не в именительном падеже, и действительно люблю "кого? что?" тебя (you). You это дополнение.

Пример парсера cверху-вниз Я разберу это же предложение "I love you", только другим способом. В любом языке его структура задаётся некоторой грамматикой. Например, языки программирования, обычно задаются некоторым подмножеством контекстно-независимой грамматики. Что это такое в точности находится, к сожалению, за рамками этой заметки... Вернёмся, к нашему примеру. Обозначим П - подлежащие, С- сказуемое, В - второстепенный член предложение. Мы выдвигаем гипотезу, что правильный разбор будет выглядеть как "ВПС". Проверим, так ли это. "I" в качестве второстепенного члена предложения, вряд ли, было бы "me" или что-то в этом роде, но посмотрим дальше. "Love" в качестве подлежащего, может быть (Love это ещё и любовь как существительное). "You" в качестве сказуемого, это вряд ли. Итак, наше гипотеза говорит о том, что речь идёт о Love (любви), которую "You" (ты)... Ну, бред получается. Или по-научному, мы пришли к противоречию, значит, выдвинутая гипотеза была не верна... Попробуем схему "ПВС". Итак, речь идёт о I (обо мне). Второстепенный член предложения - love (любовь) и я что делаю? ты (you). Опять не-то... Пробуем схему "ПСВ". Подлежащие - I (я), сказуемое love (люблю), второстепенный член предложения - you (тебя).

Другой пример совсем кратко. Вы пишите математическое выражение, например )23+)*5. Что такое? Не можете прочитать, что я написал? Правильно, потому что это неправильно сформированное выражение. А как проверить это? Есть два подхода:
Подход снизу вверх Находим наиболее фундаментальные элементы - это скобки. Ба, у нас две закрывающих скобки и ни одной открывающей. Значит выражение неправильно сформированное.
Подход сверху-вниз В формированном выражении скобки задаются формальным языком L = {aⁿ(0|1|2|3|4|5|6|7|8|9|+|-|*|/)*bⁿ}, где а - открывающиеся скобка, b - закрывающиеся скобка, * перед b - это звезда Клини. Примеры, слов которые принадлежат этому языку: (), (2), ((2+3)) и т.д. Подчеркну, я рассматриваю здесь правильность выражение только по отношению к правильно расставленным скобкам. В этом контексте выражение (2) верно. Очевидно, что )23+)*5 не принадлежит к этому языку. В самом деле, чему должно равняться n? C одной стороны, оно должно быть 0, так как нет, не одной открывающейся скобки, но с другой - оно должно быть два, так как есть 2 закрывающиеся скобки. Эти числа должны быть равны. Но 0 не равно 2. Значит выражение )23+)*5 не принадлежит к языку L, определённому выше.

В следующих постах будет рассмотрены различные варианты применения этих подходов на примере:

3. BFS and DFS exploration - Поиск в ширину и глубину.
4. Testing first - Сначала тестировать.
5. Note first - Сначала писать комментарии.

UPDATE 10-10-2010:
Продолжение следует.
END OF UPDATE.