317
правок
Изменения
→Алгоритм
==Алгоритм==
'''function'''Построение <tex>I_0\mathtt{earleyMod}(G, w)</tex>: <font color=green>// Инициализация </font> <tex> D_{0} = \lbrace [S'\rightarrow \cdot S, 0] \rbrace </tex> rulesLoop(0) '''for''' j = 1 .. n '''for''' <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in D_{j-1}</tex> <tex>D_j</tex> <tex> \cup</tex> = <tex>[A \rightarrow \alpha a_{j} \cdot \beta, i]</tex> <font color=green>// Первое правило </font> rulesLoop(j)
''Шаг 1.'function' Для каждого правила '' <tex>\mathtt{rulesLoop(j)}</tex>: <tex>D_j'' = D_j</tex> '''while''' <tex>D_j'' \ne \varnothing</tex> <tex>D_j' = D_j''</tex> <tex>D_j'' = \varnothing</tex> '''for''' <tex>[B \rightarrow \eta \cdot , i] \in D_j'</tex> <font color=green>// Цикл (*) </font> '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_{i}</tex> <tex>D_j''</tex> <tex>S \cup</tex> = <tex>[A \rightarrow \alphaB \cdot \beta, k] </tex> из <font color=green>// Второе правило </font> '''for''' <tex>[B \rightarrow \alpha \cdot A \eta, k] \in D_j'</tex> <font color=green>// Цикл (**) </font> '''for''' <tex>\beta : (A \rightarrow \beta) \in P</tex>, включить <tex>D_j''</tex> <tex> \cup</tex> = <tex>[S A \rightarrow \cdot \alphabeta, 0j]</tex> в <font color=green>// Третье правило </font> <tex>D_j</tex> <tex> \cup</tex> = <tex>I_0D_j''</tex>.
==Время работы для однозначной грамматики==
|about=1
|statement=
<tex>\forall\,j: 1 \le leqslant j \le leqslant n</tex> в списке <tex>I_jD_j</tex> находится <tex>O(j)</tex> ситуаций.
|proof=
Так как грамматика фиксирована, то <tex>\forall i</tex> количество ситуаций вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> не больше константногонекоторой константы. Таким образом, так как поскольку в <tex>I_jD_j</tex> находятся ситуации, у которых <tex>0 \le leqslant i \le leqslant j</tex>, то всего в <tex>I_jD_j</tex> будет <tex>O(j)</tex> ситуаций.
}}
{{Лемма
|about=2
|statement=
Пусть <tex>G \Gamma = (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_jD_j</tex> не более одного раза, если <tex>\alpha \ne \varepsilon</tex>.
|proof=
Ситуацию <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> можно включить в <tex>I_jD_j</tex> только на шагах по правилам <tex>(21)</tex>, <tex>(4)</tex>, или <tex>(5)</tex>. Если она включается на шаге <tex>(4)</tex>, то если последний символ цепочки <tex>\alpha</tex> {{---}} — терминал, а если на шагах ) и <tex>(2)</tex> или <tex>(5если нетерминал)</tex>, то {{---}} нетерминал. В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>I_jD_j</tex>, когда рассматриваются две различные ситуации <tex>[B \rightarrow \gamma eta_1 \cdot, kk_1]</tex> и <tex>[B \rightarrow \delta eta_2 \cdot, lk_2]</tex>(они различны, так как в цикле <tex>(*)</tex> каждая ситуация из каждого списка рассматривается по одному разу). Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>I_kD_{k_1}</tex> и в <tex>I_lD_{k_2}</tex>.Таким образом, получаем:#Пусть * <tex>k \ne lalpha' \Rightarrow^* a_{i+1} \ldots a_{k_1}</tex>. Тогда по [[Алгоритм Эрли#Корректность алгоритма|теореме]] существуют такие и <tex>\theta_1, alpha' \theta_2, Rightarrow^* a_{i+1} \theta_3ldots a_{k_2}</tex> и ;* <tex>\theta_4eta_1 \Rightarrow^* a_{k_1+1} \ldots a_j</tex>, что и <tex>S \eta_2 \Rightarrow^* a_{k_2+1} \ldots a_j</tex>.Следовательно, <tex>\theta_1 A alpha' \theta_2 eta_1 \Rightarrow ^* a_{i+1} \theta_1 ldots a_j</tex> и <tex>\alpha' B \beta \theta_2 eta_2 \Rightarrow^* a_1 a_{i+1} \dots a_nldots a_j</tex> и .<br/>Заметим, что <tex>S \Rightarrow^* \theta_3 gamma A \delta \Rightarrow^* a_1 \ldots a_i A \theta_4 delta \Rightarrow a_1 \theta_3 ldots a_i \alpha' B \beta \theta_4 delta</tex>. Предположим, что <tex>\beta \delta \Rightarrow^* a_1 \dots a_nw'</tex>(ведь в грамматике нет непорождающих нетерминалов). Но в первом выводе Тогда <tex>\theta_1 \alpha' S \Rightarrow^* a_1 \dots a_kldots a_i \alpha' \eta_1 w'</tex>, а во втором и аналогично <tex>\theta_1 \alpha' S \Rightarrow^* a_1 \dots a_lldots a_i \alpha' \eta_2 w'</tex>. Тогда для цепочки <br/>Таким образом, если <tex>a_1 k_1 \dots a_nne k_2</tex> существуют два разных дерева вывода, в которых то подстрока <tex>a_{i+1} \dots ldots a_j</tex> выводится двумя различными способами из <tex>\alpha' B\eta_1</tex> двумя разными способами.#Пусть и <tex>k = l\alpha' \eta_2</tex>. Тогда (поскольку в первом случае <tex>\gamma alpha' \ne Rightarrow^* a_{i+1} \deltaldots a_{k_1}</tex>. Тогда, так как а во втором <tex>[B \rightarrow alpha' \gamma Rightarrow^* a_{i+1} \cdotldots a_{k_2}</tex>), k] то есть у строки <tex>a_1 \in I_jldots a_jw'</tex> и есть два различных вывода, что противоречит однозначности грамматики. Если же <tex>[B \rightarrow \delta \cdot, k] \in I_jk_1 = k_2</tex>, то <tex>\gamma eta_1 \Rightarrow a_{k+1} ne \dots a_jeta_2</tex> и , что приводит к аналогичному противоречию. Суммируя выше сказанное, отметим, что противоречие получается из того факта, что в некоторый момент времени (то есть для подстроки <tex>\delta \Rightarrow a_{k+1} a_1 \dots a_ja_i</tex>) мы получаем два различных дерева вывода. Поэтому, в дальнейшем, то есть при выводе суффикса <tex>a_{ki+1} \dots a_ja_n</tex> выводится двумя разными способами., каким образом мы его не получим, деревьев вывода будет как минимум два, поскольку они будут получаться заменой какого-то листа (терминального символа) на какое-то правило (поддерево из нетерминалов и терминалов),таким образом, получаем противоречие с однозначностью (по определению [[Существенно_неоднозначные_языки | неоднозачной грамматики]])
}}
{{Теорема
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины <tex>n</tex> составляет <tex>O(n^2)</tex>.
|proof=
Орагнизуем каждый список разбора <tex>I_jD_j</tex> таким образом, чтобы по любому символу <tex>x \in \Sigma \cup N</tex>, можно было за <tex>O(1)</tex> получить список тех и только тех ситуаций, содержащихся в <tex>I_jD_j</tex>, которые имеют вид <tex>[A \rightarrow \alpha \cdot x \beta, j]</tex>. Время построения <tex>D_0</tex> не зависит от входной строки. Рассмотрим <tex>D_j, \, j > 0</tex>.# При включении ситуаций по правилу <tex>(1)</tex> необходимо лишь просмотреть предыдущий список и для каждого его элемента выполнить константное число операций.# Рассмотрим правило <tex>(2)</tex>. Можно считать, что внутри цикла <tex>(*)</tex> рассматриваются те и только те ситуации, которые удовлетворяют условию (так как список таких ситуаций можно по нетерминалу получить за <tex>O(1)</tex> следующим образом: каждый раз, когда мы добавляем ситацаию вида <tex>[A \rightarrow \alpha \cdot B \beta, i]</tex> в <tex>D_j</tex>, мы просмотрим в заранее заготовленном массиве для <tex>D_j</tex>, есть ли в <tex>D_j</tex> ситуации вида <tex>[B \rightarrow \eta \cdot, j]</tex>. Если да, то добавим <tex>[A \rightarrow \alpha B \cdot \beta, i]</tex> в <tex>D_j</tex>.). Тогда каждая такая ситуация будет добавлена в список и, исходя из леммы 2, попытка добавления будет единственной. А так как по лемме 1 всего в списке <tex>D_j</tex> находится <tex>O(j)</tex> ситуаций, то суммарно за все итерации внешнего цикла while внутри цикла <tex>(*)</tex> будет рассмотрено <tex>O(j)</tex> ситуаций.# Так как грамматика фиксирована, то при применении правила <tex>(3)</tex> при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому для каждой рассмотренной ситуации будет выполнено <tex>O(1)</tex> операций.Таким образом, на построение списка <tex>D_j</tex> будет потрачено <tex>O(j)</tex> операций. Тогда время работы алгоритма составляет <tex>O(n^2)</tex>.}}