Контекстно-свободные грамматики

Следующей по сложности за регулярной грамматикой следует контекстно-свободная (context-free) грамматика (КСГ)

Естественно, определение КСГ внешне выглядит как и обычное определение грамматики:G_ксг = (N, S, P, S), однако при этом характерным для КСГ является форма ее правил (продукций)

P: A®a,

где AÎN, aÎ (NÈS)⁺.

 

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

N = {группа_существ, глагол, прилагательное, существительное, предлог, фраза}

S = {печатать, стереть, зеленый, первый, последний, символ, строка, страница, в}

S = фраза

P = { Фр ® Г, Гс

Гс ® Прил, С

Гс ® Прил, С, Предлог, Гс

Г ®печатать

Г ®стереть

Прил ®зеленый

Прил ®первый

Прил ®последний

С ®символ

С ®строка

С ®страница

Предлог ®в}

Эта грамматика может порождать фразы вроде "Печатать зеленый строка", "Стереть первый символ в последний строка в первый страница" и т.п. Синтаксическая проверка подобных предложений может быть осуществлена путем простого перебора возможных подстановок правил грамматики. Например, анализатор предложений такого языка на Прологе может выглядеть так:

/*

АНАЛИЗАТОР КС-ГРАММАТИКИ

Фраза -> Глагол, Группа_сущ

Группа_сущ -> Прилагат, Существ

Группа_сущ -> Прилагат, Существ, Предлог, Группа_сущ

Глагол ->...

Прилагат ->...

Существ ->...

Предлог ->...

*/

goal

FRAZA = ["печатать","первый","символ","в","последний","строка"],

write("\nРАЗБОР ПРЕДЛОЖЕНИЯ\n"), print_list(FRAZA),

s(FRAZA).

clauses

s(A):- sentence(A), write("\nФРАЗА РАСПОЗНАНА\n").

s(_):- write("\nОШИБКА: ФРАЗА НЕ РАСПОЗНАНА\n").

 

% СЛУЖЕБНЫЕ И СЕРВИСНЫЕ ПРЕДИКАТЫ

 

append([],L,L).

append([H|A],B,[H|C]):- append(A,B,C).

 

print_list([]).

print_list([Head|Tail]):- write(Head,"."), print_list(Tail).

 

% СИНТАКСИС

sentence(S):-

append(S1,S2,S),

glagol(S1),

GS(S2),

write("\nГлагол:"), writel(S1),

write("\nГс: "), writel(S2).

 

GS(S):-

append(S1,S2,S),

prilagat(S1),

noun(S2),

write("\n*** Разбор ГС-1:"),

write("\nПрилагательное: "),writel(S1),

write("\nСуществительное:"),writel(S2).

GS(S):-

append(S1,Stmp1,S),

append(S2,Stmp2,Stmp1),

append(S3,S4,Stmp2),

prilagat(S1),

noun(S2),

predlog(S3),

GS(S4),

write("\n*** Разбор ГС-2:"),

write("\nПрилагательное: "), print_list(S1),

write("\nСуществительное:"), print_list(S2),

write("\nПредлог: "), print_list(S2),

write("\nГс: "), print_list(S2).

 

% СЛОВАРЬ

 

noun([ символ ]). noun([ строка ]). noun([ страница ]).

glagol([ печатать ]). glagol([ стереть ]).

prilagat([ первый ]). prilagat([ второй ]). prilagat([ последний ]).

predlog([ в ]).

 

Но это все - "экзотика". Теперь рассмотрим более осмысленный пример – грамматику арифметических выражений. Эта грамматика в различных вариантах нам будет встречаться и далее. Пока же рассмотрим наиболее простой случай, содержащий лишь две бинарные операции с разными приоритетами.

G₀=({E,T,F},{a,+,*,(,)},P,E)

P = { E ® E+T|T

T ® T*F|F

F ® (E)|a}

Анализатор на Прологе будет выглядеть так:

 

E(L):- T(L).

E(L):- a3(L1,["+"],L3,L),

     E(L1),

     T(L3).

T(L):- F(L).

T(L):- a3(L1,["*"],L3,L),

     T(L1), F(L3).

F(L):- L=["a"].

F(L):- a3(["("],L2,[")"],L),

     E(L2).

Здесь предикат a3() разбивает список на три части. Как видно, Пролог-программа повторяет нашу грамматику с точностью до формы записи.

ОК-ГРАММАТИКИ

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

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

Рассмотрим, каким образом может осуществляться согласование родов. Допустим, у нас есть группа существительных (ГС), состоящая из местоимения (Мест), прилагательного (Прил) и существительного (Сущ). Тогда определение ГС, учитывающее согласование родов, может выглядеть так:

Гс ® Мест(k), Прил(k), Сущ(k), ГС

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

Мест(муж) ® этот

Мест(жен) ® эта

Прил(муж) ® второй

Прил(жен) ® вторая

Сущ(жен) ® строка

Сущ(муж) ® пароль

и т.д.

На Прологе введение контекстуального аргумента выглядит так:

mest(“муж”,”этот”).

pril ("жен", "вторая").

и т.п.