LALR(1)

LALR(1) (LA от англ. lookahead — предпросмотр) — восходящий алгоритм синтаксического разбора.

Представляет собой расширение алгоритма SLR(1). В ряде случаев работает тогда, когда построение SLR(1) таблицы разбора для данной грамматики невозможно из-за конфликтов сдвиг-свертка или свертка-свертка. Таким образом, класс грамматик, разбираемых по LALR(1) шире, чем класс SLR(1)-грамматик.

Алгоритм собственно разбора (исполнения анализатора по входному потоку) одинаков и у LALR(1), и у SLR(1) и шире, чем у LR(0). Различаются только алгоритмы построения таблицы разбора по грамматике в процессе генерации анализатора.

Общие сведения
LALR(1)

Описание

Пусть есть грамматика, не разбираемая из-за конфликтов сдвиг-свертка или свертка-свертка по алгоритму SLR(1).

В этом случае грамматика преобразуется следующим образом:

  • ищется нетерминал, на котором возникла вызвавшая конфликт свертка. Обозначим его A.
  • вводятся новые нетерминалы A1, A2, …, An, по одному на каждое появление A в правых частях правил.
  • везде в правых частях правил A заменяется на соответствующее Ak.
  • набор правил с A в левой части повторяется n раз по разу для каждого Ak.
  • правила с A в левой части удаляются, тем самым полностью удаляя A из грамматики.

Для преобразованной грамматики (она изоморфна исходной) повторяется попытка построения SLR(1) таблицы разбора.

Действие основано на том, что Follow(A) есть объединение всех Follow(Ak). В каждом конкретном состоянии новая грамматика имеет уже не A, а одно из Ak, то есть множество Follow для данного состояния имеет меньше элементов, чем для A в исходной грамматике.

Это приводит к тому, что для LALR(1) совершается меньше попыток поставить «приведение» в клеточку таблицы разбора, что уменьшает риск возникновения конфликтов с приведениями, иногда вовсе избавляет от них и делает грамматику, не разбираемую по SLR(1), разбираемой после преобразования.

Множество Follow(Ak) называется lookahead set для A и к-той встречи в правилах, отсюда название алгоритма.

LALR(1) и полный LR(1)

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

Практическое применение

Используется в генераторе синтаксических анализаторов yacc и его производных, таких, как GNU bison.

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

Компилятор GNU С использует yacc для построения синтаксического анализатора. Возможно (наличие строки grammar.y и yacc в теле исполняемого модуля), то же самое делает компания Microsoft для построения своего компилятора языка C.

Литература