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) анализатор, который существенно более сложен, но может разбирать любую контексто-свободную однозначную грамматику.

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

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

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

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

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

К:Википедия:Статьи без источников (тип: не указан)

Отрывок, характеризующий LALR(1)

Пьер в последнее время редко виделся с женою с глазу на глаз. И в Петербурге, и в Москве дом их постоянно бывал полон гостями. В следующую ночь после дуэли, он, как и часто делал, не пошел в спальню, а остался в своем огромном, отцовском кабинете, в том самом, в котором умер граф Безухий.
Он прилег на диван и хотел заснуть, для того чтобы забыть всё, что было с ним, но он не мог этого сделать. Такая буря чувств, мыслей, воспоминаний вдруг поднялась в его душе, что он не только не мог спать, но не мог сидеть на месте и должен был вскочить с дивана и быстрыми шагами ходить по комнате. То ему представлялась она в первое время после женитьбы, с открытыми плечами и усталым, страстным взглядом, и тотчас же рядом с нею представлялось красивое, наглое и твердо насмешливое лицо Долохова, каким оно было на обеде, и то же лицо Долохова, бледное, дрожащее и страдающее, каким оно было, когда он повернулся и упал на снег.
«Что ж было? – спрашивал он сам себя. – Я убил любовника , да, убил любовника своей жены. Да, это было. Отчего? Как я дошел до этого? – Оттого, что ты женился на ней, – отвечал внутренний голос.
«Но в чем же я виноват? – спрашивал он. – В том, что ты женился не любя ее, в том, что ты обманул и себя и ее, – и ему живо представилась та минута после ужина у князя Василья, когда он сказал эти невыходившие из него слова: „Je vous aime“. [Я вас люблю.] Всё от этого! Я и тогда чувствовал, думал он, я чувствовал тогда, что это было не то, что я не имел на это права. Так и вышло». Он вспомнил медовый месяц, и покраснел при этом воспоминании. Особенно живо, оскорбительно и постыдно было для него воспоминание о том, как однажды, вскоре после своей женитьбы, он в 12 м часу дня, в шелковом халате пришел из спальни в кабинет, и в кабинете застал главного управляющего, который почтительно поклонился, поглядел на лицо Пьера, на его халат и слегка улыбнулся, как бы выражая этой улыбкой почтительное сочувствие счастию своего принципала.
«А сколько раз я гордился ею, гордился ее величавой красотой, ее светским тактом, думал он; гордился тем своим домом, в котором она принимала весь Петербург, гордился ее неприступностью и красотой. Так вот чем я гордился?! Я тогда думал, что не понимаю ее. Как часто, вдумываясь в ее характер, я говорил себе, что я виноват, что не понимаю ее, не понимаю этого всегдашнего спокойствия, удовлетворенности и отсутствия всяких пристрастий и желаний, а вся разгадка была в том страшном слове, что она развратная женщина: сказал себе это страшное слово, и всё стало ясно!
«Анатоль ездил к ней занимать у нее денег и целовал ее в голые плечи. Она не давала ему денег, но позволяла целовать себя. Отец, шутя, возбуждал ее ревность; она с спокойной улыбкой говорила, что она не так глупа, чтобы быть ревнивой: пусть делает, что хочет, говорила она про меня. Я спросил у нее однажды, не чувствует ли она признаков беременности. Она засмеялась презрительно и сказала, что она не дура, чтобы желать иметь детей, и что от меня детей у нее не будет».