Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики

Алгоритм

Приведем Алгоритм Эрли.

На вход подается КС-грамматика [math]G = (N, \Sigma, P, S)[/math] и строка [math]w = a_1 a_2 \ldots a_n[/math] из [math]\Sigma^*[/math]. Результатом работы алгоритма является список разбора [math]I_0, I_1, \ldots , I_n[/math] для строки [math]w[/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].

Выполнять шаги [math](2)[/math] и [math](3)[/math] до тех пор, пока в [math]I_0[/math] можно включать новые ситуации.

Шаг 2. Если [math][B \rightarrow \gamma \cdot, 0] \in I_0[/math], то для всех [math][A \rightarrow \alpha \cdot B \beta, 0] \in I_0[/math] включить в [math]I_0[/math] ситуацию [math][A \rightarrow \alpha B \cdot \beta, 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_0, I_1, \ldots , I_{j-1}[/math], строится [math]I_j[/math]:

Шаг 4. Для каждой ситуации [math][B \rightarrow \alpha \cdot a_j \beta, i] \in I_{j-1}[/math] включить в [math]I_j[/math] ситуацию [math][B \rightarrow \alpha a_j \cdot \beta, i][/math].

Выполнять шаги [math](5)[/math] и [math](6)[/math] до тех пор, пока в [math]I_j[/math] можно включать новые ситуации.

Шаг 5. Если [math][A \rightarrow \alpha \cdot, i] \in I_j[/math], то для всех ситуаций [math][B \rightarrow \alpha \cdot A \beta, k] \in I_i[/math] включить [math][B \rightarrow \alpha A \cdot \beta, k][/math] в [math]I_j[/math].

Шаг 6. Если [math][A \rightarrow \alpha \cdot B \beta, i] \in I_j[/math], то для всех правил [math]B \rightarrow \gamma[/math] из [math]P[/math] включить [math][B \rightarrow \cdot \gamma, j][/math] в [math]I_j[/math].

Время работы для однозначной грамматики

Лемма (1):

[math]\forall\,j: 1 \le j \le n[/math] в списке [math]I_j[/math] находится [math]O(j)[/math] ситуаций.

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

[math]\triangleright[/math]

Так как грамматика фиксирована, то [math]\forall i[/math] количество ситуаций вида [math][A \rightarrow \alpha \cdot \beta, i][/math] не больше некоторой константы. Таким образом, так как в [math]I_j[/math] находятся ситуации, у которых [math]0 \le i \le j[/math], то всего в [math]I_j[/math] будет [math]O(j)[/math] ситуаций.

[math]\triangleleft[/math]

Лемма (2):

Пусть [math]G = (N, \Sigma, P, S)[/math] — однозначная КС-грамматика и [math]a_1 \dots a_n[/math] — цепочка из [math]\Sigma^*[/math]. Тогда алгоритм Эрли пытается включить [math][A \rightarrow \alpha \cdot \beta, i][/math] в [math]I_j[/math] не более одного раза, если [math]\alpha \ne \varepsilon[/math].

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

[math]\triangleright[/math]

Ситуацию [math][A \rightarrow \alpha \cdot \beta, i][/math] можно включить в [math]I_j[/math] только на шагах [math](2)[/math], [math](4)[/math], или [math](5)[/math]. Если она включается на шаге [math](4)[/math], то последний символ цепочки [math]\alpha[/math] — терминал, а если на шагах [math](2)[/math] или [math](5)[/math], то — нетерминал. В первом случае результат очевиден. Во втором случае допустим, что [math][A \rightarrow \alpha'B \cdot \beta, i][/math] включается в [math]I_j[/math], когда рассматриваются две различные ситуации [math][B \rightarrow \gamma \cdot, k][/math] и [math][B \rightarrow \delta \cdot, l][/math]. Тогда ситуация [math][A \rightarrow \alpha' \cdot B\beta, i][/math] должна оказаться одновременно в [math]I_k[/math] и в [math]I_l[/math]. Пусть [math]k \ne l[/math]. Тогда по теореме существуют такие [math]\theta_1, \theta_2, \theta_3[/math] и [math]\theta_4[/math], что [math]S \Rightarrow^* \theta_1 A \theta_2 \Rightarrow \theta_1 \alpha' B \beta \theta_2 \Rightarrow^* a_1 \dots a_n[/math] и [math]S \Rightarrow^* \theta_3 A \theta_4 \Rightarrow \theta_3 \alpha' B \beta \theta_4 \Rightarrow^* a_1 \dots a_n[/math]. Но в первом выводе [math]\theta_1 \alpha' \Rightarrow^* a_1 \dots a_k[/math], а во втором [math]\theta_1 \alpha' \Rightarrow^* a_1 \dots a_l[/math]. Тогда для цепочки [math]a_1 \dots a_n[/math] существуют два разных дерева вывода, в которых [math]a_{i+1} \dots a_j[/math] выводится из [math]\alpha' B[/math] двумя разными способами. Пусть [math]k = l[/math]. Тогда [math]\gamma \ne \delta[/math]. Тогда, так как [math][B \rightarrow \gamma \cdot, k] \in I_j[/math] и [math][B \rightarrow \delta \cdot, k] \in I_j[/math], то [math]\gamma \Rightarrow a_{k+1} \dots a_j[/math] и [math]\delta \Rightarrow a_{k+1} \dots a_j[/math], то есть [math]a_{k+1} \dots a_j[/math] выводится двумя разными способами.

[math]\triangleleft[/math]

Теорема:

Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины [math]n[/math] составляет [math]O(n^2)[/math].

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

[math]\triangleright[/math]

Орагнизуем каждый список разбора [math]I_j[/math] таким образом, чтобы по любому символу [math]x \in \Sigma \cup N[/math], можно было за [math]O(1)[/math] получить список тех и только тех ситуаций, содержащихся в [math]I_j[/math], которые имеют вид [math][A \rightarrow \alpha \cdot x \beta, j][/math]. При построении [math]I_0[/math] входная строка не учитывается, поэтому этот список можно построить за константное время. Рассмотрим [math]I_j, \, j \gt 0[/math]. Рассмотрим шаги [math](4)[/math], [math](5)[/math] и [math](6)[/math]. На шаге [math](4)[/math] исследуется [math]a_j[/math] и предыдущий список. Для каждой ситуации из [math]I_{j-1}[/math] с символом [math]a_j[/math], расположенным справа от точки, в [math]I_j[/math] включается некоторая ситуация. Так как список в [math]I_{j-1}[/math] можно найти за [math]O(1)[/math] по символу [math]a_j[/math], то на включение каждой ситуации в [math]I_j[/math] будет потрачено [math]O(1)[/math] операций. Если применяется шаг [math](5)[/math], то в некотором списке [math]I_k[/math] для [math]k \le j[/math] надо просмотреть все ситуации, содержащие [math]"\cdot B"[/math] для некоторого конкретного [math]B[/math]. Для каждой такой ситуации в [math]I_j[/math] включается другая ситуация, и это время относится не к рассматриваемой ситуации, а к включаемой. Кроме того, так как по второй лемме для каждой ситуации предпринимается только одна попытка включить ее в список, то не нужно тратить время на проверку того, что включаемая ситуация уже есть в списке. Так как грамматика фиксирована, то на шаге [math](6)[/math] при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому на рассматриваемую ситуацию будет потрачено [math]O(1)[/math] операций. Таким образом, на каждую ситуацию тратится [math]O(1)[/math] операций. Тогда, учитывая лемму 1, получаем, что время работы алгоритма составляет [math]O(n^2)[/math].

[math]\triangleleft[/math]

Литература

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