9.2. Описание синтаксического анализа на языке Пролог

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

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

предложение(Х) означает, что X является последовательностью слов, образующей грамматически правильное предложение.

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

?- предложение ([the, man, eats, the apple]).

Ответом на этот вопрос будет «да», если «the man eats the apple» является предложением, и «нет» в противном случае.

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

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

группа_существительного(Х) означает, что последовательность X является группой существительного. Аналогично, группа_глагола(Х) значит, что последовательность X является группой глагола.

Используя эти предикаты, мы можем дать определение предиката предложение. Последовательность X является предложением, если ее можно разбить на две подпоследовательности Y и Z, где Y – это группа_существительного, Z – группа_глагола. Так как мы представляем последовательности как списки, то у нас уже есть предикат присоединить, выполняющий разбиение списка на два других. Таким образом, можно записать:

предложение(Х):-присоединить(Y,Z,Х), группа_существительного(Y), группа_глагола(Z).

Аналогично

группа_существительного(Х):- присоединить(Y,Z,Х), определитель(Y), существительное(Z).

группа_глагола(Х):- присоединить(Y,Z,Х), глагол(Y), группа_существительного(Z).

группа_глагола(Х):- глагол(Х).

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

определитель([the]).

существительное([аррlе]).

существительное([man]).

глагол([eats]).

глагол([sings]).

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

предложение(Х):- присоединить(Y,Z,Х), группа_существительного(Y), группа_глагола(Z).

и следующий вопрос:

?- предложение([the, man, eats, the, apple]).

Переменная X в правиле конкретизируется значением [the, man, eats, the, apple], а переменные Yи Z не будут конкретизированы, так что данная цель будет порождать возможные пары значений для Y и Z такие, что результат присоединения списка Z к списку Y равен X. С помощью механизма возврата будут порождены все возможные пары, по одной при каждом возврате. Цель группа_ существительного будет выполняться лишь при условии, что Y действительно приемлем как группа_существительного. Иначе она не выполняется и присоединить будет вынужден найти другое значение для Y. Так что последовательность выполнения первой части предиката предложение будет следующей:

1. Целью является предложение(thе, man, eats, the, apple]).

2. Разбиение исходного списка на два списка Y и Z. Возможны следующие варианты разбиения;

Y = [], Z = [the,man,eats,the,apple] Y = [the], Z = [man,eats,the,apple]

Y= [the,man], Z = [eats,the,apple]

Y= [the,man,eats], Z = [the,apple]

Y= [the,man,eats,the], Z = [apple]

Y= [the, man, eats, the, apple], Z = []

3. Выбор варианта значений для Y и Z из приведенного выше списка вариантов и проверка принадлежности Y классу группа_существительного. То есть, попытка согласования подцели группа_существительного(Y).

4. Если группа_существительного выполняется для Y, то перейти к группа_глагола. Иначе возвратиться к шагу 3 и попробовать другой вариант.

Очевидно, что при таком подходе выполняется совершенно ненужный поиск. Цель присоединить(Y,Z,X) порождает множество решений, большая часть которых бесполезна и не может быть идентифицирована как группа существительного. Должен существовать более прямой путь получения решения. Как следует из нашей грамматики, группа_существительного должна содержать в точности два слова. Этим можно было бы воспользоваться, чтобы не прибегать к поиску среди возможных вариантов разбиения исходной последовательности слов. Опасность заключается в том, что это не всегда так, если мы изменяем грамматику. Даже небольшое изменение в правиле для определитель могло бы повлиять на возможную длину группы существительного, а значит и на способ идентификации группы существительного. При разработке программы было бы хорошо сохранять некоторую модульность. Если мы хотим изменить одно утверждение, то это не должно вызывать изменение программы в целом.