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

Часто построенные таблицы для LR(1)-анализатора оказываются довольно

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

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

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

Если [A

u.av]

Ii и goto(Ii, a) = Ij, то определим Action[i, a] = shift j.

Если [A

u.]

Ii, то определим Action[i, a] = reduce A

u для всех a

FOLLOW(A), A

S'.

Если [S'

S.]

Ii, то определим Action[i, $] = accept.

Если goto(Ii, A) = Ij, где A

N, то определим Goto[i, A] = j.

Начальное состояние соответствует множеству ситуаций, содержащему ситуацию [S'

.S].

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

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

Содержание раздела

---

---