70
правок
Изменения
Нет описания правки
<tex>\forall\,j: 1 \le j \le n</tex> в списке <tex>I_j</tex> находится <tex>O(j)</tex> ситуаций.
|proof=
Так как грамматика фиксирована, то <tex>\forall i</tex> количество ситуаций вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> не больше константногонекоторой константы. Таким образом, так как в <tex>I_j</tex> находятся ситуации, у которых <tex>0 \le i \le j</tex>, то всего в <tex>I_j</tex> будет <tex>O(j)</tex> ситуаций.
}}
Орагнизуем каждый список разбора <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_j, \, j > 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>O(1)</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(j1)</tex>операций.Таким образом, на каждую ситуацию тратится <tex>O(1)</tex> операций. Тогда, учитывая лемму 1, получаем, что время работы алгоритма составляет <tex>O(n^2)</tex>.
}}
==Литература==
*А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.
