Cодержание

1 Постановка задачи и определения

2 Пример грамматики

3 Пример разбора в ручную

4 Реализация грамматического разбора на Прологе.

 

1. Постановка задачи

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

Представление такой структуры - Дерево разбора для предложения данного языка.

Грамматика - это множество правил, определяющих способ построения предложений языка. На Прологе разбор осуществляется через использование

Грамматик, задаваемых определенными предложениями

definite clause grammer DCG

DCG - является обобщением контекстно-свободных грамматик.

Грамматика DCG определяется через запись определенных предложений, которые показывают, как могут быть соединены эти компоненты.

2. Пример грамматики

Sentence          -> noun_phrase, verb_phrase 

noun_phrase       -> article, noun 

verb_phrase       -> intransitive_verb 

article(singular) -> "a" 

article(singular) -> "the" 

article(plural)   -> "the" 

noun(singular)    -> "turtle" 

noun(plural)      -> "turtles" 

intransitive_verb(singular) -> "sleeps" 

intransitive_verb(plural)   -> "sleep" 

Предложение состоит из noun phrase и за ним следует verb phrase компоненты, представляющие грамматические категории языка, называются нетерминальными символами.

Терминальные символы - конечные компоненты языка. В данном случае это слова. Они записываются в ковычках ( " " ). В грамматике есть один выделенный нетерминальный символ, который называется начальным. Он описывает все компоненты языка.
В грамматике должно быть по крайне мере одно правило, с левой части которого находится начальный символ.
В данной грамматике это Sentence -"предложение".

3. Пример разбора в ручную.

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

4. Реализация грамматического разбора на Прологе.

Грамматическое правило - это структура с функтором --> и размерностью 2.
Компоненты структуры - это левая и правая части правила.

Нетерминальные символы - атомы Пролога.
Терминальные символы - атомы или переменные и заключаются вквадратные скобки.

При загрузке в Пролог - ,систему утверждения с функтором --> преобразуются в утверждения стандартного Пролога.

Перепишем в этой форме наши правила.

Sentence          -> noun_phrase, verb_phrase. 

noun_phrase       -> article, noun. 

verb_phrase       -> intransitive_verb. 

article(singular) -> [a]. 

article(singular) -> [the]. 

article(plural)   -> [the]. 

noun(singular)    -> [turtle]. 

noun(plural)      -> [turtles]. 

intransitive_verb(singular) -> [sleeps]. 

intransitive_verb(plural)   -> [sleep]. 

Как должны выглядеть утверждения Пролога ?

Надо чтобы каждое правило могло анализировать слова и передавать информацию на дальнейшую обработку.

Отступление :

Запоминание состояния в Прологе.

Иногда надо некоторое значение передавать в ходе обработки от одного предиката к другому в ходе вычислений.

Передача может быть :

• immutable неизменной
• mutable переменной

immutable
G(.. , S, ..):- g(.. , S, ..), .. h(.. , S, ..).

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

G(.. , S0,Sn):-

         g(.. , S0,S1),

              ...

         h(.. , Sm,Sn).

Length([],L,L).

Length([_|List],L0,L):-

         L1 is L0+1,

         Length(List,L1,L).

Аналогично для DCG проводится

• Для одной цели

          P(X)-->G(X). 

          P(X,S0,S):-G(X,S0,S).      

• Для нескольких целей

          P(X,Y)-->G(X),

                   R(X,Y),

                   S(Y). 

          P(X,Y,S0,S):-G(X,S0,S1),

                       R(X,Y,S1,S2),

                       S(Y,S2,S).      

Грамматическое правило, которое раскрывает нетерминальный символ, заменяя его на другие нетерминальные символы, преобразуется в правило Пролога, заголовок которого соответствует левой части грамматического правила, а тело состоит из символов правой части, представляющий собой соединенные подцели.

При этом каждый предикат дополняется двумя аргументами. Первый аргумент заголовка правила представляет анализируемую цепочку. Он передается в качестве первого аргумента первой подцели.

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

Например правую

noun_phrase(N) -> article(N), noun(N).

Заменяет на

noun_phrase(N,S0,S2) -> article(N,S0,S1), noun(N,S1,S2).

Подвергаемая грамматическому разбору цепочка слов, а также та цепочка, которая остается после разбора, представляются в виде списков.

Интерпретация рассмотренного правила такова :

Список S0 начинается с noun_phrase(N), а S2 это то что остается от S0 после удаления из него noun_phrase(N),
если :

• Cписок S0 начинается с article(N), а список S1 - это то, что остается от S0 после удаления артикля,
• Cписок S1 начинается с noun(N), а список S2 - это то, что остается от S1 после удаления noun(N).

Грамматическое правило, которое раскрывает символ, заменяя его на терминальный символ, преобразуется в правило Пролога, тело которого представляет собой вызов встроенного предиката 'C', имеющего следующее определение :
'C'/3
Цель успешно согласуется, если ее первый аргумент - список, а второй - голова этого списка, а третий - его хвост.

article(singular):-'c'(s0,the,s1)

Пример преобразования грамматического правила DCG:

p-- > q, [r], t, [u].
p(s0,s4):-q(s0,s1), 'c'(s1,r,s2),t(s2,s3),'c'(s3,u,s4).

(c) M.N.Morozov, 1999.