Алгоритм Эрли

Определение:

Пусть [math]G = (N, \Sigma, P, S)[/math] — контекстно свободная грамматика и [math]\omega = a_1 a_2 ... a_n[/math] — входная цепочка из [math]\Sigma^*[/math]. Объект вида [math][A \rightarrow X_1 X_2 ... X_k \cdot X_{k+1} ... X_m, i][/math] назовем ситуацией, относящейся к цепочке [math]\omega[/math], если [math]A \rightarrow X_1 ... X_m [/math] — правило из [math]P[/math] и [math]0 \leqslant i \leqslant n[/math]. [math]\cdot[/math] является метасимволом, не принадлежащим ни [math]N[/math], ни [math]\Sigma[/math]. [math]k \in \mathbb{N}, 0 \leqslant k \leqslant m[/math].

Определение:

Для каждого [math]0 \leqslant j \leqslant n[/math] построим список ситуаций [math]I_j[/math] такой, что [math][A \rightarrow \alpha \cdot \beta , i] \in I_j[/math] для [math]0 \leqslant j \leqslant n[/math] тогда и только тогда, когда для некоторых [math]\gamma[/math] и [math]\delta[/math] существуют выводы [math]S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i[/math] и [math]\alpha \Rightarrow^* a_{i+1} ... a_j[/math].

Определение:

Последовательность списков [math]I_0, I_1, ..., I_n[/math] называется списком разбора для входной цепочки [math]\omega[/math].

Алгоритм Эрли

Вход. контекстно свободная грамматика [math]G = (N, \Sigma, P, S)[/math] и входная цепочка [math]\omega = a_1 a_2 ... a_n[/math].
Выход. Список разбора [math]I_0, I_1, ... I_n[/math] для цепочки [math]\omega[/math].
Метод.
Строим [math]I_0[/math]
Шаг 1. Если [math]S \rightarrow \alpha[/math] — правило из [math]P[/math], включить [math][S \rightarrow \cdot \alpha, 0][/math] в [math]I_0[/math].
Выполняем шаги 2 и 3 до тех пор, пока можем включать новые ситуации в [math]I_0[/math].
Шаг 2. Если [math][B \rightarrow \gamma \cdot, 0] \in I_0[/math], включить в [math]I_0[/math] ситуацию [math][A \rightarrow \alpha B \cdot \beta, 0][/math] для всех [math][A \rightarrow \alpha \cdot B \beta, 0][/math], уже принадлежащих [math]I_0[/math].
Шаг 3. Допустим, что [math][A \rightarrow \alpha \cdot B \beta, 0] \in I_0[/math]. Для каждого правила из [math]P[/math] вида [math]B \rightarrow \gamma[/math] включить в [math]I_0[/math] ситуацию [math][B \rightarrow \cdot \gamma, 0][/math] (если она еще не там).
Построение [math]I_j[/math] по [math]I_0, I_1, ..., I_{j-1}[/math].
Шаг 4. Для каждой ситуации [math][B \rightarrow \alpha \cdot a \beta, i] \in I_{j-1}[/math], для которой [math]a = a_j[/math] включить в [math]I_j[/math] ситуацию [math][B \rightarrow \alpha a \cdot \beta, i] [/math].
Выполняем шаги 5 и 6 до тех пор, пока можем включать новые ситуации в [math]I_j[/math].
Шаг 5. Пусть [math][A \rightarrow \alpha \cdot , i] \in I_j[/math]. Ищем ситуации вида [math][B \rightarrow \alpha \cdot A \beta, k][/math]. Для каждой из них включить в [math]I_j[/math] ситуацию [math][B \rightarrow \alpha A \cdot \beta, k][/math].
Шаг 6. Пусть [math][A \rightarrow \alpha \cdot B \beta, i] \in I_j[/math]. Для каждого [math]B \rightarrow \gamma[/math] из [math]P[/math] включить в [math]I_j[/math] ситуацию [math][B \rightarrow \cdot \gamma, j][/math].
Вычисляем все [math]I_j[/math] для [math]0 \leqslant j \leqslant n[/math].
[math]\omega \in L(G) \Leftrightarrow [S \rightarrow \alpha \cdot, 0] \in I_n[/math].

Литература

• А.Ахо, Дж. Ульман. Теория синтакического анализа, перевода и компиляции. Том 1. Синтактический анализ.