LALR(1) (LA от англ. lookahead — предпросмотр) - восходящий алгоритм синтаксического разбора.
Представляет собой расширение алгоритма SLR(1). В ряде случаев работает тогда, когда построение SLR(1) таблицы разбора для данной грамматики невозможно из-за конфликтов сдвиг-свертка или свертка-свертка. Таким образом, класс грамматик, разбираемых по LALR(1) шире, чем класс SLR(1)-грамматик.
Алгоритм собственно разбора (исполнения анализатора по входному потоку) одинаков и у LALR(1), и у SLR(1) — и, шире, у LR(0). Различаются только алгоритмы построения таблицы разбора по грамматике в процессе генерации анализатора.
Пусть есть грамматика, не разбираемая из-за конфликтов сдвиг-свертка или свертка-свертка по алгоритму SLR(1).
В этом случае грамматика преобразуется следующим образом:
Для преобразованной грамматики (она изоморфна исходной) повторяется попытка построения SLR(1) таблицы разбора.
Действие основано на том, что Follow(A) есть объединение всех Follow(Ak). В каждом конкретном состоянии новая грамматика имеет уже не A, а одно из Ak, то есть множество Follow для данного состояния имеет меньше элементов, чем для A в исходной грамматике.
Это приводит к тому, что для LALR(1) совершается меньше попыток поставить «приведение» в клеточку таблицы разбора, что уменьшает риск возникновения конфликтов с приведениями, иногда вовсе избавляет от них и делает грамматику, не разбираемую по SLR(1), разбираемой после преобразования.
Множество Follow(Ak) называется lookahead set для A и к-той встречи в правилах, отсюда название алгоритма.
Конфликты сдвиг-свертка и свертка-свертка могут остаться и после преобразования грамматики по LALR(1). Это означает, что для данной грамматики необходим полный LR(1) анализатор, который существенно более сложен, но может разбирать любую контексто-свободную однозначную грамматику.
По некоторым сведениями (уточнить!), все LL(1)-грамматики поддаются преобразованию в вид, разбираемый по LALR(1).
Используется в генераторе синтаксических анализаторов yacc и его производных, таких, как GNU bison.
Большинство реально используемых языков программирования имеют LALR(1)-грамматики, то есть данного вида анализаторов достаточно для разбора большинства реально используемых языков.
Компилятор GNU С использует yacc для построения синтаксического анализатора. Возможно (наличие строки grammar.y и yacc в теле исполняемого модуля), то же самое делает компания Microsoft для построения своего компилятора языка C.
В этой статье не хватает ссылок на источники информации. |
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .