Меню
Главная
Авторизация/Регистрация
 
Главная arrow Технические arrow Информационные технологии arrow
Анализ снизу вверх и сверху вниз

Примеры

Парсинг. Попытаемся проиллюстрировать и объяснить разницу между синтаксическим анализом сверху вниз и снизу вверх на примере предложения “They are flying planes” и простой грамматики, представленной в виде пронумерованных правил:

1. S ® NP VP

2. NP ® N

3. NP ® PRO

4. NP ® ADJ N

5. VP ® VT NP

6. VT ® V

7. VT ® AUX V

8. N ® planes

9. PRO ® they

10. ADJ ® flying

11. AUX ® are

12. V ® are

13. V® flying

Синтаксический разбор сверху вниз начинается с символа S, который и будет являться вершиной дерева разбора. Эта процедура эквивалентна процедуре постановки задачи, которая заключается в том, чтобы определить, является ли последовательность слов предложением. Правило 1 гласит, что каждое предложение состоит из именной группы (NP), за которой следует глагольная группа (VP). При наличии нескольких правил, сперва применяется правило с наименьшим номером, а затем оно расширяется слева направо. Таким образом следующим шагом является нахождение первой связи, т.е. NP. Сперва активируется правило 2, а затем правило 8 (рис. 2а). Т.к. “planes” не соответствует ”they”, алгоритм срабатывает вновь, и теперь сперва активируется правило 3, а затем правило 9. Затем алгоритм возвращается к правилу 1 и следующей целью ставит определение VP. Сперва активируются правила 5, 6, а затем 12 (рис. 2b). Дальнейший ход разбора отржен на рисунке 2 (с, d, e).

Синтаксический разбор снизу вверх начинается со слов в предложении. Опять же разбор ведется слева направо, и сперва применяется правило с наименьшим номером. Итак, сначала первое слово предложения “they” соотносится с антецедентом правила 9, которое после выполнения выдает утверждение, что “they” является местоимением (PRO). Затем выполняется правило 3 и выдает, что “they” является NP. NP соответствует антецедентам правил 1 и 5, но ни одно из этих правил еще не вызвано, поэтому разбор переходит к “are”. Выполняется правило 11 (несмотря на то, что правило 12 также вызвано, оно не выполняется в соответствии с правилом о последовательности выполнения правил). Затем выполняются правила 10, 8 и 2 (рис. 3а). На данной стадии дальнейший разбор последовательности NP+AUX+ADJ+NP невозможен, поэтому мы возвращаемся к последнему вызванному, но еще не выполненному правилу, т.е. к правилу 4. Разбор последовательности NP+AUX+NP так же невозможен, поэтому опять выполняется последнее вызванное невыполненное правило. Сейчас это правило 13, которое выдает, что “flying” является V. Затем выполняются правила 6 и 5 (рис. 3с). Разбор последователльности NP+AUX+VP невозможен, поэтому выполняется правило 7 и выдает утверждение, что “are flying” является VT. Затем снова выполняются правила 5 и 1, на чем и заканчивается синтаксический разбор (рис. 3d).

Данный пример был приведен с целью сравнения механизмов синтаксического разбора снизу вверх и сверху вниз. Установление строгого порядка разбора слева направо и нумерация правил обусловлены стремлением к применению в наибольшей степени сходного алгоритма, несмотря на то, что результаты разбора оказались различными.

Системы со встроенными правилами. Рассмотрим прямой и обратный цепной анализ на примере выдуманного набора правил о том, как следует провести вечер. Правила расположены в обычном порядке, антецедент располагается слева, а следствие - справа, все вызванные правила выполняются, а разбор ведется параллельно.

  • 1. Хороший фильм по ТВ + Рано утром встреч нет ® Позднее кино
  • 2. Рано утром встреч нет + Нужно поработать ® Работа допоздна
  • 3. Нужно поработать + Необходимы документы ® Работа в офисе
  • 4. Позднее кино ® Не спать допоздна
  • 5. Работа допоздна ® Не спать допоздна
  • 6. Работа допоздна ® Возвращение в офис
  • 7. Работа в офисе ® Возвращение в офис

Например, правило 1 гласит, что если по ТВ идет хорошее кино и у меня завтра рано утром встреч нет, тогда я следую режиму “Позднее кино”.

Рассмотрим сперва пример прямого цепного анализа. Допустим, система получила начальную информацию о том, что завтра рано уторм у меня нет встреч. Активируются правила 1 и 2. Допустим, что далее система получила сообщение о том, что мне нужно поработать. Активируется правило 3, а правило 2 вызывается и выполняетя, откуда следует вывод, что я нахожусь в режиме “Работа допоздна”, в результате чего вызываются и выполняются правила 5 и 6. В итоге система заключает, что я должна вернуться в офис и не спать допоздна.

Теперь рассмотрим эту же проблему с применением обратного цепного анализа. Допустим, что система получила исходную информацию о том, что у меня нет завтра утром встреч, но мне нужно еще поработать, а затем ее (систему) спросили, следует ли мне вернуться в офис. Данный запрос активирует правила 6 и 7. В свою очередь возникнет вопрос “Работа допоздна” или “Работа в офисе”? При этом активируются правила 2 и 3, и возникает вопрос “Рано утром встреч нет”, “Нужно поработать” или “Нужны документы”? Первые два антецедента будут удовлетворены, таким образом правило 2 будет вызвано и выполнено, что повлечет за собой удовлетворение антецедента “Работа допоздна”, вызов и выполнение правила 6, в результате чего система придет к заключению, что мне следует вернуться в офис.

Обратите внимание на то, что при прямом разборе порождается больше следствий, а при обратном - запросов. Т.к. в обоих примерах использовались одни и те же данные, то в ходе анализа выполнялись одни и те же правила, но активировались различные.

 
Оригинал текста доступен для загрузки на странице содержания
< Пред   СОДЕРЖАНИЕ   След >
 

СКАЧАТЬ ОРИГИНАЛ
Анализ снизу вверх и сверху вниз