Программирование на языке пролог

Клоксин У.

Представляется важной возможность использования дополнительных аргументов для возврата дерева разбора, являющегося результатом синтаксического анализа. В главе 3 было показано, как можно представить деревья в виде структур Пролога. Здесь это будет использовано при расширении синтаксического анализатора с целью включить в него построение дерева разбора. Польза деревьев синтаксического разбора в том, что они дают структурное представление предложения. Удобно писать программы, которые обрабатывают эти структурные представления подобно тому, как обрабатывались арифметические формулы и списки в гл. 7. Новая программа для грамматически правильного предложения, такого например, как

The man eats the apple.

строит в качестве

результата структуру вида:

предложение(

группа_существительного(

определитель(thе), существительное(man)),

группа_глагола(

глагол(eats), группа_существительного(определитель(the),существительное(аррlе))

)

)

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

предложение(Х,предложение(NP,VP))--› группа_существительного(X,NP), группа_глагола(X,VP).

Это правило указывает, что, если можно найти последовательность, составляющую группу существительного с деревом разбора NP,за которой следует последовательность, составляющая группу глагола, с деревом разбора VPто можно найти последовательность, составляющую полное предложение, и деревом разбора для этого предложения является предложениe(NP,VP).Или, в более процедурной формулировке: для того, чтобы выполнить разбор предложения необходимо найти группу существительного, за которой следует группа глагола, и затем объединить деревья разбора этих двух составляющих, используя функтор предложениедля построения дерева разбора предложения. Отметим, что аргументы X– это аргументы, использовавшиеся ранее для согласования формы числа, и решение поставить аргументы для построения дерева разбора после, а не перед ними является совершенно произвольным. Если вам трудно понять это расширение возможностей грамматических правил, то полезно напомнить, что последнее правило представляет собою всего лишь краткую запись следующего утверждения на языке Пролог:

предложение(Х,предложение(NР,VP),S0,S):-группа_существительного(Х,NР,S0,S1),

группа_глагола(Х,VР,S1,S).

где S0, S1и S– части входной последовательности слов. Аргументы, предназначенные для построения дерева разбора, можно ввести в правила грамматики обычным образом. Здесь приведен получившийся после этого фрагмент грамматики (аргумент, используемый для согласования формы числа, для ясности опущен):

предложение(предложение(NР,VP))--›группа _существительного (NP), группа _ глагола (VP).

группа_глагола(группа_глагола(V))--› глагол(V).

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

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

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

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

транслируется в утверждение

предложение(Х,S0,S):-

группа_существительного(Х,S0,S1),группа_глагола(Х,S1,S).

При вызове целевых утверждений, содержащих грамматические правила, с самого верхнего уровня интерпретатора (т. е. из вопросов, задаваемых программистом.- Ред.)или из обычных правил Пролога, необходимо явным образом указать дополнительные аргументы, добавив их в конец списка аргументов. Таким образом, правильное целевое утверждение, содержащее обращение к функтору предложение,должно быть таким:

?- предложение(Х,[a,clergyman,eats,a, cake],[]).

?- предложение(Х, [every, bird, sings,and,pigs,can,fly],L).

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

?- phrase(предложение(Х),[the, man,sings]).

9.5. Введение дополнительных условий

Рассматривавшиеся до сих пор грамматические правила, входящие в программу синтаксического анализатора, содержали информацию лишь о том, какая часть входной последовательности обрабатывается каждым из правил. Каждый элемент описания правил должен содержать указание о том, как обрабатывать два дополнительных аргумента, добавленных транслятором грамматических правил. Так что каждое целевое утверждение в результирующем утверждении Пролога обрабатывало определенную часть входной последовательности. Иногда может возникнуть желание определить целевые утверждения иного типа, не связанные непосредственно с обработкой входной последовательности, и рассматриваемый формализм грамматических правил позволяет сделать это. В языке принято следующее соглашение: каждое целевое утверждение, заключенное в фигурные скобки {}, при трансляции не меняется.

Рассмотрим несколько примеров ситуаций, в которых было бы полезно использовать эту возможность. Мы покажем, как можно улучшить «словарь» синтаксического анализатора, т. е. его «знания» о словах обрабатываемого языка.

Прежде всего рассмотрим накладные расходы, связанные с введением нового слова в программу, в которой используются оба множества дополнительных аргументов (для согласования формы числа и для построения дерева разбора). Если нужно добавить новое слово, например banana, то для этого необходимо добавить хотя бы правило

существительное(едч, существительное(banana))--› [banana].

которое сводится к следующему факту на Прологе:

существительное(едч, существительное(banana),[banana|S],S).

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