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

Вход

LR(0)-грамматика

Выход

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

Алгоритм

Построим LR(0)-автомат $(Q,\Sigma \cup \Gamma ,\delta ,\nabla ,Q)$ по входной грамматике (должны уже были построить для проверки, что входная грамматика LR(0)-грамматика)

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

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

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

В каждой строке $q$ для $A\in \Gamma$ заносим состояние $\delta (q,A)$, если функция перехода определена