Алгоритм. Построение LR(1)-анализатора

Вход

Расширенная грамматика $G=(\Sigma ,\Gamma ,P,S)$

Выход

LR(1)-анализатор

Алгоритм

Подготовка

Построим LR(1)-автомат $(Q,\Sigma \cup \Gamma ,\delta ,\nabla ,Q_0)$ по входной грамматике

Заполнение таблицы ACTION

0. Занумеровать правила грамматики от 1 до $k$
1. В строке состояния $[S^{\prime }\to S\bullet ,⊣]$ в столбце $⊣$ заносим допуск $\surd$
2. В строках состояний $[A\to \alpha \bullet ,a]$ (кроме $[S^{\prime }\to S\bullet ,⊣]$) в столбце $a\in \Sigma \cup \{⊣\}$ заносим свертку $\otimes n$ ($n:A\to \alpha$), где $n=1\dots k$
3. В строках $q$, не заполненных ранее, для каждого $a\in \Sigma \cup \{⊣\}$: Если есть пункт $[A\to {\beta }_1\bullet a{\beta }_2,b]$, то в столбце $a$ заносим перенос $\leftarrow \delta (q,a)$

Заполнение таблицы GOTO

В каждой строке $q$ для каждого $B\in \Gamma$:

• Если существует пункт $[A\to {\beta }_1\bullet B{\beta }_2,b]$, то в столбце $B$ заносим состояние $\delta (q,B)$, $B\in \Gamma$