70
правок
Изменения
Нет описания правки
{{Лемма
|about=1
|statement=
<tex>\forall\,j: 1 \le j \le n</tex> в списке <tex>I_j</tex> находится <tex>O(j)</tex> ситуаций.
|proof=
}}
{{Лемма
|about=2
|statement=
Пусть <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>.
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины <tex>n</tex> составляет <tex>O(n^2)</tex>.
|proof=
Орагнизуем каждый список разбора <tex>I_j</tex> таким образом, чтобы по любому символу <tex>x \in \Sigma \cup N</tex>, можно было за <tex>O(1)</tex> получить список тех и только тех ситуаций, содержащихся в <tex>I_j</tex>, которые имеют вид <tex>[A \rightarrow \alpha \cdot x \beta, j]</tex>.
Покажем, что на каждую ситуацию алгоритм расходует фиксированное количество времени.
Список <tex>I_0</tex> можно построить за фиксированное время.
Рассмотрим <tex>I_j, \, j \ge 0</tex>. Рассмотрим шаги <tex>(4)</tex>, <tex>(5)</tex> и <tex>(6)</tex>.
# На шаге <tex>(4)</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>(5)</tex>, то в некотором списке <tex>I_k</tex> для <tex>k \le j</tex> надо просмотреть все ситуации, содержащие <tex>"\cdot B"</tex> для некоторого конкретного <tex>B</tex>. Для каждой такой ситуации в <tex>I_j</tex> включается другая ситуация, и это время относится не к рассматриваемой ситуации, а к включаемой. Кроме того, так как по второй лемме для каждой ситуации предпринимается только одна попытка включить ее в список, то не нужно тратить время на проверку того, что включаемая ситуация уже есть в списке.
#Так как размер грамматики фиксирован, то , учитывая первую лемму, получаем, что шаг <tex>(6)</tex> выполняется за <tex>O(j)</tex>.
Таким образом, время работы алгоритма составляет <tex>O(n^2)</tex>.
}}
