Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 288
Текст из файла (страница 288)
Алгоритмы, которые действуют слева направо и предотвращают формирование таких невозможных составляющих, называются синтаксическими анализаторами по 'в. левому углу, поскольку они формируют дерево синтаксического анализа, начинающееся с начального символа грамматики и продолжающееся вниз к самому левому слову предложения (к левому углу). Ребро добавляется к диаграмме, только если оно может послужить для продления этого дерева синтаксического анализа (соответствующий пример приведен на рис.
22.4). ир Ле/С!лизе чве Ьохяе Каче Тве пйе пав члы Рис. 22.4. Алгоритм синтаксического анализа но левому углу позволяет предотвратить предсказание словосочетания чв, начинаюи)егося со слова "пде", но предсказывает словосочетание цв, начинающееся со слова "шах", посколысу в данной грамматике допускается наличие словосочетания хгв, которое следует за нж Треугольник, показанный над словами зйе Боте даче" (на которую пустилось эта лошадь), означает, что для этих слов был сделан синтаксический анализ, который показал, что они представляют собой относительное предложение вехс1ацве, но дополнительные промежуточные составляющие этого синтаксического анализа не показаны Этот диаграммный синтаксический анализатор характеризуется только полиномиальными затратами времени и пространства. Он требует о()сп') пространства для хранения ребер, где и — количество слов в предложении, а )с — константа, которая зависит от грамматики.
Если алгоритм не может продолжать дальнейшее формирование ребер, он останавливается, поэтому известно, что работа данного алгоритма всегда завершается (даже при наличии леворекурсивных правил). В действительно- 1064 Часть УП. Общение, восприятие и осуществление действий сти он требует времени 0(и') даже в наихудшем случае, а это — самые лучшие показатели, которые могут быть достигнуты при использовании контекстно-свободных грамматик. Узким местом алгоритма с]гакс-Рагве является процедура ехсеис]ег, которая должна предпринять попытку продления каждого из 0(и) неполных ребер, оканчивающихся в позиции т', с помощью каждого из 0(и) полных ребер, начинающихся с позиции з, для каждого из и+1 различных значений тх Перемножая эти числа, получаем значение 0(п').
Полученные результаты довольно парадоксальны — как может алгоритм с затратами времени 0(и') возвратить ответ, в котором может содержаться экспоненциальное количество деревьев синтаксического анализа? Рассмотрим один пример; следующее предложение: Ра11 1еачев Еа11 апс] вркьпд 1еачев вркьпд является неоднозначным, поскольку в нем каждое слово (кроме "апг]") может быть либо существительным, либо глаголом, а 'Та!1" и "зрг]пя" могут быть также прилагательными. В целом этому предложению могут соответствовать четыре приведенных ниже варианта' синтаксического анализа.
[гп [ьч [в[Р: ва11 1еачев] еа11] апе( [гп [г(Р. "вркхпд 1еачев] врк1пд) [ьч [я: [в[Р: Ра11 1еачев) еа11] апе[ [ьч врвьпд [(гР: 1еачев вркхпд]1 [гп [гп Ра11 [(гР: 1еачев еа11]) апй [ьч [л[Р: врк1пд 1еачев] вркьпд] [ьч [ьч Ра11 [(гР: 1еачев еа11]] апе( [ьч вркхпд [РР: 1еачев вркхпд]1 Если имеется и неоднозначных сочетающихся друг с другом фрагментов предложения, то может быть предусмотрено 2" способа' выбора вариантов синтаксического анализа для этих фрагментов предложения. Как избежать экспоненциального роста затрат времени на обработку при использовании данного алгоритма диаграммного синтаксического анализатора? По сути на этот вопрос можно дать два ответа. Первый ответ состоит в том, что сам алгоритм С]загс-Рагве фактически представляет собой не синтаксический анализатор, а распознаватель. Если в диаграмме имеется полное ребро в форме [О, п, Š— э а ° ), это означает, что какое-то словосочетание Я распознано.
Восстановление дерева синтаксического анализа из информации, заданной в этом ребре, не рассматривается как часть функций алгоритма С]таксРагве, но может быть выполнено с его помощью. Обратите внимание на то, что в последней операции процедуры ехсеис[ек строка а формируется как список ребер е„а не просто как список имен категорий. Поэтому, чтобы преобразовать ребро вдерево синтаксического анализа, достаточно выполнить рекурсивный просмотр составляющих ребер, преобразовав каждое ребро [Е, з',х -э а ° ] в дерево [Х: а]. Такой процесс является несложным, но позволяет получить только одно дерево синтаксического анализа. Второй ответ состоит в том, что если требуются все возможные варианты синтаксического анализа, то придется глубже разобраться в этой диаграмме.
Во время преобразования ребра [Е, т', х — + а ° ] в дерево [х: а] можно будет проверить, есть ли какие-либо другие ребра в форме [ Е, з', х — т [з ° 1. Если они имеются, то эти з Вариант синтаксического анализа [ьч Ра11 [(гР: 1еачев еа11] ] эквивалентен предложению? Ашшпл вьандолз авнпнл" (Осень покидает осень).
е Может возникнуть также о(п! ) неоднозначных вариантов, связанных с тем способом, как компоненты соединяются друг с другом, например (хи (у н г)) нлн ((х и у) н г). Но это — другая проблема, которая весьма успешно исследована в [256]. 1065 Глава 22. Общение ребра должны сформировать дополнительные варианты синтаксического анализа.
Определив все эти варианты, необходимо будет продумать вопрос, что с ними делать. Можно просто перечислить все варианты, а это означает, что указанный выше парадокс будет разрешен и потребуется экспоненциальное количество времени для составления списка всех вариантов синтаксического анализа.
Еще один подход может состоять в том, чтобы еше немного продолжить эту работу н представить варианты синтаксического анализа в виде структуры, называемой Ъ. упакованным лесом, который выглядит примерно так: [ЛГР: Ра11 1еачев)[иР: Еа11) [ГГР: Ра11][ирз 1еа ев Еа11]) [ГГР: вркЕпд 1еачев)[[гР: вркьпд] [ггР: врхзпд)[иР: 1еачев вркхпд]) Идея этого способа представления состоит в том, что каждый узел дерева синтаксического анализа может быть либо обычным узлом дерева, либо множеством узлов дерева. Это позволяет возвратить из программы некоторое представление экспоненциального количества вариантов синтаксического анализа за счет полиномиальных затрат пространства и времени. Безусловно, если п=2, то разницы между 2" и 2п нет, но при больших значениях и такое представление обеспечивает значительную экономию.
К сожалению, этот простой подход на основе упакованного леса не позволяет учесть все о [и ) ] вариантов неоднозначности, касающиеся того, как могут быть связаны между собой различные составляющие. Максвелл и Каплан [1002[ показали, что некоторый более сложный способ представления, основанный на принципах систем поддержки истинности, позволяет упаковывать деревья еше плотнее. 22.4.
РАСШИРЕННЫЕ ГРАММАТИКИ Как было показано в разделе 22.2, простая грамматика для языка бс производит предложение "1 япе1! а згепсй" (Я чувствую неприятный запах) и много других предложений на английском языке. К сожалению, она производит также много словосочетаний, не являюшихся предложениями, таких как "Ме япе)! а згепс)[". Для предотвращения этой проблемы в этой грамматике нужно было бы учесть, что слово "те" не является допустимым словосочетанием г)Р при его использовании в качестве подлежащего некоторого предложения. Как говорят лингвисты, местоимение "Г' находится в именительном падеже, а "гпе" — в объектном падеже'.
После того как учтено наличие падежа, становится очевидно, что грамматика Б, не является контекстно- свободной, поскольку нельзя утверждать, что любое словосочетание в)Р эквивалентно любому другому независимо от контекста. Этот недостаток можно исправить, ВВЕДЯ НОВЫЕ КатЕГОРИИ, таКИЕ КаК ДГРв И ВГР„ ДЛЯ ОбОЗНаЧЕНИЯ ИМЕННЫХ СЛОВОСОЧЕтаний в именительном и объектном падеже соответственно. Для этого также потребу- ЕТСЯ РаЗДЕЛИтъ КатЕГОРИЮ МЕСтОИМЕНИй РПОПОиП На ДВЕ КатЕГОРИИ вЂ” Рхаипиив (которая включает "Г) и . копоип, (которая включает "те").
В верхней части лис- ' Именительный падеж иногда называют также яомвнатявяым ладелсом, а объектный падеж— еяляглельным падежом. Во многих языках имеется также дательный падеж для слов в позиции косвенного объекта. 1066 Часть У!!. Общение, восприятие и осуществление действий тинга 22.5 показана полная грамматика В(чГ, подготовленная с учетом соглашения о падеже; мы будем называть полученный в результате язык Е,. Обратите внимание на то, что пришлось продублировать все правила ир, введя ОДНО пРавило для ир„ а другое — для ир,. Листинг 22.5.
Варианты представления грамматики. В верхней части показана грамматика В)ЧР для языка Е„п котором учитываются именительный н объектный падежи в именных оловосочетаннях н поэтому не допускается такое суп(еотвенное перепроизводство, как в языке Ео. Части грамматики, ндентнчные грамматике Е„были исключены. В нижней части показана грамматика определенных выражений (Рейпйе С1аняе бгапипаг — ВС6) языка Е, — ь ирл гу 1 -+ Ряолоило ( Иаюе ( Иоил — э Ряопоипо ( иаме ! иоип — > УР ИРо †) Ряерояз'.с!оп иРо -) х ! уои ! Ье ( пЬе †> ве ( уои ( Ьып ! Ьек ( ае Иро ИРо )ГР Ряолоипя Ргопоипо ИР(лиЬ)есезке) (Р Ряопоип(саяе) ( Инее ! Иоил УР ИР(ОЬУесгз'.ие) Ряероях своп ИР(ОЪзесехие) уои ! Ье ! пЬе юе ( уои ) Ьью ) Ьек ! ас Я вЂ” Ф ИР(саяе) УР -+ РР— > Ряопоип(яиьуессхие) Ряопаил(оьуессзие) К сожалению, язык Е, все еше допускает перепроизводство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
