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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство второго пункта леммы)
Строка 38: Строка 38:
 
|about=2
 
|about=2
 
|statement=
 
|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>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=
 
|proof=
 
Ситуацию <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> можно включить в <tex>I_j</tex> только по правилам <tex>(1)</tex> (если последний символ <tex>\alpha</tex> — терминал) и <tex>(2)</tex> (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>I_j</tex>, когда рассматриваются две различные ситуации <tex>[B \rightarrow \eta_1 \cdot, k_1]</tex> и <tex>[B \rightarrow \eta_2 \cdot, k_2]</tex>. Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>I_{k_1}</tex> и в <tex>I_{k_2}</tex>.
 
Ситуацию <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> можно включить в <tex>I_j</tex> только по правилам <tex>(1)</tex> (если последний символ <tex>\alpha</tex> — терминал) и <tex>(2)</tex> (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>I_j</tex>, когда рассматриваются две различные ситуации <tex>[B \rightarrow \eta_1 \cdot, k_1]</tex> и <tex>[B \rightarrow \eta_2 \cdot, k_2]</tex>. Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>I_{k_1}</tex> и в <tex>I_{k_2}</tex>.
 
# Пусть <tex>k_1 \ne k_2</tex>. Тогда  существуют такие <tex>\gamma_1, \delta_1, \gamma_2</tex> и <tex>\delta_2</tex>, что <tex>S \Rightarrow^* \gamma_1 A \delta_1 \Rightarrow \gamma_1 \alpha' B \beta \delta_1</tex> и <tex>S \Rightarrow^* \gamma_2 A \delta_2 \Rightarrow \gamma_2 \alpha' B \beta \delta_2</tex>. Но в первом выводе <tex>\gamma_1 \alpha' \Rightarrow^* a_1 \dots a_{k_1}</tex>, а во втором <tex>\gamma_2 \alpha' \Rightarrow^* a_1 \dots a_{k_2}</tex>. Тогда для цепочки <tex>a_1 \dots a_n</tex> существуют два разных дерева вывода, в которых <tex>a_{i+1} \dots a_j</tex> выводится из <tex>\alpha' B</tex> двумя разными способами.
 
# Пусть <tex>k_1 \ne k_2</tex>. Тогда  существуют такие <tex>\gamma_1, \delta_1, \gamma_2</tex> и <tex>\delta_2</tex>, что <tex>S \Rightarrow^* \gamma_1 A \delta_1 \Rightarrow \gamma_1 \alpha' B \beta \delta_1</tex> и <tex>S \Rightarrow^* \gamma_2 A \delta_2 \Rightarrow \gamma_2 \alpha' B \beta \delta_2</tex>. Но в первом выводе <tex>\gamma_1 \alpha' \Rightarrow^* a_1 \dots a_{k_1}</tex>, а во втором <tex>\gamma_2 \alpha' \Rightarrow^* a_1 \dots a_{k_2}</tex>. Тогда для цепочки <tex>a_1 \dots a_n</tex> существуют два разных дерева вывода, в которых <tex>a_{i+1} \dots a_j</tex> выводится из <tex>\alpha' B</tex> двумя разными способами.
# Пусть <tex>k_1 = k_2</tex>. Тогда <tex>\eta_1 \ne \eta_2</tex>. Тогда, так как <tex>[B \rightarrow \eta_1 \cdot, k_1] \in I_j</tex> и <tex>[B \rightarrow \eta_2 \cdot, k_1] \in I_j</tex>, то <tex>\eta_1 \Rightarrow^* a_{k_1 + 1} \dots a_j</tex> и <tex>\eta_2 \Rightarrow^* a_{k_1 + 1} \dots a_j</tex>, то есть <tex>a_{k_1 + 1} \dots a_j</tex> выводится двумя разными способами. Так как <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_{k_1}</tex>, то <tex>S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta \Rightarrow^* a_1 \ldots a_i \alpha' B \beta \delta \Rightarrow^* a_1 \ldots a_i a_{i+1} \ldots a_{k_1} B \beta \delta</tex> и <tex> a_1 \ldots a_{k_1} B \beta \delta \Rightarrow a_1 \ldots a_i a_{i+1} \ldots a_{k_1} \eta \beta \delta \Rightarrow^* a_1 \ldots a_i a_{i+1} \ldots a_{k_1} a_{k_1+1} \ldots a_j w'</tex>, где <tex>\eta = \eta_1</tex> или <tex>\eta = \eta_2</tex>, а <tex>w'</tex> {{---}} некоторая строка, такая что <tex>\beta \delta \Rightarrow^* w'</tex>. Таким образом, строка <tex>a_1 \ldots a_i a_{i+1} \ldots a_{k_1} a_{k_1+1} \ldots a_j w'</tex> выводится двумя способами.
+
# Пусть <tex>k_1 = k_2 = k</tex>. Тогда <tex>\eta_1 \ne \eta_2</tex>. Тогда, так как <tex>[B \rightarrow \eta_1 \cdot, k] \in I_j</tex> и <tex>[B \rightarrow \eta_2 \cdot, k] \in I_j</tex>, то <tex>\eta_1 \Rightarrow^* a_{k + 1} \dots a_j</tex> и <tex>\eta_2 \Rightarrow^* a_{k + 1} \dots a_j</tex>. Так как <tex>[A \rightarrow \alpha' \cdot B \beta, i] \in I_k</tex>, то <tex>S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta \Rightarrow^* a_1 \ldots a_i \alpha' B \beta \delta \Rightarrow^* a_1 \ldots a_k B \beta \delta \Rightarrow^* a_1 \ldots a_k \eta_1 \beta \delta</tex>. Аналогично, <tex>S \Rightarrow^* a_1 \ldots a_k \eta_2 \beta \delta</tex>. Теперь, если предположить, что <tex>\beta \delta \Rightarrow^* w'</tex>, то можно видеть, что <tex>S \Rightarrow^* a_1 \ldots a_k \eta_1 w'</tex> и <tex>S \Rightarrow^* a_1 \ldots a_k \eta_2 w'</tex>, а поскольку, как мы установили, из <tex>\eta_1</tex> и <tex>\eta_2</tex> выводится <tex>a_{k + 1} \dots a_j</tex>, у строки <tex>a_1 \ldots a_j w'</tex> в данной грамматике есть два различных вывода, что противоречит однозначности.
 
}}
 
}}
  

Версия 04:34, 19 января 2012

Алгоритм

Приведем Алгоритм Эрли.

На вход подается КС-грамматика [math]G = (N, \Sigma, P, S)[/math] и строка [math]w = a_1 a_2 \ldots a_n[/math] из [math]\Sigma^*[/math]. Результатом работы алгоритма является список разбора [math]I_0, I_1, \ldots , I_n[/math] для строки [math]w[/math].

Для простоты добавим новый стартовый вспомогательный нетерминал [math]S'[/math] и правило [math]S' \rightarrow S[/math].

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

for i = 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):
    do
        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)
    while на данной итерации какое-то множество изменилось

Время работы для однозначной грамматики

Лемма (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][A \rightarrow \alpha' \cdot B\beta, i][/math] должна оказаться одновременно в [math]I_{k_1}[/math] и в [math]I_{k_2}[/math].

  1. Пусть [math]k_1 \ne k_2[/math]. Тогда существуют такие [math]\gamma_1, \delta_1, \gamma_2[/math] и [math]\delta_2[/math], что [math]S \Rightarrow^* \gamma_1 A \delta_1 \Rightarrow \gamma_1 \alpha' B \beta \delta_1[/math] и [math]S \Rightarrow^* \gamma_2 A \delta_2 \Rightarrow \gamma_2 \alpha' B \beta \delta_2[/math]. Но в первом выводе [math]\gamma_1 \alpha' \Rightarrow^* a_1 \dots a_{k_1}[/math], а во втором [math]\gamma_2 \alpha' \Rightarrow^* a_1 \dots a_{k_2}[/math]. Тогда для цепочки [math]a_1 \dots a_n[/math] существуют два разных дерева вывода, в которых [math]a_{i+1} \dots a_j[/math] выводится из [math]\alpha' B[/math] двумя разными способами.
  2. Пусть [math]k_1 = k_2 = k[/math]. Тогда [math]\eta_1 \ne \eta_2[/math]. Тогда, так как [math][B \rightarrow \eta_1 \cdot, k] \in I_j[/math] и [math][B \rightarrow \eta_2 \cdot, k] \in I_j[/math], то [math]\eta_1 \Rightarrow^* a_{k + 1} \dots a_j[/math] и [math]\eta_2 \Rightarrow^* a_{k + 1} \dots a_j[/math]. Так как [math][A \rightarrow \alpha' \cdot B \beta, i] \in I_k[/math], то [math]S \Rightarrow^* \gamma A \delta \Rightarrow \gamma \alpha' B \beta \delta \Rightarrow^* a_1 \ldots a_i \alpha' B \beta \delta \Rightarrow^* a_1 \ldots a_k B \beta \delta \Rightarrow^* a_1 \ldots a_k \eta_1 \beta \delta[/math]. Аналогично, [math]S \Rightarrow^* a_1 \ldots a_k \eta_2 \beta \delta[/math]. Теперь, если предположить, что [math]\beta \delta \Rightarrow^* w'[/math], то можно видеть, что [math]S \Rightarrow^* a_1 \ldots a_k \eta_1 w'[/math] и [math]S \Rightarrow^* a_1 \ldots a_k \eta_2 w'[/math], а поскольку, как мы установили, из [math]\eta_1[/math] и [math]\eta_2[/math] выводится [math]a_{k + 1} \dots a_j[/math], у строки [math]a_1 \ldots a_j w'[/math] в данной грамматике есть два различных вывода, что противоречит однозначности.
[math]\triangleleft[/math]


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

Орагнизуем каждый список разбора [math]I_j[/math] таким образом, чтобы по любому символу [math]x \in \Sigma \cup N[/math], можно было за [math]O(1)[/math] получить список тех и только тех ситуаций, содержащихся в [math]I_j[/math], которые имеют вид [math][A \rightarrow \alpha \cdot x \beta, j][/math].

Время построения [math]I_0[/math] не зависит от входной строки.

Рассмотрим [math]I_j, \, j \gt 0[/math].

  1. При включении ситуации по правилу [math](1)[/math] исследуется [math]a_j[/math] и предыдущий список. Для каждой ситуации из [math]I_{j-1}[/math] с символом [math]a_j[/math], расположенным справа от точки, в [math]I_j[/math] включается некоторая ситуация. Так как список в [math]I_{j-1}[/math] можно найти за [math]O(1)[/math] по символу [math]a_j[/math], то на включение каждой ситуации в [math]I_j[/math] будет потрачено [math]O(1)[/math] операций.
  2. Если применяется правило [math](2)[/math], то в некотором списке [math]I_k[/math] для [math]k \le j[/math] надо просмотреть все ситуации, содержащие [math]"\cdot B"[/math] для некоторого конкретного [math]B[/math]. Для каждой такой ситуации в [math]I_j[/math] включается другая ситуация, и это время относится не к рассматриваемой ситуации, а к включаемой. Кроме того, так как по второй лемме для каждой ситуации предпринимается только одна попытка включить ее в список, то не нужно тратить время на проверку того, что включаемая ситуация уже есть в списке.
  3. Так как грамматика фиксирована, то при применении правила [math](3)[/math] при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому на рассматриваемую ситуацию будет потрачено [math]O(1)[/math] операций.
Таким образом, на каждую ситуацию в каждом списке тратится [math]O(1)[/math] операций. Тогда, учитывая лемму 1, получаем, что время работы алгоритма составляет [math]O(n^2)[/math].
[math]\triangleleft[/math]

Литература

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