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

Алгоритм

Для начала модифицируем алгоритм Эрли.

Будем рассматривать грамматику без ε-правил и бесполезных символов.

[math]I_0[/math] = [math]\{[S' \rightarrow \cdot S, 0]\}[/math] # Правило (0) — инициализация
useful_loop(0)

for j = 1..n
    for [math][A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}[/math]
        [math]I_j[/math] ∪= [math][A \rightarrow \alpha a_{j} \cdot \beta, i][/math] # Правило (1)
    useful_loop(j)

function useful_loop(j):
    [math]I_j'' = I_j[/math]
    while [math]I_j'' \ne \varnothing[/math]
        [math]I_j' = I_j''[/math]
        [math]I_j'' = \varnothing[/math]
        for [math][B \rightarrow \eta \cdot , i] \in I_j'[/math] # (*)
            for [math][A \rightarrow \alpha \cdot B \beta, k] \in I_{i}[/math]
                [math]I_j''[/math] ∪= [math][A \rightarrow \alpha B \cdot \beta, k][/math] # Правило (2)
            
        for [math][B \rightarrow \alpha \cdot A \eta, k] \in I_j'[/math] # (**)
            for [math]\beta : (A \rightarrow \beta) \in P[/math]
                [math]I_j''[/math] ∪= [math][A \rightarrow \cdot \beta, j][/math] # Правило (3)
        [math]I_j[/math] ∪= [math]I_j''[/math]

В циклах, помеченных [math](*)[/math] и [math](**)[/math], просматривается не весь список [math]I_j[/math], а только те ситуации, которые были добавлены на предыдущей итерации цикла while. Данная модификация является корректной.

1. Рассмотрим цикл [math](*)[/math]. Если в текущей ситуации [math][B \rightarrow \eta \cdot, i][/math] этого цикла [math]i \ne j[/math], то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию [math][B \rightarrow \eta \cdot, i][/math] в цикле [math](*)[/math] рассматривать не нужно. Если же [math]i = j[/math], то [math]\eta \Rightarrow^* \varepsilon[/math], что возможно, только если [math]B = S', \eta = \varepsilon[/math]. Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как [math]S'[/math] не встречается в правых частях правил.
2. Теперь рассмотрим цикл [math](**)[/math]. Так как для каждой ситуации [math][B \rightarrow \alpha \cdot A \eta, k][/math] в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для [math][B \rightarrow \alpha \cdot A \eta, k][/math].

Таким образом, во все списки будут добавлены ситуации, которые были бы добавлены в ходе обычного алгоритма. Очевидно, что лишних ситуаций добавлено не будет, так как в циклах [math](*)[/math] и [math](**)[/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](1)[/math] (если последний символ [math]\alpha[/math] — терминал) и [math](2)[/math] (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что [math][A \rightarrow \alpha'B \cdot \beta, i][/math] включается в [math]I_j[/math], когда рассматриваются две ситуации [math][B \rightarrow \eta_1 \cdot, k_1][/math] и [math][B \rightarrow \eta_2 \cdot, k_2][/math] (они различны, так как в цикле [math](*)[/math] каждая ситуация из каждого списка рассматривается по одному разу). Тогда ситуация [math][A \rightarrow \alpha' \cdot B\beta, i][/math] должна оказаться одновременно в [math]I_{k_1}[/math] и в [math]I_{k_2}[/math]. Таким образом, получаем: [math]\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_1}[/math] и [math]\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_2}[/math]; [math]\eta_1 \Rightarrow^* a_{k_1+1} \ldots a_j[/math] и [math]\eta_2 \Rightarrow^* a_{k_2+1} \ldots a_j[/math]. Следовательно, [math]\alpha' \eta_1 \Rightarrow^* a_{i+1} \ldots a_j[/math] и [math]\alpha' \eta_2 \Rightarrow^* a_{i+1} \ldots a_j[/math]. Заметим, что [math]S \Rightarrow^* \gamma A \delta \Rightarrow^* a_1 \ldots a_i A \delta \Rightarrow a_1 \ldots a_i \alpha' B \beta \delta[/math]. Предположим, что [math]\beta \delta \Rightarrow^* w'[/math] (ведь в грамматике нет непорождающих нетерминалов). Тогда [math]S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_1 w'[/math] и аналогично [math]S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_2 w'[/math]. Таким образом, если [math]k_1 \ne k_2[/math], то подстрока [math]a_{i+1} \ldots a_j[/math] выводится двумя различными способами из [math]\alpha' \eta_1[/math] и [math]\alpha' \eta_2[/math] (поскольку в первом случае [math]\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_1}[/math], а во втором [math]\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_2}[/math]), то есть у строки [math]a_1 \ldots a_jw'[/math] есть два различных вывода, что противоречит однозначности грамматики. Если же [math]k_1 = k_2[/math], то [math]\eta_1 \ne \eta_2[/math], что приводит к аналогичному противоречию.

[math]\triangleleft[/math]

Теорема:

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

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

[math]\triangleright[/math]

По лемме 1 в [math]j[/math]-том списке в итоге будет содержаться [math]O(j)[/math] ситуаций, а по лемме 2 алгоритм попытается добавить в список принадлежащую ему ситуацию ровно один раз, т.е. соответствующие строчки кода выполнятся для [math]j[/math]-того списка суммарно [math]O(j)[/math] раз. Заметим, чтобы избежать «холостых» итераций во внутреннем цикле правила [math](2)[/math], необходимо организовать списки [math]I_k[/math] таким образом, чтобы по любому символу [math]x \in (\Sigma \cup N)[/math], можно было за [math]O(1)[/math] получить список тех и только тех ситуаций, содержащихся в [math]I_k[/math], которые имеют вид [math][A \rightarrow \alpha \cdot x \beta, j][/math] (например, этого можно добиться с помощью хеш-таблицы). Таким образом, поскольку списков ситуаций всего [math]n[/math], время работы алгоритма составляет [math]O(n^2)[/math].

[math]\triangleleft[/math]

Литература

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