- LALR(1)
-
Восходящий алгоритм синтаксического разбора.
Представляет собой расширение алгоритма SLR(1). В ряде случаев работает тогда, когда построение SLR(1) таблицы разбора для данной грамматики невозможно из-за конфликтов сдвиг-свертка или свертка-свертка. Таким образом, класс грамматик, разбираемых по LALR(1) (кр. "LALR(1)-грамматик") шире, чем класс SLR(1)-грамматик.
Буквы "LA" в сокращении означают "lookahead".
Алгоритм собственно разбора (исполнения анализатора по входному потоку) одинаков и у 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) анализатор, который существенно более сложен, но может разбирать любую контексто-свободную однозначную грамматику.
По некоторым сведениями (уточнить!), все LL(1)-грамматики поддаются преобразованию в вид, разбираемый по LALR(1).
Практическое применение
Используется в генераторе синтаксических анализаторов yacc и его производных, таких, как GNU bison.
Большинство реально используемых языков программирования имеют LALR(1)-грамматики, т.е. данного вида анализаторов достаточно для разбора большинства реально используемых языков.
Компилятор GNU С использует yacc для построения синтаксического анализатора. Возможно (наличие строки grammar.y и yacc в теле исполняемого модуля), то же самое делает компания Microsoft для построения своего компилятора языка C.
Категория:- Синтаксический анализ
Wikimedia Foundation. 2010.