LL(1)

FIRST(α): Множество всех терминалов, на которые может начинаться строка терминалов и нетерминалов α, или ε, если α ⇒* ε
FOLLOW(X): Множество терминалов a, таких, что существует порождение S ⇒* α X a β; Множество терминалов, которые могут следовать за нетерминалом X в каком-либо порождении.

Формально,

FIRST(α) = { a ∈ T | α ⇒* a β } ∪ { ε | α ⇒* ε }

FOLLOW(X) = { a ∈ T | S ⇒* α X a β }

Таблица переходов M[A,a] LL(1)-анализатора

∀ (A → α) ∈ G: ∀ a ∈ T, a ∈ FIRST(α): M[A, a] = α; если ε ∈ FIRST(α), то ∀ b ∈ FOLLOW(A) M[A,b] = α.

Перенос/свёртка

Идея восходящего синтаксического анализа в том, чтобы начать с “листьев” дерева разбора и восстановить по ним весь путь порождения в обратном направлении.

Можно рассматривать процесс восходящего анализа как процесс “свёртки” некого порождения обратно к стартовому символу. То есть, свёртка по сути – операция обратная порождению.

Синтаксический анализ “перенос/свёртка” – вариант восходящего синтаксического анализа, при котором кроме принятия и ошибки анализатор может совершать две операции:

Перенос : Следующий терминал переносится из входного буфера на вершину стека

Свёртка : Некоторое количество символов на вершине стека “сворачивается” в нетерминал (операция обратная правому порождению)

Реализуется такой механизм стековой машиной, изначально стек пуст, входной буфер полон. В конце анализа, на стеке находится только стартовый символ, входной буфер пуст.

Не все контекстно-свободные грамматики можно разобрать используя анализ перенос/свёртка. В таких грамматиках может возникать два типа конфликтов:

Конфликт перенос/свёртка : На очередном шаге анализа, анализатор не может совершить однозначный выбор между действиями преноса или свёртки. Пример: грамматика с висящим else.

Конфликт свёртка/свёртка : На очередном шаге анализа, анализатор не может сделать выбор между двумя разными свёртками

SLR

Наиболее распространённый тип восходящего анализа – LR(k)-анализ. Наибольший практический интерес представляют случаи LR(0) и LR(1).

LR-грамматики – истинное надмножество LL-грамматик. В LR-анализе мы должны распознать правую часть продукции на вершине стека с дополнительным предпросмотром k входных символов. Это требование гораздо более мягкое, чем для LL(k) грамматик где необходимо “угадать” продукцию по первым k символам некого порождения её правой части.

Недостаток LR-анализа в относительной сложности построения анализатора.

Пункты и LR(0)

LR-анализатор принимает решение о выборе между переносом и свёрткой, отслеживая, в каком месте тела продукции находится анализ. Это реализуется при помощи состояний, называемых “пунктами”. LR(0)-пункты описываются в виде продукций с точкой в “текущем” месте. Так, продукция A → X Y Z имеет 4 пункта

A → . X Y Z

A → X . Y Z

A → X Y . Z

A → X Y Z .

Продукция с пустым телом A → ε имеет единственный пункт A → .

Один набор пунктов LR(0), называемый каноническим служит для построения ДКА, называемого LR(0)-автоматом, который используется в процессе анализа. Каждое состояние такого автомата представляет множество LR(0)-пунктов.

Замыкание множества пунктов

Пусть I – множество пунктов грамматики G. Тогда I⁺ – замыкание множества пунктов, соответствующее правилу: Если A → α . B β ∈ I⁺, и ∃ B → γ, то B → . γ ∈ I⁺.

Интуитивно, если в замыкании присутствует A → α . B β, то мы ожидаем во входной строке порождения из B, и поэтому мы добавляем первые пункты всех продукций B в замыкание.

Функция переходов

Вторая часть, определяющая LR(0)-автомат – функция переходов GOTO. Переход в LR(0)-анализе однозначно определяется текущим состоянием (множеством пунктов I) и текущим грамматическим символом X.

GOTO(I,X) = { A → α X . β | A → α . X β ∈ I }⁺

Канонический набор множеств пунктов LR(0)

Канонический набор С строится на основе функции переходов начиная с первого пункта стартовой продукции.

Начиная с первого пункта стартовой продукции, для каждого множества пунктов I в C и каждого грамматического символа X множество GOTO(I,X) должно входить в C.

SLR

SLR использует LR(0)-автомат следующим образом:

Пусть строка γ переводит автомат из состояния 0 в состояние j. Тогда, если состояние j имеет переход для символа a, выполним перенос этого символа. Иначе, выполним свёртку по продукции, последний пункт которой соответствует текущему состоянию j. При этом, при свёртке, j снимается со стека и ищется переход из предыдущего сотояния по нетерминалу, в который произведена свёртка.

LR-анализаторы используют стек для хранения состояний; символы грамматики могут быть восстановлены по ним.

Алгоритм SLR дополнительно ограничивает случаи, когда возможна свёртка на основе функции FOLLOW.

В общем случае, LR-анализатор управляется стеком состояний, текущим входным символом и двумя таблицами, таблицей действий ACTION и таблицей переходов GOTO. Последняя строится по функции переходов, первая же может отличаться в зависимости от типа анализа.

Таблица действий определяется текущим состоянием на вершине стека и текущим входным терминалом.

В случае SLR-анализа, действия определяются следующим образом:

Если для состояния i, [A → α . a β] ∈ i и GOTO(i, a) = j, то ACTION[i, a] = перенос j. a – терминал.
Если [A → α .] ∈ i, то ∀ a ∈ FOLLOW(A): ACTION[i, a] = свёртка A → α.

LR(1)

LR(1) аналогичен SLR, с одним ключевым отличием: дабы исключить часть конфликтов перенос/свёртка, LR(1)-пункты дополнительно включают один символ предпросмотра, то есть LR(1)-пункт может иметь вид, скажем [A → α . B β, a]. Здесь a – это символ, который следует после β.

Соответственно модифицируются определения замыканий LR(1)-пунктов и функция переходов.

Замыкание : Пусть I – множество пунктов грамматики G. Тогда I⁺ – замыкание множества пунктов, соответствующее правилу: Если [A → α . B β, a] ∈ I⁺, и ∃ B → γ, то ∀ b ∈ FIRST(β a) [B → . γ, b] ∈ I⁺.

Это определение интуитивно понятно: после строки α B β мы ожидаем терминал a; тогда после B разумно ожидать терминалы, входящие в FIRST(β a) (полагая, что возможно β=ε).

Определение GOTO практически не меняется, так как переход не влияет на символ предпросмотра.

GOTO(I,X) = { [A → α X . β, a] | [A → α . X β, a] ∈ I }⁺

Таблица действий строится как

Если для состояния i, [A → α . a β, b] ∈ i и GOTO(i, a) = j, то ACTION[i, a] = перенос j. a – терминал.
Если [A → α ., a] ∈ i, ACTION[i, a] = свёртка A → α.

LALR(1)

LALR(1) – это упрощение LR(1), в котором используется множество пунктов LR(0), но каждый из них расширен множеством допустимых символов предпросмотра из соответствующих LR(1)-пунктов. При этом, количество состояний совпадает с количеством состояний в SLR, но вероятность возникновения конфликтов перенос/свёртка ниже – хотя и выше чем в полноценном LR(1) анализе.

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

lr