ИСПОЛЬЗОВАНИЕ LR-ТАБЛИЦ ДЛЯ РАЗБОРА ОГРАНИЧЕННОГО ЕСТЕСТВЕННОГО ЯЗЫКА

Крищенко В. А. (crpg@aha.ru)

Московский Государственный Технический Университет им. Н.Э. Баумана

Создание эффективного синтаксического разбора ограниченного естественного языка (ОЕЯ) является центральным моментом для любых задач, связанных с интеллектуальным анализом текстовой информации, как отмечено в [2]. Наиболее проработанными к настоящему моменту являются методы разбора структуры предложения ОЕЯ, использующие различные варианты формальных грамматик [3].

К настоящему времени имеется несколько алгоритмов синтаксического разбора подвидов КС языков, базирующихся на описанных в [1] LR таблицах. В частности, предложенный в [4] подход к разбору естественного языка опирается на идею относительной близости многих грамматик, описывающих естественный язык, к LR грамматикам. Он также использует при разборе вариант LR таблиц, с единственным отличием - оно вытекает из изначальной неоднозначности естественного языка. Каждый элемент таблицы действий является множеством действий, а не единственным действием. Стандартный алгоритм при обнаружении нескольких действий в одной ячейке таблицы заканчивает свою работу с сообщением об ошибке, а алгоритм, направленный на разбор ЕЯ, должен в таком случае порождать в ходе синтаксического анализа несколько деревьев вывода. Пусть дана контекстно-свободная грамматика G = {VT, VN, P, S},

где VT - множество терминальных символов, VN - множество нетерминальных символов, V = VN U VT - полный алфавит грамматики, S е VN - начальный символ грамматики,

P: VN - V - множество продукций или правил вывода цепочек, принадлежащих порождаемому грамматикой языку.

Алгоритм синтаксического разбора из [4] может использовать любую из вариаций LR-таблиц, но обычно используют LR(1)-таблицы. Для построения LR(1) таблицы необходимы ресурсы памяти, примерно пропорциональные числу сочетаний из P VT, а

для LR(2)-таблицы - числу сочетаний из P VT , поэтому LR-разбор хотя и мог бы

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

Построение 1 Р(1)-таблиц

Сначала дадим описание модифицированного с учетом неоднозначности ЕЯ метода построения LR-таблиц. Условимся считать, что исходная КС-грамматика, хотя и не является LR(1), не содержит пустых правил вида A - e и циклов вида A = а1 B[31 = а2A[32. Предположение об отсутствии пустых правил допустимо, поскольку a) любую КС-грамматику с пустыми правилами можно преобразовать к эквивалентной грамматике без

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

LR(1)-CMTyaL44/m

ЬЯ(1)-ситуация записывается в виде [A - а], где A - а[е P - правило вывода, а -текущий символ: а е VT или а = $, где $ - маркер конца входной цепочки. Другая форма записи ЫА(1)-ситуации - [p, j, а], где p - номер продукции A - A/е P, а j = Щ .

Схема алгоритма

Алгоритм строит на основе исходной грамматики управляющие таблицы ACTIONS и GOTO для синтаксического анализатора - магазинного автомата, описывающие его состояния и переходы между ними. Состояния анализатора получаются из так называемой канонической системы ЫА(1)-ситуаций. Она строится как замыкание начальной ЫА(1)-ситуации [S - .S, $] для расширенной грамматики G = {VT, VNP, S}, где S - .S - новая продукция, Sначальный символ расширенной грамматики, VN = VN U {S}, P = P U {S - S}. Замыкание

строится при помощи функций CLOSURE и GOTO. Вспомогательная функция FIRST возвращает активный префикс для цепочки символов грамматики.

Построение функции FIRST

Если ае V+, то FIRST(a) есть множество терминалов, которыми начинаются строки, выводимые из а. Поскольку грамматика изначально не содержит пустых правил, то вычисление функции FIRST производится следующим образом.

1. Если X е VT, то FIRST(X) = {X}.

2. Если XeVN и X - аа, то добавить а к FIRST(X).

3. Если X eVN и X - Ya , X ф Y , то добавить каждый символ из FIRST(Y) к first(x ).

4. FIRST(Xa) = FIRST(X) в силу отсутствия пустых правил в грамматике, поэтому можно заранее рассчитать FIRSTX = FIRST(X) для каждого X е V и легко получить FIRST (а) для любой ае V + .

Функция CLOSURE

CLOSURE) - функция, принимающая s - множество LR(1)-ситуаций - и возвращает другое множество LR(1 )-ситуаций.

1 . Повторять, пока в s нельзя добавить новых элементов.

2. Для любого [A - Х.Б[, а] из s, для любой B - уе P и любого терминала b е FIRST(e?) таких, что [Б - у, b]<£ s, добавить [Б - .у, b] в s . 3. Вернуть s .

Функция GOTO

Функция GOTO(s, X) возвращает новое множество ситуаций для множества s и символа грамматики X е V.

1. Пусть q- множество ситуаций вида [A - AXа], если [A - X.Xfi, а]е s .

2. Вернуть CLOSURE(q) .

Построения канонической системы ситуаций

1. Положим C = CLOSURE({S - .S, $]}).

2. Повторять, пока в C нельзя добавить новых элементов.

3. Для любого s е C и любого X е V таких, что множество GOTO(s, X) не является пустым, и GOTO(s, X)ё C, добавить GOTO(s, X) в C.

Построение таблиц ACTION и GOTO

LR(1)-таблицы ACTION и GOTO, управляющие синтаксическим LR(1)-анализатором, строятся по каноническому множеству ситуаций C = {s0, sk } следующим образом.

1. Для каждого элемента si е C

2. Если [A - A.a/3, b]e s, и GOTO(si, a) = sj и a е U то добавить shift t к ACTION [i, a ].

3. Если [A - A., si, то добавить reduce j к ACTION [i, a ], где p е P - продукция A - A.

4. Если [S - S., $]е si то добавить accept в ACTION[i, a]. 5. Для любых состояний и любых нетерминалов A еVN

6. Если GOTO(s A) =sj то GOTO[i, A] = j

7. Множество ситуаций, построенное из является начальным состоянием

анализатора.

Способ использования построенных таблиц ACTION и GOTO синтаксическим анализатором совпадает с изложенным в [1 ] с единственным исключением: обнаружив в ячейке таблицы ACTION более одного элемента, анализатор не прекращает разбор, а создает несколько выводов для каждого из вариантов.

Построение 1 Р(1)-таблицы для грамматик, описывающих естественный язык

Структуру предложения естественного языка можно описать КС-грамматикой, которая достаточно близка к LR(k) [4]. Для грамматик, у которых некоторые элементы таблицы ACTION содержат более одного элемента, размер канонической системы множеств ситуаций растет весьма быстро при увеличении числа правил и символов грамматики, и построение таблиц ACTION и GOTO может занимать значительное время.

Таблица 1. Зависимость времени построения таблиц от размера грамматики

В таблице 1 приведены экспериментальные данные для исходного алгоритма построения

LR(1 )-таблиц применительно к нескольким грамматикам, описывающих предложения

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

Фрагмент одной из грамматик, участвовавшей в эксперименте:

start - s vp - v,np np - n

s - np,vp vp - vp, conj, vp np - adj, n

Таблица 1 показывает, что, учитывая, практическую ценность грамматик с количеством правил [PJ = 300 -г- 400, модернизация алгоритма с целью повышения быстродействия

является достаточно актуальной задачей. Два возможных пути для этого - изменение вычисления функции CLOSURE и ускорение доступа ко множествам LR(1 )-ситуаций.

Изменение вычисления функции CLOSURE

Функцию CLOSURE(s) можно разбить на вычисление замыканий для каждой ситуации. 1 . Повторять, пока в s нельзя добавить новых элементов.

2. Для любой ситуации I е s, s = CLOSURE1(I) U s.

3. Вернуть s .

4. Функция CLOSURE1 (I) возвращает замыкание для LR(1 )-ситуации I вида [A - A.B[, а ]. Поскольку одна и та же LR(1 )-ситуация может принадлежать более чем одному множеству ситуаций, то может иметь смысл вычислять значение функции CLOSURE1(I) только один раз, а результат запоминать для дальнейшего использования. Это увеличивает расход памяти, но позволяет существенно сократить время построения таблиц.

Хеширование множества ситуаций

Для ускорения работы с множествами ситуаций можно ввести их хеширование. Каждая ситуация является тройкой [p, j, а], где p - продукция, j - положение точки в правой части продукции p, а а - терминал. Таким образом, на множестве LR(1 )-ситуаций можно определить три естественных отношения порядка (и построить ключ хеширования на их основе):

1 ) по номеру продукции, перенумеровав все продукции и тем самым определив отношения порядка на P;

2) по номеру терминала, перенумеровав все терминалы и определив таким образом отношения порядка на VT;

3) по позиции точки в правой части продукции.

Рисунок 1. Распределение мощности множества ситуаций

500-TF 450

400 -Р 350

О Ф

300

1 250-

5 200-1-

Мощность множества

Для КС-грамматик, описывающих ЕЯ, количество правил намного больше числа терминалов, поэтому для минимизации времени поиска можно взять первый ключ - по продукциям. Однако для хеширования в пределах одного множества LR(1 )-ситуаций можно использовать ключ по терминалам с целью экономии памяти. На рис.1 для грамматики предложения на естественном языке (количество правил P = 160, а терминалов VT = 40)

показано распределение длины множеств ситуаций из канонической системы множеств. Среднее значение длины множества LR(1)-ситуаций для рисунка 1 равно 1 sj ~ 200 . Таким

образом, использование хеширования по продукциям (при P = 160 значениях ключа) будет более эффективно по скорости, но хуже по расходу памяти.

Для грамматик с большим числом правил одна LR(1)-ситуация может принадлежать большому числу множеств из канонической системы. Поэтому можно дополнительно ввести множество всех найденных LR(1 )-ситуаций и вычисленной для каждой ситуации функции CLOSURE1(l): H = {< I, CLOSURE1(l) > : I = [p, j, a]}. Для быстрого поиска ситуации в этом множестве можно использовать хеширование по номеру продукции: H = {< p, Hi >: p e P, H: = {< I, CLOSURE (I) > : I = [p, j, a ]}}. Однако, поскольку размер

множества H относительно небольшой (для грамматики с P = 160 в примере имеем 13860

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

точки. Тогда будет использоваться следующая функция: F([p, j, a]) = (j P + p) )vt + a, где

a и p - соответственно номер терминала и правила, VT = VT ! {$}. Это ключ имеет не меньше значений, чем максимальное количество возможных LR(1 )-ситуаций для данной грамматики. Всего есть]P V T значений ключа хеширования, где Jmax на единицу больше

максимальной длины правой части правила из P .

Тогда сами множества ситуаций, образующие состояния синтаксического анализатора, можно рассматривать как множество номеров ситуаций из H, хешированных по номеру терминала a из LR(1)-ситуации [p, j, a]: s = {< a, st > a e V T }, где st - множество номеров

ситуаций [p, j, a] из H.

Хеширование множества множеств ситуаций

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

система множеств имеет вид: C = {< /, Q >: Q = {Sj : Sj = {{ : I = [A - X.Bft, a]} / = sj}}.

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

Рисунок 2. Распределение ЬЩ1)-ситуаций канонической системы

множествам

Улучшенный алгоритм построения ЬЯ(1)-таблиц

Ниже дан адаптированный для разбора ЕЯ алгоритм построения LR(1 )-таблиц для КС-грамматик без пустых правил и циклов, как потребовано ранее.

Функция CLOSURE1

CLOSURE1(sO ) - функция, принимающая LR(1)-ситуацию [A - A.B[, а], и возвращающая множество LR(1 )-ситуаций.

1. s = {< а, [A - A.B , а]>, < b0, 0 >, < b1, 0 > ... < bM, 0 >} - все множества пусты, кроме

множества, соответствующему символу а .

2. Повторять пока в s нельзя добавить новых элементов.

3. Для любого [A - A.B[, а]е s, для любой B - уе P и любого терминала bе FIRST(e?), таких, что [Б - .у, b]g st v < b, st >е s , добавить [S - .у, b] в si.

4. Вернуть s .

и возвращает

Функция CLOSURE

CLOSURE(s) - функция, принимающая s - множество LR(1 )-ситуаций другое множество LR(1 )-ситуаций.

1 . Повторять пока нельзя добавить новых элементов в s .

2. Для любого q = [A - A.B , а]е st v < а, st >е s, для любого

t = [A - .у, CLOSURE1(q), такого, что (t g sj v < b, sj >е s) a (3sj : < b, sj >е s)

добавить t в sj или добавить < b, {t} > в s .

3. Вернуть s .

Функция GOTO

Функция GOTO(s,X) возвращает новое множество ситуация для множества s и символа грамматики X е VN . 1 . Пусть q пусто.

2. Для любого a e V T, пусть - множество ситуаций вида [A - XXв, a], если

st v < a, st >e s . Добавить < a, q} > в s .

3. Вернуть CLOSURE(q).

Построение канонической системы ситуаций

1. Для любого X e V вычислить FIRST(X) .

2. Положить C = CLOSURE ({[[ - .S ,$]}).

3. Повторять пока в C нельзя добавить новых элементов.

Для любого s e C и любого X e V, таких, что множество gs = GO TO (s, X) 0 и

gs £ Ci, где < l, C > e C V l = gs, добавить gs в Q.

Сравнение быстродействия различных вариантов алгоритма

В табл. 2 приведено сравнение четырех вариантов реализации алгоритма:

1) исходный вариант;

2) вариант с повсеместным использованием хеширования, но без сохранения результата вычисления функции CLOSURE 1;

3) с повторным использованием CLOSURE 1, но без хеширования;

4) с хешированием и повторным использованием CLOSURE1 .

Прочерк в таблице 2 означает, что эксперимент не был закончен из-за слишком большого объема времени, требуемого для его завершения.

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

На основе этой таблицы можно попытаться сделать вывод о быстродействии модифицированного алгоритма по сравнению с исходным.

Рисунок 3. Сравнение затрат времени при различных вариантах вычисления ЬЩ1)-таблиц

.о

Ь£ cd о

ъ

cd cL

1800 -1600 -1400 -1200 -

1000 800 600 400 200 0

40 80 120

Количество правил грамматики

---Вариант 1

......Вариант 2

----Вариант 3

-Вариант 4

Литература

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х томах. М.: Мир, 1978.

2. Интеллектуальный интерфейс к базам данных. / Лахути Д.Г, Рубашкин В.Ш.

VI национальная конференция по искусственному интеллекту с международным участием КИИ-98. Сборник научных трудов в трех томах. Пущино, 1998 Т. 1. - с. 246-249.

3. Синтез формальных моделей языка и смысла как проблема семантической обработки естественного языка / Поляков В. Н. Новости искусственного интеллекта. - 1997. -№ 1. - с. 6-63.

4. Tomita M. Efficient parsing for natural language. Berlin, 1993.