LALR(1)

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

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

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

Описание

Пусть есть грамматика, не разбираемая из-за конфликтов сдвиг-свертка или свертка-свертка по алгоритму 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) анализатор, который существенно более сложен (алгоритмы LR(0)/SLR(1)/LALR(1) не сохраняют абсолютно никакой информации об уже разобранной части входного потока, в то время как полный LR(1) это делает, и потому сложнее), но может разбирать любую контексто-свободную однозначную грамматику.

По некоторым сведениями (уточнить!), все LL(1)-грамматики поддаются преобразованию в вид, разбираемый по LALR(1).

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

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

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

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