Трансформаціонные грамматики

Лексический анализ

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

Соглашение: в дальнейшем, если особо не оговорено, под регулярной грамматикой будем понимать леволинейную грамматику.

Напомним, что грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р имеет вид A ® Bt либо A ® t, где A Î VN, B Î VN, t Î VT.

Соглашение: предположим, что анализируемая цепочка заканчивается специальным символом ^ - признаком конца цепочки.

Для грамматик этого типа существует алгоритм определения того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой (алгоритм разбора):

(1) первый символ исходной цепочки a₁a₂...a_n^ заменяем нетерминалом A, для которого в грамматике есть правило вывода A ® a₁ (другими словами, производим "свертку" терминала a₁ к нетерминалу A)

(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал a_i исходной цепочки заменяем нетерминалом B, для которого в грамматике есть правило вывода B ® Aa_i (i = 2, 3,.., n);

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

При работе этого алгоритма возможны следующие ситуации:

(1) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу S. Это означает, что исходная цепочка a₁a₂...a_n^ Î L(G).

(2) прочитана вся цепочка; на каждом шаге находилась единственная нужная "свертка"; на последнем шаге свертка произошла к символу, отличному от S. Это означает, что исходная цепочка a₁a₂...a_n^ Ï L(G).

(3) на некотором шаге не нашлось нужной свертки, т.е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала a_i исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B ® Aa_i. Это означает, что исходная цепочка a₁a₂...a_n^ Ï L(G).

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

Допустим, что разбор на каждом шаге детерминированный.

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

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

Например, для грамматики G = ({a, b, ^}, {S, A, B, C}, P, S), такая таблица будет выглядеть следующим образом:

		a	b	^
P: S ® C^	C	A	B	S
C ® Ab \| Ba	A	-	C	-
A ® a \| Ca	B	C	-	-
B ® b \| Cb	S	-	-	-

Знак "-" ставится в том случае, если для пары "терминал-нетерминал" свертки нет.

Но чаще информацию о возможных свертках представляют в виде диаграммы состояний (ДС) - неупорядоченного ориентированного помеченного графа, который строится следующим образом:

(1) строят вершины графа, помеченные нетерминалами грамматики (для каждого нетерминала - одну вершину), и еще одну вершину, помеченную символом, отличным от нетерминальных (например, H). Эти вершины будем называть состояниями. H - начальное состояние.

(2) соединяем эти состояния дугами по следующим правилам:

a) для каждого правила грамматики вида W ® t соединяем дугой состояния H и W (от H к W) и помечаем дугу символом t;

б) для каждого правила W ® Vt соединяем дугой состояния V и W (от V к W) и помечаем дугу символом t;

Диаграмма состояний для грамматики G (см. пример выше):

Алгоритм разбора по диаграмме состояний:

(1) объявляем текущим состояние H;

(2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: считываем очередной символ исходной цепочки и переходим из текущего состояния в другое состояние по дуге, помеченной этим символом. Состояние, в которое мы при этом попадаем, становится текущим.

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

(1) прочитана вся цепочка; на каждом шаге находилась единственная дуга, помеченная очередным символом анализируемой цепочки; в результате последнего перехода оказались в состоянии S. Это означает, что исходная цепочка принадлежит L(G).

(2) прочитана вся цепочка; на каждом шаге находилась единственная "нужная" дуга; в результате последнего шага оказались в состоянии, отличном от S. Это означает, что исходная цепочка не принадлежит L(G).

(3) на некотором шаге не нашлось дуги, выходящей из текущего состояния и помеченной очередным анализируемым символом. Это означает, что исходная цепочка не принадлежит L(G).

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

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

Определение: конечный автомат (КА) - это пятерка (K, VT, F, H, S), где

K - конечное множество состояний;

VT - конечное множество допустимых входных символов;

F - отображение множества K ´ VT ® K, определяющее поведение автомата; отображение F часто называют функцией переходов;

H Î K - начальное состояние;

S Î K - заключительное состояние (либо конечное множество заключительных состояний).

F(A, t) = B означает, что из состояния A по входному символу t происходит переход в состояние B.

Определение: конечный автомат допускает цепочку a₁a₂...a_n, если F(H,a₁) = A₁; F(A₁,a₂) = A₂;...; F(A_n-2,a_n-1) = A_n-1; F(A_n-1,a_n) = S, где a_i Î VT, A_j Î K,
j = 1, 2,...,n-1; i = 1, 2,...,n; H - начальное состояние, S - одно из заключительных состояний.

Определение: множество цепочек, допускаемых конечным автоматом, составляет определяемый им язык.

Для более удобной работы с диаграммами состояний введем несколько соглашений:

a) если из одного состояния в другое выходит несколько дуг, помеченных разными символами, то будем изображать одну дугу, помеченную всеми этими символами;

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

c) введем состояние ошибки (ER); переход в это состояние будет означать, что исходная цепочка языку не принадлежит.

По диаграмме состояний легко написать анализатор для регулярной грамматики.

Например, для грамматики G = ({a,b, ^}, {S,A,B,C}, P, S), где

P: S ® C^

С ® Ab | Ba

A ® a | Ca

B ® b | Cb

анализатор будет таким:

#include <stdio.h>

int scan_G(){

enum state {H, A, B, C, S, ER}; /* множество состояний */

state CS; /* CS - текущее состояние */

FILE *fp;/*указатель на файл, в котором находится анализируемая цепочка */

int c;

CS=H;

fp = fopen ("data","r");

c = fgetc (fp);

do {switch (CS) {

case H: if (c == 'a') {c = fgetc(fp); CS = A;}

else if (c == 'b') {c = fgetc(fp); CS = B;}

else CS = ER;

break;

case A: if (c == 'b') {c = fgetc(fp); CS = C;}

else CS = ER;

break;

case B: if (c == 'a') {c = fgetc(fp); CS = C;}

else CS = ER;

break;

case C: if (c =='a') {c = fgetc(fp); CS = A;}

else if (c == 'b') {c = fgetc(fp); CS = B;}

else if (c == '^') CS = S;

else CS = ER;

break;

}

} while (CS!= S && CS!= ER);

if (CS == ER) return -1; else return 0;

}

О недетерминированном разборе

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

Например, для грамматики G = ({a,b, ^}, {S,A,B}, P, S), где

P: S ® A^

A ® a | Bb

B ® b | Bb

разбор будет недетерминированным (т.к. у нетерминалов A и B есть одинаковые правые части - Bb).

Такой грамматике будет соответствовать недетерминированный конечный автомат.

Определение: недетерминированный конечный автомат (НКА) - это пятерка (K, VT, F, H, S), где

K - конечное множество состояний;

VT - конечное множество допустимых входных символов;

F - отображение множества K ´ VT в множество подмножеств K;

H Ì K - конечное множество начальных состояний;

S Ì K - конечное множество заключительных состояний.

F(A,t) = {B₁,B₂,...,B_n} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний B_i, i = 1, 2,...,n.

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

Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом языков, определяемых детерминированными конечными автоматами.

Это означает, что для любого НКА всегда можно построить детерминированный КА, определяющий тот же язык.

ТРАНСФОРМАЦІОННЫЕ ГРАММАТИКИ

Контекстно-свободные и контекстно-зависимые грамматики выходят из того положения, что все правила языка как синтаксические так и семантические должны найти свое отображение в правилах грамматики.

В 1950х годах Хомский выдвинул идею, что человек имеет два уровня механизма языковой компетенции. Один есть заложенным у него при рождении и реализует "глубинные" синтаксические структуры, которые являются наиболее обобщенными и не зависимыми от конкретного языка. Второй механизм возникает в результате обучения и отвечает за преобразование или трансформацию предложений образованных с помощью глубинных структур в предложение конкретного языка. Грамматика, которая реализует как глубинные синтаксические правила так и трансформационные правила, будет называться трансформационной.

В грамматиках из примеров 1.5 и 1.6 некоторые правила не являются присущими только русскому языку, а являются характерными для многих естественных языков сразу. Например, это правило, что предложения составляется из фразы существительного и фразы глагола. Также, что фраза глагола состоит из глагола и фразы существительного. Такие правила позволяют порождать основу (или "скелет") будущего предложения.

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

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

Пример 1.7. Трансформационная грамматика для предложений вида

кошка поймала мышку

мышка была поймана кошкой

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

Контекстно-зависимая грамматика будет иметь правила порождения основы предложения:

S NP Subject VP Object

NP N

VP Verb NP

Verb Aux V

Aux Modal Past | Past

V спійм

N кош

N мыш

Эти правила построены таким образом, чтобы они давали основу предложения, пригодную для превращения в правильное предложение как активного так и пассивного залога. Контексты Subject и Object введены для порождения падежных окончаний, контекст Aux - для порождения модального глагола (если нужно) и окончание глагола. Итак, основа предложения, построенного по этим правилам порождается как:

S => NP Subject VP Object => N Subject Verb NP Object => N Subject Aux V N Object.

Для трансформации основы в предложении активного залога нужно правило вида:

N1 Subject Aux V N2 Object N1 ка Aux V N2 ку

Past V V Past

V Past V ала

Здесь контексты Subject и Object заменяются морфемами, которые прибавляют к существительным нужные по правилам языка окончания (и суффиксы), а вспомогательная часть к глаголу заменяется его окончанием соответственно времени глагола.

Пользуясь такими трансформационными правилами, можно породить правильное предложение активного залога:

N Subject Aux V N Object => N1 ка Aux V N2 ку =>

=> кош ка Past V мыш ку => кош ка V Past мыш ку =>

=> кош ка спійм ала мыш ку => кошка поймала мышку

Для порождения предложения пассивного залога нужна одна трансформация из предложения активного залогу и еще одна трансформация для порождения слова "была":

N1 ка Aux V N2 ку > N2 ка Aux V N1 кой

Modal V Past > была V ана

Порождение правильного предложения пассивного залога имеет вид:

N Subject Aux V N Object => N1 ка Aux V N2 ку =>

=> N2 ка Aux V N1 кой => мыш ка Modal Past V кош кой =>

=> мыш ка Modal V Past кош кой => мыш ка была V ана кош кой =>

=> мыш ка была пойм ана кош кой => мышка была поймана кошкой.

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

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

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

ГРАММАТИКИ СВЯЗЕЙ

Как отмечалось в выводах к подразделу 1.1, формальная грамматика, которая моделирует естественный язык, не обязательно должна быть построена "сверху-вниз" от наиболее обобщенных правил конструкции предложений к конкретным словам в них.

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

Грамматика связей предоставляет именно такую возможность.

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

Грамматика связей - это формальная грамматика, которая определяет список терминалов (слов) языка и их возможные связи с другими словами, причем последовательность слов является правильным предложением языка, если выполняются три условия:

1) связи между словами в предложении не пересекаются (проективность);

2) все слова в предложении связаны друг с другом (связность);

3) выполнены все условия относительно связей каждого слова.

Пример 1.8. В предложении " кошка поймала мышку " мы имеем две связи между словами. Первый - между существительным-субъектом действия и глаголом, который определяет это действие. Обозначим этот тип связи буквой S (Subject). Второй - между глаголом и его существительным-объектом действия, который обозначим буквой O (Object). Эти связи иллюстрирует граф:

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

Здесь вместо связи O между глаголом-действием и его существительным-объектом использована связь MV между глаголом и его существительным-объектом с характеристикой (прилагательным). Слово "поймала" имеет еще одну связь E налево. E обозначает связь между глаголом и его наречием-модификатором перед ним. Связь A объединяет существительное и прилагательные, которые его характеризуют.

Два приведенных выше примера связей демонстрируют, что некоторые типы связей для слов в предложении являются необходимыми: S, O (или вместо него MV). Некоторые связи являются необязательными (A и E), так как прилагательных перед существительным может и не быть, равно как и наречий перед глаголом.

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

В естественном языке связей больше чем приведено здесь в примере (107 для английского). Полный перечень связей можно найти в Интернете по адресу http://www.lіnk.cs.cmu.edu/lіnk/dіct/summarіzelіnks.html.

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

· направление обозначается знаком "+" если связь идет направо от слова (например, " кошка: S+ ");

· направление обозначается знаком "." если связь идет налево (например, " мышку: O- ");

· если слово имеет более одного связи, то они объединяются знаком "&" (например, " поймала: S- & O+ ");

· если слово имеет больше одного связи в левую сторону, то связи перечисляются в порядке от наиболее дальнего слова к наиболее ближнему (например, " поймала: S- & E- ");

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

· если связь необходима, но может быть разных типов, то такие типы объединяются оператором "OR" (например, " мышку: MV- OR O- ");

· если связь необязательная, то она записывается в фигурных скобках (например, " поймала: { E- } ");

· если связь повторяется, то перед ней ставится знак "@" (например, " мышку: @A- ").

Пример 1.8 (продолжение): По указанным выше правилам, полностью грамматика связей для языка предложений "кошка поймала мышку" и " кошка вчера поймала серую мышку " записывается как:

кошка: S+;

вчера: E+;

поймала: S- & { E- } & (O+ OR MV+);

мышку: (O- OR MV-) & { @A- };

серую: A+;

Грамматику из примера 1.8 легко расширить чтобы она порождала больше похожих предложений. Так предложение "кошка поймала серую ловкую мышку" будет порождаться из грамматики если прибавить правило вида " ловкую: A+ ". А предложение " кошка поймала птичку " будет правильным при наличии правила " птичку: (O- OR MV-) & { @A- }; ".

Важно отметить, что в обоих приведенных случаях грамматика расширяется новыми словами, а не связями. Связи для слова " ловкую " будут теми же самыми, что и для слова " серую ". Аналогично, связи для слов " мышку " и " птичку " будут одинаковые.

Оказывается, что связи в грамматике одинаковы для всех морфологически похожих слов, т.е. слов с одинаковой граммемой.

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

Пример 1.8 (продолжение): Слова " мышку " и " птичку " – это существительные (n, Noun), обозначают живое существо (l, Lіve), женского рода (f, Female), единственные числа (s, Sіngle), в винительном падеже (v, accusatіVe). Граммема для обоих слов - nlfsv.

" кошка " - это существительное (n), обозначает живое существо (l), женского рода (f), единственного числа (s), в именительном падеже (i, subjectіve case). Граммема слова - nlfsі.

"поймала" - это глагол (v, Verb), совершенного вида (s), переходное (p), действительного залога (d), прошлого времени (p, Past), женского рода (f), единственного числа (s). Граммема слова - vspdpfs.

" серую " и " ловкую " - это прилагательные (a, Adjectіve), женского рода (f), единственные числа (s), в винительном падеже (v). Граммема для обоих слов - afsv. Расширенная грамматика с новыми словами и граммемами будет записана как:

кошка.nlfsі: S+;

поймала.vspdpfs: S. & { E- } & (O+ OR MV+);

мышку,птичку.nlfsv: (O- OR MV-) & { @A-. };

серую,ловкую.afsv: A+;

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

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

· грамматика строится "снизу-вверх", когда на основе предложений воспроизводятся грамматические правила;

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

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

Выводы. Итак, как инструмент компьютерной обработки естественных языков грамматика связей будет не только проста в разработке, но и иметь все преимущества контекстно-свободных грамматик (распространенность и скорость компьютерных алгоритмов).

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

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

Разработка формальной грамматики украинского языка. На конец 2008-го года формальной грамматики украинского языка в свободном доступе не существует. Поэтому, в отличие от английского языка, из всех задач компьютерной обработки украинский язык решен лишь три – поиск в тексте, проверка правописания и статистический перевод. Как будет показано во втором разделе, лишь для таких задач наличие формальной грамматики не обязательно. Для дальнейшего развития компьютерных технологий обработки украинского языка позарез необходимо создание формальной грамматики.

Разработка грамматики связей считается самым перспективным способом получить такую формальную грамматику. Но для этого необходимые следующие предпосылки:

· должен быть собран национальный корпус украинского языка, в котором бы содержались все известные правильные предложения языка;

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

Собрание национального корпуса проводится Украинским языко-информационным фондом Национальной академии наук Украины (http://ulіf.org.ua /UMIF/). По состоянию на конец 2008-го года объем корпуса представляет свыше 43 млн. словоупотреблений, но морфологическую аннотацию имеет лишь несколько процентов всех предложений. Также корпус не находится в свободном доступе. Таким образом, разработка грамматики связей украинского языка и до сих пор остается задачей для будущих прикладных лингвистов.

В мире наиболее полной грамматикой связей является грамматика английского языка, разработанная Дэниэлом Слетором и Дэвидом Темперлеем из университета Карнеги-Мелон на протяжении свыше 10 лет.

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

Разработана также грамматика русского языка (Сергей Протасов).

Грамматика до сих пор находится в разработке, хотя и есть достаточно полной.

Грамматика и программы грамматического разбора доступны для приобретения.

Общее описание грамматики и демонстрационная программа построения диаграммы связей представленные на сайте http://slashzone.ru/parser.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: