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

Модификация алгоритма, обеспечивающая построение бесконфликтного LR-анализатора для более широкого, чем LR(0) класса грамматик

Вход

Расширенная грамматика

Выход

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

Алгоритм

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

0. Занумеровать правила грамматики от одного до $k$
1. Построить LR(0)-автомат $(Q,\Sigma \cup \Gamma ,\delta ,\nabla ,Q)$ по входной грамматике
2. Построить множества FOLLOW (можно воспользоваться алгоритмом построение множества FOLLOW)
3. В строке, соответствующей состоянию $[S^{\prime }\to S\bullet ]$ в столбце $⊣$ заносим допуск ​
4. В каждой строке $q$ (состояние автомата), не заполненной в 3):
   • Для каждого пункта $p=[A\to \alpha \bullet ]\in q$ в столбцах $a\in FOLLOW(A)$ заносим свертку $\otimes n$ ($n$ - номер соответствующего правила рассматриваемого пункта $p$)
   • Для каждого пункта $[A\to {\beta }_1\bullet a{\beta }_2]\in q,{\beta }_1,{\beta }_2\in (\Sigma \cup \Gamma {)}^{\ast },a\in \Sigma$ в столбце $a$ заносим перенос $\leftarrow \delta (q,a)$

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

В каждой строке $q$ для каждого пункта $[A\to {\beta }_1\bullet B{\beta }_2]\in q,{\beta }_1,{\beta }_2\in (\Sigma \cup \Gamma {)}^{\ast },B\in \Gamma$ в столбец $B$ заносим состояние $\delta (q,B)$