У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

Чтобы представлять, что значит правило в контекстно-свободной грамматике, их следует читать следующим образом: X--›Yкак « X может иметь вид Y», а ' X, Y' как « X, за которым следует Y». Так первое правило может быть прочитано:

предложение может иметь вид: группа_существительного, за которой следует группа_ глагола.

Все это очень хорошо, но что представляют собой группа_существительногои группа_глагола? Как мы должны распознавать подобные объекты и как узнать их грамматическую структуру? Ответы на эти вопросы следуют из второго, третьего и четвертого правил грамматики. Например,

группа_существительного может иметь вид: определитель, за которым следует существительное.

Неформально, группа существительного – это группа слов, служащая для обозначения некоторого объекта (или объектов). Такая группа содержит слово – существительное, которое определяет главный класс, которому принадлежит этот объект. Так « the man» (человек) обозначает человека, « the program» (программа) обозначает программу и так далее. Кроме того, в соответствии с приведенной грамматикой, существительному должна предшествовать группа слов, названная «определитель» (см. рис. 9.2). Аналогично, внутренняя структура словосочетания группа_глаголаописывается соответствующими правилами. Заметим, что для этого словосочетания существуют два правила. Это вызвано тем, что оно может принимать два вида. Словосочетание группа_глаголаможет содержать словосочетание группа_существительного,как в предложении «the man eats the apple»(человек ест яблоко), или группа_существительногоможет отсутствовать, как в предложении «the man sings»(человек поет).

Для чего нужны остальные правила грамматики? Эти правила показывают, как некоторые словосочетания могут быть построены из настоящих слов, а не сводят их к совокупности более мелких словосочетаний. Слова английского языка записываются в квадратных скобках, так что правило:

определитель--› [the].

можно читать так:

определитель может иметь вид: слово the.

Теперь, когда мы получили достаточно полное представление о грамматике, мы можем поговорить о том, какие последовательности слов являются грамматически правильными предложениями в соответствии с приведенной грамматикой. Наша грамматика очень проста и нуждается в целом ряде расширений. Основной недостаток заключается в том, что она допускает предложения, составленные лишь из пяти различных слов. Если мы хотим определить, является ли заданная последовательность слов предложением, в соответствии с тем, как оно определяется грамматикой, то необходимо применить первое правило, чтобы получить ответ на следующий вопрос:

можно ли разбить заданную последовательность на два словосочетания таким образом, чтобы первое из них было группа_существительного, а второе группа_глагола?

Затем, чтобы проверить, является ли первое словосочетание группой существительного, необходимо применить второе правило, которое можно интерпретировать как вопрос: можно ли разбить словосочетание на определитель и существительное, следующее за определителем?

Рис. 9.2.

И так далее. В результате этой процедуры, если она завершится успешно, мы выделим все словосочетания и их части, входящие в заданное предложение, в соответствии с тем, как они определены грамматикой, и получим структуру, подобную приведенной на рис. 9.3. Эта диаграмма, показывающая структуру разбиения предложения на словосочетания, называется деревом (синтаксического) разбора предложения.

Мы увидели, как, имея грамматику языка, можно построить деревья разбора для предложений этого языка, чтобы показать их структуру. Задача построения дерева разбора предложения по заданной грамматике называется задачей синтаксического разбора (анализа). Программа для ЭВМ, которая строит деревья разбора для предложений языка, называется синтаксическим анализатором.

В этой главе будет показано, как задача синтаксического анализа может быть сформулирована в рамках языка Пролог. Будет введен используемый в Прологе формализм грамматических правил, значительно облегчающий создание синтаксических анализаторов на Прологе. Область применения вводимых далее идей не ограничивается синтаксисом естественных языков. Действительно, те же самые методы применимы к любой задаче, объектом рассмотрения которой является упорядоченная последовательность элементов, которая некоторым естественным образом может быть разбита на группы, а порядок этих групп может быть определен множеством правил. Однако, ради простоты, в оставшейся части этой главы будет рассматриваться задача синтаксического анализа предложений на английском языке, а обобщение изложенных далее идей и методов на другие области предоставляется читателю.

предложение

Рис. 9.3.

Основная структура данных, о которой идет речь при обсуждении задачи синтаксического анализа, представляет последовательность слов. Предполагается, что можно выделить подпоследовательности этой структуры, представляющие различные словосочетания, допустимые грамматикой, и, основываясь на этом, показать, что последовательность в целом допустима в качестве словосочетания типа предложение. Так как стандартным способом представления последовательности является список, то входные данные для синтаксического анализатора будут представлены как список языка Пролог. А какое же представление имеют сами слова? Для решаемой здесь задачи знание внутренней структуры слов представляется несущественным, так как все, что необходимо делать,- это сравнивать слова друг с другом. Поэтому естественно представлять слова как атомы языка Пролог,

Давайте разработаем программу, позволяющую определять, является ли заданная последовательность слов предложением в соответствии с приведенной выше грамматикой. Для того чтобы сделать это, программа будет должна выявить внутреннюю структуру заданных ей предложений. Далее будет показано, как разрабатывать программу, которая запоминает эту структуру и делает ее доступной для обозрения, но здесь этот вопрос не будет рассматриваться, чтобы не усложнять программу. Так как программа проверяет, является ли некоторая последовательность слов предложением, то давайте определим предикат предложение. Этот предикат использует лишь один аргумент и соответствует следующему утверждению: