Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 286
Текст из файла (страница 286)
открытыми классами. Другие категории (местоимения, артикли, предлоги и союзы) называются сх закрытыми классами. Они включают небольшое количество слов (от нескольких слов до нескольких десятков слов), которые можно Глава 22. Общение 1055 в принципе перечислить полностью. Состав закрытых классов изменяется на про- тяжении столетий, а не месяцев. Например, местоимения "(Ьее" и ВЬоц" широко использовались в английском языке в ХЧН веке, затем в Х1Х веке их частота пошла на убыль, а в наши дни они встречаются только в поэзии и в некоторых диалектах. Грамматика языка Ео На следующем этапе необходимо обеспечить объединение слов в словосочетания. Мы будем использовать пять нетерминальных символов для определения словосочетаний различных типов: предложение (Беп(епсе — Я), именное словосочетание (]х]оцп РЬгазе — МР), глагольное словосочетание (ЧегЬ РЬгазе — (гр), пре)ьчожное словосочетание (Ргероз](1опа1 РЬгазе — РР) и относительное предложение' (Ве1а(!уе С1ацзе — пе2С2аиае).
Грамматика языка сп приведена в листинге 22.3, где для каждого правила полстановки показан пример. Грамматика сп вырабатывает допустимые английские предложения, например, такие, как показаны ниже. .топо йе йп сне рье Тце ьпзтрцв Сваг вг1пхв 1в зп (2,2] Магу йв йп Вовеоп апс) цонп вг1п)св Листинг 22.3. Грамматика языка Еп с примерами словосочетаний, иллюстрирующих каждое правило  — гМ ГР в сопэцпссйоп В МР -г Р УР— + (Г РР -Ч Ргероззгйоп МР ле1С1 е -+ Ецас у К сожалению, эта грамматика не только производит приемлемые предложения, но и допускает 'ж перепроизводство, т.е, производит предложения, которые не являются грамотными, такие как "Ме до Воз(оп" и "! з пе!1 рй Во!д туцшрцз по[!йпй еав(".
Кроме того, эта грамматика допускает 'са недопроизводство — она отвергает многие ' Относительное предложение следует зв именным словосочетанием и модифицирует его. Относительное предложение состоит из относительного местоимения (такого как "зчйо" (кто) или "Фа(" (что)), за которым следует глагольное словосочетание (еще одна разновидность относительного предложения рассматривается в улр. 22.12). Примером относительного предложения явяяется конструкция чьаг з(1пхз*' в предложении "тйе вчппрцз рйаг вйпхз !з!и !2,21" (Вампус, который испускает неприятный запах, находится в квадрате (2,2]). гопоцп Мате Моин Агейсзе Моин рйдзс р'сзс МР РР МР Яе2С2аиее егЬ УР МР (гР Ас(бесед ие (гР РР УР Ас(ггегЬ 1 + гее1 а Ьгеезе 1 Гее1 а Ьгеезе + апс) + 1 вте11 а ицтрце 1 Зоип рйсв Сне + ьпдпрця 3 4 СЬе иотрцв + Со Сне еаеп сне ыцтрцв + спас гв вте11у в пылка гее1 + а Ьгеезе ьв + яте11у гцгп е со сне еавс по ь анеас) Со + Сне еаве Сиае + 1в вгпе11у 1056 Часть згП.
Общение, восприятие и осуществление действий правильные английские предложения, такие как "! [Рдп)с [)зе зчпгпрпз )з згпе!!у". [Еше одним недостатком этой грамматики является то, что она не обеспечивает запись первого слова предложения с прописной буквы или добавление точки в конце. Это связано с тем, что данная грамматика предназначена в основном для устной, а не письменной речи.) 22.3. СИНТАКСИЧЕСКИЙ АНАЛИЗ (СИНТАКСИЧЕСКИЙ РАЗБОР) Выше в этой главе уже было дано определение синтаксического анализа как процесса поиска дерева синтаксического анализа для данной конкретной входной строки. Это означает, что вызов функции синтаксического анализа Рагэе, такой как Расее[ "С[зе кадиров зв деад", Ею Я) должен привести к получению дерева синтаксического анализа с корнем Я, листьями которого являются слова "[)зе зчпгпрпз [з деад", а внутренними узлами — нетерминальные символы грамматики сь.
Такое дерево показано на рис. 22.1. В виде линейного текста это дерево может быть записано следующим образом: [ьп [иР: [Аге1с1е: Ене![ггопп: мьнпрпв]] [ кР: [[гегь: з.в) [Аддессзие: деад!)! с[у Синтаксический анализ может рассматриватьсл как лрапесс поиска дерева синтаксического анализа. Существуют два крайне противоположных способа задания соответствующего пространства поиска [а также множество промежуточных вариантов таких способов).
Во-первых, можно начать с символа Б и искать дерево, листьями которою являются соответствующие слова. Такой способ называется ж нисходящим синтаксическпи анализом (поскольку символ Я изображается в верхней части рисунка, на котором показано дерево, повернутое корнем вверх). Во-вторых, можно начать со слов и выполнять поиск дерева с корнем о. Такой метод называется 'в. восходяпоьм синтаксическим анализом'-. Нисходящий синтаксический анализ может быть точно определен как задача поиска в соответствии с приведенным ниже описанием.
° Начальное состояние представляет собой дерево синтаксического анализа, состоящее из корня Я и неизвестных дочерних узлов: (~: ?]. Вообще говоря, каждое состояние в пространстве поиска также представляет собой дерево синтаксического анализа. ° Функция определения преемника выбирает в дереве самый левый узел с неизвестными дочерними узлами. Затем в грамматике осуществляется поиск правил, которые имеют корневую метку узла, находящегося в левой части.
Для каждого такого правила создается состояние-преемник, в котором символ ? заменяется списком, соответствующим правой части правила. Например, в грамматике се имеются два правила для Я, поэтому дерево (Я: ? ] должно быть заменено следующими двумя преемниками: - Читатель может заметить, что нисходящий и восходящий синтаксический анализ аналогичен прямому и обратному формированию логических рассуждений соответственно, как описано в главе 7 Вскоре будет показано, что эта аналогия является полной. Глава 22.
Общение 1057 [Я: [Я: ?) (сопуипссхоп: ?1 [ан ?] ] (ьп [ьгд: ?] (ьп: ?1] Второй из этих преемников имеет семь преемников, по одному для каждого правила подстановки ИР. ° В проверке цели проверяется, какие листья дерева синтаксического анализа точно соответствуют входной строке, без неизвестных и неохваченных входных данных. Одна существенная проблема при нисходящем синтаксическом анализе возникает, когда приходится сталкиваться с так называемыми леворекурсивными правилами, т.е, правилами в форме х — >х.... При поиске в глубину применение такого правила может привести к тому, что замена х на [х: х...1 будет осуществляться в бесконечном цикле.
А при поиске в ширину можно будет успешно найти варианты синтаксического анализа для допустимых предложений, но при наличии недопустимого предложения может возникнуть такая ситуация, что программа не сможет выйти из бесконечного пространства поиска. Ниже приведено описание восходящего синтаксического анализа как задачи поиска. ° Начальным состоянием является список слов во входной строке, где каждое из слов рассматривается как дерево синтаксического анализа только с одним листовым узлом, например [еЬе,мшария,ха,йеает]. Вообще говоря, каждое состояние в пространстве поиска представляет собой список деревьев синтаксического анализа. ° С помощью функции определения преемника выполняется поиск в каждой позиции з списка леревьев и в каждой правой части правила грамматики.
Если подпоследовательность списка деревьев, начинающаяся с з, согласуется с правой частью, то эта подпослеловательность заменяется новым деревом, категорией которого является левая часть правила, а дочерними узлами — эта подпоследовательность. Под "согласованием" подразумевается, что категория узла является такой же, как и элемент в правой части. Например, правило Ахезс1е — эа]зе согласуется с подпоследователЬНоетЬю, соетОяШЕй из первоГО узла в списке [еЬе,заварив, ха,йеай), поэтому состоянием-преемником становится [ [Атсдс2е: еье),ъпцарцв, ха, беай). ° В проверке цели проверяется наличие состояния, представляющего собой единственное дерево с корнем Я. Пример восходящего синтаксического анализа приведен в табл. 22.2. И нисходящий, и восходящий синтаксический анализ может оказаться неэффективным из-за того, что отдельные этапы синтаксического анализа различных сочетаний могут комбинироваться самыми разными способами.
И в той и в другой процедуре могут возникать непроизводительные затраты времени, связанные с поиском в тех частях пространства состояний, которые не позволяют получить требуемый результат. При нисходящем синтаксическом анализе иногла создаются промежуточные узлы, которые так и не удастся связать со словами, а при восходящем синтаксическом анализе создаются частичные фрагменты синтаксического анализа слов, которые невозможно преобразовать в корневой узел Ы.
Часть ЪЧ!. Общение, восприятие и осуществление действий 1058 Таблнпа 22.2. Трассировка восходящего синтаксического анализа строки "Тйс нчпирщ Н осад". Работа начинается со списка узлов, состоящего из отдельных слов. После этого происходит замена подпослсдоватсльносгей, соответствующих правой части правила, новым узлом, корнем которого является левая часть правила. например, в третьей строке показано, как узлы Агсзс1е и нопп заменяются узлом нр, для которого эти два узла являются дочерними. Нисходящий синтаксический анализ приводит к выработке аналогичной трассировки, но в пративополоащом направлении Этап Список узлов Подпослсдовагсльносгь Правило 1пй ЕЬе мнирня Ьв деай ЕЬе Атсзсзе †>еье Ноип -гнпюрпв МР— г Ат с з с1 е нсиа ИетЬ вЂ >ья Адэестзче-зйеай УРз ЪетЬ ГГР— >ГГРАдэестз е з — г нР РР 2 Атгдсзезпзюрпв ьв деад мнлзрпв 3 Ат СЗ с1 е но оп ба йеад 4 ИРЬв деад 5 нР Четь йеад 6 нРиетьАддессзче 7 ИР РРАсуестдче 3 ИР ГГР Оса! Ать д сз е Но ил йеай ггегЬ ГГР Аду ес С З ие ИР ГГР Но даже если бы существовала идеальная эвристическая функция, позволяющая осуществлять поиск без ненужных отступлений, эти алгоритмы все равно были бы неэффективными, поскольку для некоторых предложений количество деревьев синтаксического анализа измеряется экспоненциальной зависимостью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
