70
правок
Изменения
Нет описания правки
На вход подается [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматика]] <tex>G = (N, \Sigma, P, S)</tex> и строка <tex>w = a_1 a_2 \ldots a_n</tex> из <tex>\Sigma^*</tex>. Результатом работы алгоритма является [[Алгоритм Эрли#Определения|список разбора]] <tex>I_0, I_1, \ldots , I_n</tex> для строки <tex>w</tex>.
Для простоты добавим новый стартовый вспомогательный нетерминал <tex>S'''Построение </tex> и правило <tex>I_0S' \rightarrow S</tex>:'''.
<tex>I_0</tex> ∪= <tex>[S''Шаг \rightarrow \cdot S, 0]</tex> # Правило (0) — инициализация useful_loop(0) for i = 1.'' Для каждого правила .n for <tex>S [A \rightarrow \alpha\cdot a_{j} \beta, i] \in I_{j-1}</tex> из <tex>PI_j</tex>, включить ∪= <tex>[S A \rightarrow \alpha a_{j} \cdot \alphabeta, 0i]</tex> в <tex>I_0</tex>.# Правило (1) useful_loop(j)
==Время работы для однозначной грамматики==
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} однозначная КС-грамматика и <tex>a_1 \dots a_n</tex> {{---}} цепочка из <tex>\Sigma^*</tex>. Тогда алгоритм Эрли пытается включить <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> в <tex>I_j</tex> не более одного раза, если <tex>\alpha \ne \varepsilon</tex>.
|proof=
Ситуацию <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> можно включить в <tex>I_j</tex> только на шагах по правилам <tex>(21)</tex>, и <tex>(4)</tex>, или <tex>(52)</tex>. Если она включается на шаге по правилу <tex>(41)</tex>, то последний символ цепочки <tex>\alpha</tex> {{---}} терминал, а если на шагах по правилу <tex>(2)</tex> или <tex>(5)</tex>, то {{---}} нетерминал. В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>I_j</tex>, когда рассматриваются две различные ситуации <tex>[B \rightarrow \gamma \cdot, k]</tex> и <tex>[B \rightarrow \delta \cdot, l]</tex>. Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>I_k</tex> и в <tex>I_l</tex>.
#Пусть <tex>k \ne l</tex>. Тогда по [[Алгоритм Эрли#Корректность алгоритма|теореме]] существуют такие <tex>\theta_1, \theta_2, \theta_3</tex> и <tex>\theta_4</tex>, что <tex>S \Rightarrow^* \theta_1 A \theta_2 \Rightarrow \theta_1 \alpha' B \beta \theta_2 \Rightarrow^* a_1 \dots a_n</tex> и <tex>S \Rightarrow^* \theta_3 A \theta_4 \Rightarrow \theta_3 \alpha' B \beta \theta_4 \Rightarrow^* a_1 \dots a_n</tex>. Но в первом выводе <tex>\theta_1 \alpha' \Rightarrow^* a_1 \dots a_k</tex>, а во втором <tex>\theta_1 \alpha' \Rightarrow^* a_1 \dots a_l</tex>. Тогда для цепочки <tex>a_1 \dots a_n</tex> существуют два разных дерева вывода, в которых <tex>a_{i+1} \dots a_j</tex> выводится из <tex>\alpha' B</tex> двумя разными способами.
#Пусть <tex>k = l</tex>. Тогда <tex>\gamma \ne \delta</tex>. Тогда, так как <tex>[B \rightarrow \gamma \cdot, k] \in I_j</tex> и <tex>[B \rightarrow \delta \cdot, k] \in I_j</tex>, то <tex>\gamma \Rightarrow a_{k+1} \dots a_j</tex> и <tex>\delta \Rightarrow a_{k+1} \dots a_j</tex>, то есть <tex>a_{k+1} \dots a_j</tex> выводится двумя разными способами.
При построении <tex>I_0</tex> входная строка не учитывается, поэтому этот список можно построить за константное время.
Рассмотрим <tex>I_j, \, j > 0</tex>. Рассмотрим шаги <tex>(4)</tex>, <tex>(5)</tex> и <tex>(6)</tex>.# На шаге При включении ситуации по правилу <tex>(41)</tex> исследуется <tex>a_j</tex> и предыдущий список. Для каждой ситуации из <tex>I_{j-1}</tex> с символом <tex>a_j</tex>, расположенным справа от точки, в <tex>I_j</tex> включается некоторая ситуация. Так как список в <tex>I_{j-1}</tex> можно найти за <tex>O(1)</tex> по символу <tex>a_j</tex>, то на включение каждой ситуации в <tex>I_j</tex> будет потрачено <tex>O(1)</tex> операций.#Если применяется шаг правило <tex>(52)</tex>, то в некотором списке <tex>I_k</tex> для <tex>k \le j</tex> надо просмотреть все ситуации, содержащие <tex>"\cdot B"</tex> для некоторого конкретного <tex>B</tex>. Для каждой такой ситуации в <tex>I_j</tex> включается другая ситуация, и это время относится не к рассматриваемой ситуации, а к включаемой. Кроме того, так как по второй лемме для каждой ситуации предпринимается только одна попытка включить ее в список, то не нужно тратить время на проверку того, что включаемая ситуация уже есть в списке.#Так как грамматика фиксирована, то на шаге при применении правила <tex>(63)</tex> при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому на рассматриваемую ситуацию будет потрачено <tex>O(1)</tex> операций.
Таким образом, на каждую ситуацию в каждом списке тратится <tex>O(1)</tex> операций. Тогда, учитывая лемму 1, получаем, что время работы алгоритма составляет <tex>O(n^2)</tex>.
}}
==Литература==
*А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.
