Розробка нових алгоритмів реалізації з метою розробки інтелектуальної системи синтаксичного аналізу

Работа алгоритма построения системы C множеств допустимых LR(1)-ситуаций начинается с того, что в C помещается начальное  множество ситуаций I₀ = closure({[S'  .S, $]}). Затем с помощью функции goto вычисляются новые множества ситуаций и включаются в C. По-существу, goto(I, X) - переход конечного автомата из состояния I по символу X.

Рассмотрим теперь, как по системе  множеств LR(1)-ситуаций строится LR(1)-таблица, т.е. функции действий и переходов LR(1)-анализатора.

Алгоритм 4.10. Построение LR(1)-таблицы.

Вход. Каноническая система C = {I₀, I₁, ..., I_n} множеств допустимых LR(1)-ситуаций для грамматики G.

Выход. Функции Action и Goto, составляющие LR(1)-таблицу  для грамматики G.

Метод. Для каждого состояния i функции Action[i, a] и Goto[i, X] строятся по множеству  ситуаций I_i:

• Значения функции действия (Action) для состояния i определяются следующим образом:
• если [A    .a , b]   I_i (a - терминал) и goto(I_i, a) = I_j, то полагаем Action[i, a] = shift j;
• если [A    ., a]   I_i, причем A S', то полагаем Action[i, a] = reduce A    ;
• если [S'  S., $]   I_i, то полагаем Action[i, $] = accept.
• Значения функции переходов для состояния i определяются следующим образом: если goto(I_i, A) = I_j, то Goto[i, A] = j (здесь A - нетерминал).
• Все входы в Action и Goto, не определенные шагами 2 и 3, полагаем равными error.
• Начальное состояние анализатора строится из множества, содержащего ситуацию [S'  .S, $].

Таблица на основе функций Action и Goto, полученных в результате работы алгоритма 4.10, называется канонической LR(1)-таблицей. LR(1)-анализатор, работающий с этой таблицей, называется каноническим LR(1)-анализатором.

Пример 4.10. Рассмотрим следующую грамматику, являющуюся пополненной для грамматики из примера 4.8:

	(0) E'  E
	(1) E   E + T
	(2) E   T
	(3) T   T * F
	(4) T   F
	(5) F   id

 

 Множества ситуаций и переходы по goto для этой грамматики приведены  на рис. 4.11. LR(1)-таблица для этой грамматики приведена на рис. 4.9.

Рис. 4.11:

 

 

 

4.4.4 LR(1)-грамматики

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

Язык L называется LR(1)-языком, если он может быть порожден некоторой LR(1)-грамматикой.

Иногда используется другое определение LR(1)-грамматики. Грамматика называется LR(1), если из условий

1. S' _r^*uAw  _ruvw,

2. S' _r^*zBx  _ruvy,

3. FIRST(w) = FIRST(y)

следует, что uAy = zBx (т.е. u = z, A = B и x = y).

Согласно этому определению, если uvw и uvy - правовыводимые цепочки пополненной  грамматики, у которых FIRST(w) = FIRST(y) и A   v - последнее правило, использованное в правом выводе цепочки uvw, то правило A   v должно применяться и в правом разборе при свертке uvy к uAy. Так как A дает v независимо от w, то LR(1)-условие означает, что в FIRST(w) содержится информация, достаточная для определения того, что uv за один шаг выводится из uA. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики.

Можно доказать, что эти два определения  эквивалентны.

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

В частности, неоднозначная грамматика не может быть LR(1). Для доказательства рассмотрим два различных правых вывода

(1) S  _ru_{1  r}...  _ru_{n  r}w, и

(2) S  _rv_{1  r}...  _rv_{m  r}w.

Нетрудно  заметить, что LR(1)-условие (согласно второму  определению LR(1)-грамматики) нарушается для наименьшего из чисел i, для  которых u_n-i v_m-i.

Пример 4.11. Рассмотрим вновь грамматику условных операторов:

	S   if E then S | if E then S else S | a
	E   b

 

  Если анализатор типа сдвиг-свертка находится в конфигурации, такой что необработанная часть  входной цепочки имеет вид else...$, а в магазине находится ...if E then S, то нельзя определить, является ли if E then S основой, вне зависимости от того, что лежит в магазине ниже. Это  конфликт сдвиг/свертка. В зависимости  от того, что следует на входе  за else, правильной может быть свертка  по S   if E then S или сдвиг else, а затем разбор другого S и завершение основы if E then S else S. Таким образом нельзя сказать, нужно ли в этом случае делать сдвиг или свертку, так что грамматика не является LR(1).

Эта грамматика может быть преобразована  к LR(1)-виду следующим образом:

	S   M | U
	M   if E then M else M | a
	U   if E then S | if E then M else U
	E   b

 

Основная  разница между LL(1)- и LR(1)-грамматиками заключается в следующем. Чтобы  грамматика была LR(1), необходимо распознавать вхождение правой части правила  вывода, просмотрев все, что выведено из этой правой части и текущий  символ входной цепочки. Это требование существенно менее строгое, чем  требование для LL(1)-грамматики, когда  необходимо определить применимое правило, видя только первый символ, выводимый  из его правой части. Таким образом, класс LL(1)-грамматик является собственным  подклассом класса LR(1)-грамматик.

Справедливы также следующие утверждения [2].

Теорема 4.5. Каждый LR(1)-язык является детерминированным КС-языком.

Теорема 4.6. Если L - детерминированный КС-язык, то существует LR(1)-грамматика, порождающая L.

4.4.5 Восстановление после синтаксических  ошибок

Одним из простейших методов восстановления после ошибки при LR(1)-анализе является следующий. При синтаксической ошибке просматриваем магазин от верхушки, пока не найдем состояние s с переходом  на выделенный нетерминал A. Затем сканируются  входные символы, пока не будет найден такой, который допустим после A. В  этом случае на верхушку магазина помещается состояние Goto[s, A] и разбор продолжается. Для нетерминала A может иметься несколько таких вариантов. Обычно A - это нетерминал, представляющий одну из основных конструкций языка, например оператор.

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

4.4.6 Варианты LR-анализаторов

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

Одним из способов такого упрощения  является LR(0)-анализ - частный случая LR-анализа, когда ни при построении таблиц, ни при анализе не учитывается  аванцепочка.

Еще одним вариантом LR-анализа являются так называемые SLR(1)-анализаторы (Simple LR(1)). Они строятся следующим образом. Пусть C = {I₀, I₁, ..., I_n} - набор множеств допустимых LR(0)-ситуаций. Состояния анализатора соответствуют I_i. Функции действий и переходов анализатора определяются следующим образом.

• Если [A   u.av]   I_i и goto(I_i, a) = I_j, то определим Action[i, a] = shift j.
• Если [A   u.]   I_i, то определим Action[i, a] = reduce A   u для всех a   FOLLOW(A), A S'.
• Если [S'  S.]   I_i, то определим Action[i, $] = accept.
• Если goto(I_i, A) = I_j, где A   N, то определим Goto[i, A] = j.
• Остальные входы для функций Action и Goto определим как error.
• Начальное состояние соответствует множеству ситуаций, содержащему ситуацию [S'  .S].

Распространенным вариантом LR(1)-анализа  является также LALR(1)-анализ. Он основан  на объединении (слиянии) некоторых  таблиц. Назовем ядром множества LR(1)-ситуаций множество их первых компонент (т.е. во множестве ситуаций не учитываются  аванцепочки). Объединим все множества  ситуаций с одинаковыми ядрами, а  в качестве аванцепочек возьмем  объединение аванцепочек. Функции Action и Goto строятся очевидным образом. Если функция Action таким образом построенного анализатора не имеет конфликтов, то он называется LALR(1)-анализатором (LookAhead LR(1)). 

 

СПИСОК  ВИКОРИСТАНИХ ДЖЕРЕЛ

 

1. Болотова Л.С., Смольянинов  А.А. Неформальные модели представления  знаний в системах искусственного интеллекта: учебное пособие. – М.: МИРЭА (ТУ), 1999. – 100 с.
2. Дж. Фостер Автоматичний синтаксичний аналіз – 1998. – №330. – С. 5-12.
3. Борисов А.Н., Вильюмс Э.Р., Сукур Л.Я. Диалоговые системы принятия решений на базе мини-ЭВМ: Информационное, математическое и програмное обеспечение. – Рига: Зинатне, 1986. – 195 с.
4. Дж. Фостер Автоматичний синтаксичний аналіз – 1998. – №330. – С. 5-12.
5. Катренко А.В., Бобало І.Ю. Асоціативні правила та їх застосування у видобуванні даних // Вісник Національного університету "Львівська політехніка" “Інформаційні системи та мережі". – 1998. – №330. – С. 128-134.
6. Колмогоров А.Н. Теория вероятности и математическая статистика. – М.: Наука, 1986. – 535 с.
7. Колмогоров А.Н. Теория информации и теория алгоритмов. – М.: Наука, 1987. – 304 с.
8. Дж. Фостер Автоматичний синтаксичний аналіз – 1998. – №330. – С. 5-12.
9. Л.П. Крысин Лингвистический процесор - Москва «Наука», 1992.-256 с.
10. В. А. Серебряков, М. П. Галочкин Основы конструирования компиляторов // Издательство: Едиториал УРСС – 2001.