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

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

Пусть [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]\omega[/math]. [math]\cdot[/math] является метасимволом, не принадлежащим ни [math]N[/math], ни [math]\Sigma[/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]\omega[/math] Строим [math]I_0[/math]
Шаг 1. Если [math]S \rightarrow \alpha \in P[/math], включить [math][S \rightarrow \cdot \alpha, 0][/math] в [math]I_0[/math].
Пока можно включить новые ситуации в [math]I_0[/math] повторяем шаги 2 и 3.
Шаг 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]\gamma[/math] таких, что [math]B \rightarrow \gamma \in P[/math] включить [math][B \rightarrow \cdot \gamma, 0][/math] в [math]I_0[/math].
Построение [math]I_j[/math] по [math]I_0, I_1, ..., I_{j-1}[/math].
Шаг 4. Для каждой ситуации [math][B \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}[/math], [math]a_j[/math]— j-й символ в [math]\omega[/math] включить [math][B \rightarrow \alpha a \cdot \beta, i] [/math] в [math]I_j[/math].
Пока можно включить новые ситуации в [math]I_j[/math] повторяем шаги 5 и 6.
Шаг 5. Если [math][A \rightarrow \alpha \cdot , i] \in I_j[/math], то для каждой ситуации [math][B \rightarrow \gamma \cdot A \beta, k] \in I_{i}[/math] включить [math][B \rightarrow \gamma A \cdot \beta, k][/math] в [math]I_j[/math].
Шаг 6. Для всех [math][A \rightarrow \alpha \cdot B \beta, i] \in I_j[/math], для всех [math]\gamma[/math] таких, что [math]B \rightarrow \gamma \in P[/math] включить [math][B \rightarrow \cdot \gamma, j][/math] в [math]I_j[/math].
Если [math][S \rightarrow \alpha \cdot, 0] \in I_n[/math], то [math]\omega \in L(G) [/math].

Корректность алгоритма

Теорема:

[math][A \rightarrow \alpha \cdot \beta, i] \in I_{j} \Leftrightarrow \alpha \Rightarrow^* a_{i+1}...a_{j}[/math] и [math] \mathcal {9} \gamma [/math] и [math] \delta[/math] такие, что [math]S \Rightarrow^* \gamma A \delta[/math] и [math] \gamma \Rightarrow^* a_1...a_{i}[/math]

Доказательство:

[math]\triangleright[/math]

Необходимость Докажем по индукции. База: для любой ситуации из [math]I_0[/math] [math]\alpha \Rightarrow^* \varepsilon [/math] и [math]S \Rightarrow^* \gamma A \delta [/math] при [math]\gamma = \varepsilon [/math]. Индукционный переход (и.п.): пусть верно для всех ситуаций из списков [math] I_{i}, i \leqslant j [/math]. Пусть включаем [math][A \rightarrow \alpha \cdot \beta, i] [/math] в [math]I_{j}[/math]. Рассмотрим три случая: Пусть включаем по правилу 4 Тогда [math]\alpha = \alpha' a_{j} , [A \rightarrow \alpha' \cdot a_{j} \beta, i] \in I_{j-1}[/math]. По и.п. [math]\alpha' \Rightarrow^* a_{i+1}...a_{j-1} [/math]и существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{i} [/math]. Значит [math] \alpha = \alpha' a_{j} \Rightarrow^* a_{i+1}...a_{j}[/math] и при [math]\gamma = \gamma', \delta = \delta' [/math] для [math][A \rightarrow \alpha \cdot \beta, i][/math] утверждение верно. Пусть включаем по правилу 5 Тогда [math]\alpha = \alpha' B , [A \rightarrow \alpha' \cdot B \beta, k] \in I_{i}[/math] и [math] [B \rightarrow \eta \cdot, i] \in I_{j} [/math]. По и.п. [math]\alpha' \Rightarrow^* a_{k+1}...a_{i}, \eta \Rightarrow^* a_{i+1}...a_{j} [/math], откуда [math]\alpha = \alpha' B \Rightarrow^*a_{k+1}...a_{j} [/math]. Также по и.п. существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S \Rightarrow^* \gamma' A \delta', \gamma' = a_1...a_{k} [/math]. Значит при [math]\gamma = \gamma', \delta = \delta' [/math] для [math][A \rightarrow \alpha \cdot \beta, i][/math] утверждение верно. Пусть включаем по правилу 6 Тогда [math]\alpha = \varepsilon, i = j, [B \rightarrow \alpha' \cdot A \beta, k] \in I_{j}[/math]. По и.п. [math]\alpha' \Rightarrow^* a_{k+1}...a_{i}[/math] и существуют [math]\gamma'[/math] и [math]\delta' [/math] такие, что [math]S \Rightarrow^* \gamma' B \delta', \gamma' = a_1...a_{k} [/math]. Значит при [math]\gamma = \gamma' \alpha', \delta = \beta \delta' [/math] выполнено [math] S \Rightarrow^* \gamma A \delta[/math], значит для [math][A \rightarrow \alpha \cdot \beta, i][/math] утверждение верно.

[math]\triangleleft[/math]

Литература

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