LR (1) анализ. LR (1) — ситуация. 
Замыкание множества ситуаций. 
Определение переходов

LR (1) — ситуация. В описании добавляется инфа о том, какие символы м б текущими во время свертки. [A-> б^.в₁a]. Такая ситуация считается допустимой для активного префикса г, если существует вывод B=> ^. дAw=>дбвw.

Замыкание множества ситуаций closure (I) определяется индуктивно.

Базовый случай: I € closure (I).

Шаг индукции: Если [A-> б^. Bв, a] € closure (I) и существует продукция В->г, тогда [B->^. г, b] € closure (I) для всех b € FIRST (вa).

Определение переходов. Если ситуация [A-> б^.xб, a] € closure (I), то goto (I, x) строит замыкание вида [A-> бх^. в, a].

LR (1) Анализ. заполнение таблиц LR разбора

• * LR (1)?анализ? наиболее мощный метод анализа без возвратов типа сдвиг? свертка;
• * LR (1)?анализ может быть реализован довольно эффективно;
• * LR (1)?анализаторы могут быть построены для практически всех конструкций языков программирования;
• * класс грамматик, которые могут быть проанализированы LR (1)?методом, строго включает класс грамматик,

которые могут быть проанализированы предсказывающими анализаторами (сверху?вниз типа LL (1)).

Анализатор состоит из входной ленты, выходной ленты, магазина, управляющей программы и таблицы анализа (LR (1)-таблицы), которая имеет две части — функцию действий (Action) и функцию переходов (Goto). Управляющая программа одна и та же для всех LR (1)-анализаторов, разные анализаторы отличаются только таблицами анализа.

Анализатор читает символы на входной ленте по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S0X1S1X2S2 … XmSm (Sm — верхушка магазина). Каждый Xi — символ грамматики (терминальный или нетерминальный), а Si — символ состояния.

Заметим, что символы грамматики (либо символы состояний) не обязательно должны размещаться в магазине. Однако, их использование облегчает понимание поведения LR-анализатора.

Элемент функции действий Action[Sm; ai] для символа состояния Sm и входа, может иметь одно из четырех значений:

• 1. shift S (сдвиг), где S? символ состояния,
• 2. reduce A г (свертка по правилу грамматики A г),
• 3. accept (допуск),
• 4. error (ошибка).

Алгоритм заполнения таблиц анализа заключается в следующем.

• 1 Построить каноническую совокупность множества ситуаций.
• 2 Каждое множество I канонической совокупности определяет состояние конечного автомата с соответствующим номером, а следовательно строку в таблицах анализа. Ячейки в таблице заполняются по следующим вариантам.
• а) Если ситуация [Aa] принадлежит множеству I_i и существует переход по терминалу a в некоторое множество I_j, то в ячейку action (i, a) значение shift j. В приведенной ситуации основа не может быть найдена, так как для ее завершения как минимум необходимо распознать терминал a, то есть выполнить сдвиг.
• б) Если ситуация [A] принадлежит множеству I_i, то для всех терминалов а, принадлежащих follow (A), в ячейку action[i, a] заносим значение reduce A. Это происходит потому что основа найдена полностью и распознавание любого символа, следующего за А, должно привести к приведению основы.
• в) Если ситуация [SS], принадлежит множеству I_i, то есть можно осуществить редукцию для стартовой продукции, то в ячейку action[I, eof] записываем значение accept. То есть разбор успешно закончен, если достигнут конец входной последовательности.
• 3 Если существует переход из множества I_i в множество I_j по некоторому нетерминалу А, то в ячейку goto[i, А] заносим значение j.
• 4 Все незаполненные ячейки в таблицах action и goto заполняем значением «ошибка».
• 5 Начальным состояние автомата является состояние, содержащее ситуацию [SS]