РАСШИРЕННЫЕ ГРАММАТИКИ
Именительный падеж иногда называют также номинативным падежом, а объектный падеж — винительным падежом. Во многих языках имеется также дательный падеж для слов в позиции косвенного объекта.
Как было показано в разделе 22.2, простая грамматика для языка ?0 производит предложение "I smell a stench" (Я чувствую неприятный запах) и много других предложений на английском языке. К сожалению, она производит также много словосочетаний, не являющихся предложениями, таких как "Me smell a stench". Для предотвращения этой проблемы в этой грамматике нужно было бы учесть, что слово "те" не является допустимым словосочетанием NP при его использовании в качестве подлежащего некоторого предложения. Как говорят лингвисты, местоимение "I" находится в именительном падеже, а "те" — в объектном падеже7. После того как учтено наличие падежа, становится очевидно, что грамматика ?0 не является контекстно-свободной, поскольку нельзя утверждать, что любое словосочетание № эквивалентно любому другому независимо от контекста. Этот недостаток можно исправить, введя новые категории, такие как NPS И NP0, ДЛЯ обозначения именных словосочетаний в именительном и объектном падеже соответственно. Для этого также потребуется разделить категорию местоимений Pronoun на две категории— Pronouns (которая включает "I") и Ргопоищ (которая включает "те"). В верхней части листинга 22.5 показана полная грамматика BNF, подготовленная с учетом соглашения о падеже; мы будем называть полученный в результате язык ?г. Обратите внимание на то, что пришлось продублировать все правила NP, введя одно правило для NPS, а другое — для NP0.
Листинг 22.5. Варианты представления грамматики. В верхней части показана грамматика BNF для языка 5i, в котором учитываются именительный и объектный падежи в именных словосочетаниях и поэтому не допускается такое существенное перепроизводство, как в языке ?0. Части грамматики, идентичные грамматике 50, были исключены.
К сожалению, язык Ј± все еще допускает перепроизводство. В английском и многих других языках требуется согласование между подлежащим и основным глаголом предложения. Например, если подлежащим является "I", то предложение "I smell" является грамматически правильным, a "I smells" — нет. Если же подлежащим является "it", то верно противоположное. В английском языке различия, обусловленные согласованием, являются минимальными: большинство глаголов имеют одну форму для подлежащего, представляющего собой местоимение третьего лица в единственном числе ("he", "she" или "it"), и вторую форму для всех других комбинаций лица и числа. Есть только одно исключение: словосочетания "I am / you are / he is" имеют три формы. Умножая эти три разные формы на две разные формы NPS и NP0, получим шесть форм NP. Если бы количество различий было еще больше, то в конечном итоге общее количество вариантов выражалось бы экспоненциальной зависимостью.
Альтернативный подход состоит в том, что необходимо расширить существующие правила грамматики, а не вводить новые правила. Вначале приведем пример того, как могли бы выглядеть расширенные правила (см. нижнюю часть листинга 22.5), а затем формально определим способ интерпретации этих правил. Расширенные правила допускают применение параметров в нетерминальных категориях. В листинге 22.5 показано, как описать грамматику ?г с использованием расширенных правил. Категории NP и Pronoun имеют параметр, обозначающий их падеж. (Существительные не имеют падежа в английском языке, но имеют его во многих других языках.) В правиле для s словосочетание NP должно находиться в именительном падеже, тогда как в правилах для VP и РР словосочетание NP должно находиться в объектном падеже. Правило для NP принимает в качестве параметра некоторую переменную, case. Назначение этой конструкции состоит в том, что словосочетание NP может иметь любой падеж, но если вместо этого словосочетания NP подставляется местоимение Pronoun, то последнее должно иметь такой же падеж. Применение переменных, позволяющее исключить необходимость принятия решения, когда различие, определяемое переменной, не имеет значения, способствует тому, что не приходится увеличивать размер множества правил в экспоненциальной зависимости от количества рассматриваемых характеристик.
Используемая для такого дополнения формальная система называется грамматикой определенных выражений, или сокращенно DCG (Definite Clause Grammar), поскольку каждое правило этой грамматики можно интерпретировать как определенное выражение8 в хорновской логике. Вначале мы покажем, как можно интерпретировать в качестве определенного выражения обычные, нерасширенные правила. Мы будем рассматривать каждый символ с обозначением категории как предикат, заданный на строках, поэтому выражение NP(s) принимает истинное значение, если строка s образует некоторое словосочетание NP. Следующее правило CFG:
s -» NP VP
является сокращенным обозначением для следующего определенного выражения:
iVP(si) л VP(s2) => 5(si+s2)
Здесь Sx+s2 обозначает конкатенацию двух строк, поэтому данное правило говорит о том, что если строка s1 представляет собой словосочетание NP, а строка s2 — словосочетание VP, то их конкатенация представляет собой словосочетание S; это означает, что данная интерпретация точно соответствует тому, как мы уже интерпретировали это правило CFG. Важно отметить, что грамматика определенных выражений позволяет рассматривать синтаксический анализ как логический вывод. Такой подход открывает возможность рассуждать о языках и строках с помощью многих разных способов. Например, он означает, что восходящий синтаксический анализ можно осуществлять с помощью прямого логического вывода, а нисходящий синтаксический анализ — с помощью обратного логического вывода. Как будет показано ниже, это также означает, что одна и та же грамматика может использоваться и для синтаксического анализа, и для производства новых предложений.
Но самым важным преимуществом подхода на основе DCG является то, что он дает возможность дополнять символы категорий вспомогательными параметрами, отличными от обычных строковых параметров. Например, следующее правило:
NP(case) —> Pronoun(case)
является сокращенным обозначение для такого определенного выражения:
Pronoun(case, si) => NP{case, si)
Это правило гласит, что если строка s1 представляет собой местоимение Pronoun с падежом, указанным переменной case, то sx также представляет собой словосочетание NP с тем же падежом. Вообще говоря, символ категории может быть
дополнен любым количеством формальных параметров, а сами формальные параметры могут заменяться фактическими параметрами, подлежащими унификации, как в обычном логическом выводе с использованием хорновских выражений.
Но за такое удобство приходится платить: в распоряжение составителя грамматики передается все мощь системы автоматического доказательства теорем, поэтому приходится отказываться от гарантированного выполнения синтаксического анализа за время О (л3); задача синтаксического анализа грамматики с расширениями может оказаться NP-трудной или даже неразрешимой, в зависимости от этих расширений.
Для того чтобы обеспечить применение грамматики DCG, необходимо воспользоваться еще несколькими приемами; например, требуется способ задания терминальных символов, кроме того, было бы удобно иметь возможность не вводить автоматический строковый параметр. Учтя все эти пожелания, авторы решили, что нужно задать грамматику определенных выражений как описано ниже.
• Запись X —> Y Z ... должна быть преобразована в запись V(si) л Z(s2) л ... => X(Si+s2+...).
• Запись х —> Y | Z | ... должна быть преобразована в запись Y(s) v Z(s) v ... => x(s).
• В том и в другом приведенном выше правиле любой нетерминальный символ Y может быть дополнен одним или несколькими параметрами. Каждый параметр может представлять собой переменную, константу или функцию от некоторых параметров. После перевода в форму определенного выражения эти параметры должны предшествовать строковому параметру (например, терм NP(case) переводится в форму NP (case, Si)).
• Запись {Р (...) } может появляться в правой части правила и буквально переводится в Р (...). Это позволяет составителю грамматики вставлять проверку для терма Р (...) без необходимости добавления автоматического строкового параметра.
• Запись X —> word переводится как х( [ word] ).
Проблему согласования подлежащего и глагольного сказуемого также можно решить с помощью дополнений, но мы отложим эту задачу до упр. 22.2. Вместо этого решим более сложную задачу, такую как субкатегоризация глагола.