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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
 
(не показано 26 промежуточных версий 5 участников)
Строка 1: Строка 1:
 
==Алгоритм==
 
==Алгоритм==
Для начала модифицируем [[Алгоритм Эрли|алгоритм Эрли]].
+
Для начала модифицируем [[Алгоритм Эрли|алгоритм Эрли]]. Главным отличием от базовой версии алгоритма является функция <tex>\mathtt{rulesLoop}</tex>, внутри которой мы, как и в базовой версии, просматриваем второе и третье правило, однако, в отличие от базовой версии, где при каждом изменении <tex>D_j</tex> мы просматривали весь список <tex>D_j</tex> и применяли к нему второе и третье правило, в модифицированной версии мы применяем правила внутри <tex>\mathtt{rulesLoop}</tex>, просматривая только те ситуации, которые были добавлены на предыдущей итерации цикла <tex>\mathtt{while}</tex>.
  
Удалим из входной грамматики [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>-правила]] и [[Удаление бесполезных символов из грамматики|бесполезные символы]]. В итоге получится грамматика <tex>G = (N, \Sigma, P, S)</tex>.
+
Будем рассматривать грамматику [[Удаление eps-правил из грамматики|без &epsilon;-правил]] и [[Удаление бесполезных символов из грамматики|бесполезных символов]].
  
  <tex>I_0</tex> = <tex>\{[S \rightarrow \cdot \alpha, 0] \, | \, S \rightarrow \alpha \in P\}</tex> # Правило (0) — инициализация
+
  '''function''' <tex>\mathtt{earleyMod}(G, w)</tex>:
useful_loop(0)
+
    <font color=green>// Инициализация </font>
+
    <tex> D_{0} = \lbrace [S' \rightarrow \cdot S, 0] \rbrace </tex>
for i = 1..n
+
    rulesLoop(0)
    for <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in I_{j-1}</tex>
+
    '''for''' j = 1 .. n
        <tex>I_j</tex> &cup;= <tex>[A \rightarrow \alpha a_{j} \cdot \beta, i]</tex> # Правило (1)
+
        '''for''' <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in D_{j-1}</tex>
    useful_loop(j)
+
            <tex>D_j</tex> <tex> \cup</tex> = <tex>[A \rightarrow \alpha a_{j} \cdot \beta, i]</tex> <font color=green>// Первое правило </font>
 +
        rulesLoop(j)  
  
  function useful_loop(j):
+
  '''function''' <tex>\mathtt{rulesLoop(j)}</tex>:
     <tex>I_j'' = I_j</tex>
+
     <tex>D_j'' = D_j</tex>
     while <tex>I_j'' \ne \varnothing</tex>
+
     '''while''' <tex>D_j'' \ne \varnothing</tex>
         <tex>I_j' = I_j''</tex>
+
         <tex>D_j' = D_j''</tex>
         <tex>I_j'' = \varnothing</tex>
+
         <tex>D_j'' = \varnothing</tex>
         for <tex>[B \rightarrow \eta \cdot , i] \in I_j'</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 I_{i}</tex>
+
             '''for''' <tex>[A \rightarrow \alpha \cdot B \beta, k] \in D_{i}</tex>
                 <tex>I_j''</tex> &cup;= <tex>[A \rightarrow \alpha B \cdot \beta, k]</tex> # Правило (2)
+
                 <tex>D_j''</tex> <tex> \cup</tex> = <tex>[A \rightarrow \alpha B \cdot \beta, k] </tex> <font color=green>// Второе правило </font>
 
              
 
              
         for <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j'</tex> # (**)
+
         '''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>
+
             '''for''' <tex>\beta : (A \rightarrow \beta) \in P</tex>
                 <tex>I_j''</tex> &cup;= <tex>[A \rightarrow \cdot \beta, j]</tex> # Правило (3)
+
                 <tex>D_j''</tex> <tex> \cup</tex> = <tex>[A \rightarrow \cdot \beta, j]</tex>     <font color=green>// Третье правило </font>
        <tex>I_j</tex> &cup;= <tex>I_j''</tex>
+
        <tex>D_j</tex> <tex> \cup</tex> = <tex>D_j''</tex>
 +
 
 +
== Доказательство эквивалентности ==
 +
 
 +
В циклах, помеченных <tex>(*)</tex> и <tex>(**)</tex>, просматривается не весь список <tex>D_j</tex>, а только те ситуации, которые были добавлены на предыдущей итерации цикла <tex>\mathrm{while}</tex>. Данная модификация является корректной.
 +
# Рассмотрим цикл <tex>(*)</tex>. Если в текущей ситуации <tex>[B \rightarrow \eta \cdot, i]</tex> этого цикла <tex>i \ne j</tex>, то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию <tex>[B \rightarrow \eta \cdot, i]</tex> в цикле <tex>(*)</tex> рассматривать не нужно. Если же <tex>i = j</tex>, то <tex>\eta \Rightarrow^* \varepsilon</tex>, что возможно, только если <tex>B = S', \eta = \varepsilon</tex>. Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как <tex>S'</tex> не встречается в правых частях правил.
 +
# Теперь рассмотрим цикл <tex>(**)</tex>. Так как для каждой ситуации <tex>[B \rightarrow \alpha \cdot A \eta, k]</tex> в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для <tex>[B \rightarrow \alpha \cdot A \eta, k]</tex>.
 +
Таким образом, во все списки будут добавлены ситуации, которые были бы добавлены в ходе обычного алгоритма. Очевидно, что лишних ситуаций добавлено не будет, так как в циклах <tex>(*)</tex> и <tex>(**)</tex> просматривается подмножество полного списка. Значит этот алгоритм эквивалентен оригинальному.
  
В циклах, помеченных <tex>(*)</tex> и <tex>(**)</tex> просматривается не весь список <tex>I_j</tex>, а только те ситуации, которые еще не были просмотрены. Данная модификация является корректной.
 
# Рассмотрим цикл <tex>(*)</tex>. Если в текущей ситуации <tex>[B \rightarrow \eta \cdot, i]</tex> этого цикла <tex>i \ne j</tex>, то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию <tex>[B \rightarrow \eta \cdot, i]</tex> в цикле <tex>(*)</tex> рассматривать не нужно. Если же <tex>i = j</tex>, то <tex>\eta \Rightarrow^* \varepsilon</tex>, что возможно, только если <tex>B = S \, , \eta = \varepsilon</tex>. Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как <tex>S</tex> не встречается в правых частях правил.
 
# Теперь рассмотрим цикл <tex>(**)</tex>.
 
 
==Время работы для однозначной грамматики==
 
==Время работы для однозначной грамматики==
 
{{Лемма
 
{{Лемма
 
|about=1
 
|about=1
 
|statement=
 
|statement=
<tex>\forall\,j: 1 \le j \le n</tex> в списке <tex>I_j</tex> находится <tex>O(j)</tex> ситуаций.
+
<tex>\forall\,j: 1 \leqslant j \leqslant n</tex> в списке <tex>D_j</tex> находится <tex>O(j)</tex> ситуаций.
 
|proof=
 
|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>\forall i</tex> количество ситуаций вида <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> не больше некоторой константы. Таким образом, поскольку в <tex>D_j</tex> находятся ситуации, у которых <tex>0 \leqslant i \leqslant j</tex>, всего в <tex>D_j</tex> будет <tex>O(j)</tex> ситуаций.
 
}}
 
}}
  
Строка 42: Строка 47:
 
|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>\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>D_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>D_j</tex> только по правилам <tex>(1)</tex> (если последний символ <tex>\alpha</tex> — терминал) и <tex>(2)</tex> (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>D_j</tex>, когда рассматриваются две ситуации <tex>[B \rightarrow \eta_1 \cdot, k_1]</tex> и <tex>[B \rightarrow \eta_2 \cdot, k_2]</tex> (они различны, так как в цикле <tex>(*)</tex> каждая ситуация из каждого списка рассматривается по одному разу). Тогда ситуация <tex>[A \rightarrow \alpha' \cdot B\beta, i]</tex> должна оказаться одновременно в <tex>D_{k_1}</tex> и в <tex>D_{k_2}</tex>. Таким образом, получаем:
* <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_1}</tex> и <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_2}</tex>
+
* <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_1}</tex> и <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_2}</tex>;
* <tex>\eta_1 \Rightarrow^* a_{k_1+1} \ldots a_j</tex> и <tex>\eta_2 \Rightarrow^* a_{k_2+1} \ldots a_j</tex>
+
* <tex>\eta_1 \Rightarrow^* a_{k_1+1} \ldots a_j</tex> и <tex>\eta_2 \Rightarrow^* a_{k_2+1} \ldots a_j</tex>.
Следовательно
+
Следовательно, <tex>\alpha' \eta_1 \Rightarrow^* a_{i+1} \ldots a_j</tex> и <tex>\alpha' \eta_2 \Rightarrow^* a_{i+1} \ldots a_j</tex>.<br/>
* <tex>\alpha' \eta_1 \Rightarrow^* a_{i+1} \ldots a_j</tex> и <tex>\alpha' \eta_2 \Rightarrow^* a_{i+1} \ldots a_j</tex>
+
Заметим, что <tex>S \Rightarrow^* \gamma A \delta \Rightarrow^* a_1 \ldots a_i A \delta \Rightarrow a_1 \ldots a_i \alpha' B \beta \delta</tex>. Предположим, что <tex>\beta \delta \Rightarrow^* w'</tex> (ведь в грамматике нет непорождающих нетерминалов). Тогда <tex>S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_1 w'</tex> и аналогично <tex>S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_2 w'</tex>.<br/>
Заметим, что <tex>S \Rightarrow^* \gamma A \delta \Rightarrow^* a_1 \ldots a_i A \delta \Rightarrow a_1 \ldots a_i \alpha' B \beta \delta</tex>. Предположим, что <tex>\beta \delta \Rightarrow^* w'</tex>. Тогда:
+
Таким образом, если <tex>k_1 \ne k_2</tex>, то подстрока <tex>a_{i+1} \ldots a_j</tex> выводится двумя различными способами из <tex>\alpha' \eta_1</tex> и <tex>\alpha' \eta_2</tex> (поскольку в первом случае <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_1}</tex>, а во втором <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_2}</tex>), то есть у строки <tex>a_1 \ldots a_jw'</tex> есть два различных вывода, что противоречит однозначности грамматики. Если же <tex>k_1 = k_2</tex>, то <tex>\eta_1 \ne \eta_2</tex>, что приводит к аналогичному противоречию.  
* <tex>S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_1 w'</tex> и <tex>S \Rightarrow^* a_1 \ldots a_i \alpha' \eta_2 w'</tex>
+
 
Таким образом, если <tex>k_1 \ne k_2</tex>, то подстрока <tex>a_{i+1} \ldots a_j</tex> выводится двумя различными способами из <tex>\alpha' \eta_1</tex> и <tex>\alpha' \eta_2</tex>, то есть у строки <tex>a_1 \ldots a_jw'</tex> есть два различных вывода, что противоречит однозначности грамматики. Если же <tex>k_1 = k_2</tex>, то <tex>\eta_1 \ne \eta_2</tex>, что приводит к аналогичному противоречию.
+
Суммируя выше сказанное, отметим, что противоречие получается из того факта, что в некоторый момент времени (то есть для подстроки <tex>a_1 \dots a_i</tex>) мы получаем два различных дерева вывода. Поэтому, в дальнейшем, при выводе суффикса <tex>a_{i+1} \dots a_n</tex>, каким образом мы его не получим, деревьев вывода будет как минимум два, поскольку они будут получаться заменой какого-то листа (терминального символа) на какое-то правило (поддерево из нетерминалов и терминалов),таким образом, получаем противоречие с однозначностью (по определению [[Существенно_неоднозначные_языки | неоднозачной грамматики]])
 
}}
 
}}
  
Строка 59: Строка 64:
 
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины <tex>n</tex> составляет <tex>O(n^2)</tex>.
 
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины <tex>n</tex> составляет <tex>O(n^2)</tex>.
 
|proof=
 
|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>D_j</tex> таким образом, чтобы по любому символу <tex>x \in \Sigma \cup N</tex>, можно было за <tex>O(1)</tex> получить список тех и только тех ситуаций, содержащихся в <tex>D_j</tex>, которые имеют вид <tex>[A \rightarrow \alpha \cdot x \beta, j]</tex>.
  
Время построения <tex>I_0</tex> не зависит от входной строки.
+
Время построения <tex>D_0</tex> не зависит от входной строки.
  
Рассмотрим <tex>I_j, \, j > 0</tex>.
+
Рассмотрим <tex>D_j, \, j > 0</tex>.
 
# При включении ситуаций по правилу <tex>(1)</tex> необходимо лишь просмотреть предыдущий список и для каждого его элемента выполнить константное число операций.
 
# При включении ситуаций по правилу <tex>(1)</tex> необходимо лишь просмотреть предыдущий список и для каждого его элемента выполнить константное число операций.
# Если применяется правило <tex>(2)</tex>, то в некотором списке <tex>I_k</tex> для <tex>k \le j</tex> надо просмотреть все ситуации, содержащие <tex>"\cdot B"</tex> для некоторого конкретного <tex>B</tex>. Для каждой такой ситуации в <tex>I_j</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>(3)</tex> при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому для каждой рассмотренной ситуации будет выполнено <tex>O(1)</tex> операций.
Таким образом, на каждую ситуацию в каждом списке тратится <tex>O(1)</tex> операций. Тогда, учитывая лемму 1, получаем, что время работы алгоритма составляет <tex>O(n^2)</tex>.
+
Таким образом, на построение списка <tex>D_j</tex> будет потрачено <tex>O(j)</tex> операций. Тогда время работы алгоритма составляет <tex>O(n^2)</tex>.
 
}}
 
}}
  
==Литература==
+
== См. также ==
*А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.
+
* [[Алгоритм_Эрли | Алгоритм Эрли]]
 +
* [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ | Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ ]]
 +
 
 +
== Источники информации==
 +
*А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ. Издательство "Мир", Москва, 1978г., стр. 364-366
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Алгоритмы разбора]]

Текущая версия на 16:48, 5 января 2017

Алгоритм[править]

Для начала модифицируем алгоритм Эрли. Главным отличием от базовой версии алгоритма является функция [math]\mathtt{rulesLoop}[/math], внутри которой мы, как и в базовой версии, просматриваем второе и третье правило, однако, в отличие от базовой версии, где при каждом изменении [math]D_j[/math] мы просматривали весь список [math]D_j[/math] и применяли к нему второе и третье правило, в модифицированной версии мы применяем правила внутри [math]\mathtt{rulesLoop}[/math], просматривая только те ситуации, которые были добавлены на предыдущей итерации цикла [math]\mathtt{while}[/math].

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

function [math]\mathtt{earleyMod}(G, w)[/math]:
   // Инициализация 
   [math] D_{0} = \lbrace [S' \rightarrow \cdot S, 0] \rbrace [/math]
   rulesLoop(0)
   for j = 1 .. n
       for [math][A \rightarrow \alpha \cdot a_{j} \beta, i] \in D_{j-1}[/math]
           [math]D_j[/math] [math] \cup[/math] = [math][A \rightarrow \alpha a_{j} \cdot \beta, i][/math]  // Первое правило 
       rulesLoop(j) 
function [math]\mathtt{rulesLoop(j)}[/math]:
    [math]D_j'' = D_j[/math]
    while [math]D_j'' \ne \varnothing[/math]
        [math]D_j' = D_j''[/math]
        [math]D_j'' = \varnothing[/math]
        for [math][B \rightarrow \eta \cdot , i] \in D_j'[/math]             // Цикл (*) 
            for [math][A \rightarrow \alpha \cdot B \beta, k] \in D_{i}[/math]
                [math]D_j''[/math] [math] \cup[/math] = [math][A \rightarrow \alpha B \cdot \beta, k]  [/math] // Второе правило 
            
        for [math][B \rightarrow \alpha \cdot A \eta, k] \in D_j'[/math]        // Цикл (**) 
            for [math]\beta : (A \rightarrow \beta) \in P[/math]
                [math]D_j''[/math] [math] \cup[/math] = [math][A \rightarrow \cdot \beta, j][/math]     // Третье правило 
        [math]D_j[/math] [math] \cup[/math] = [math]D_j''[/math]

Доказательство эквивалентности[править]

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

  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 \leqslant j \leqslant n[/math] в списке [math]D_j[/math] находится [math]O(j)[/math] ситуаций.
Доказательство:
[math]\triangleright[/math]
Так как грамматика фиксирована, то [math]\forall i[/math] количество ситуаций вида [math][A \rightarrow \alpha \cdot \beta, i][/math] не больше некоторой константы. Таким образом, поскольку в [math]D_j[/math] находятся ситуации, у которых [math]0 \leqslant i \leqslant j[/math], всего в [math]D_j[/math] будет [math]O(j)[/math] ситуаций.
[math]\triangleleft[/math]


Лемма (2):
Пусть [math]\Gamma = (N, \Sigma, P, S)[/math] — однозначная КС-грамматика без непорождающих нетерминалов и [math]a_1 \dots a_n[/math] — цепочка из [math]\Sigma^*[/math]. Тогда алгоритм Эрли пытается включить [math][A \rightarrow \alpha \cdot \beta, i][/math] в [math]D_j[/math] не более одного раза, если [math]\alpha \ne \varepsilon[/math].
Доказательство:
[math]\triangleright[/math]

Ситуацию [math][A \rightarrow \alpha \cdot \beta, i][/math] можно включить в [math]D_j[/math] только по правилам [math](1)[/math] (если последний символ [math]\alpha[/math] — терминал) и [math](2)[/math] (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что [math][A \rightarrow \alpha'B \cdot \beta, i][/math] включается в [math]D_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]D_{k_1}[/math] и в [math]D_{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]a_1 \dots a_i[/math]) мы получаем два различных дерева вывода. Поэтому, в дальнейшем, при выводе суффикса [math]a_{i+1} \dots a_n[/math], каким образом мы его не получим, деревьев вывода будет как минимум два, поскольку они будут получаться заменой какого-то листа (терминального символа) на какое-то правило (поддерево из нетерминалов и терминалов),таким образом, получаем противоречие с однозначностью (по определению неоднозачной грамматики)
[math]\triangleleft[/math]


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

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

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

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

  1. При включении ситуаций по правилу [math](1)[/math] необходимо лишь просмотреть предыдущий список и для каждого его элемента выполнить константное число операций.
  2. Рассмотрим правило [math](2)[/math]. Можно считать, что внутри цикла [math](*)[/math] рассматриваются те и только те ситуации, которые удовлетворяют условию (так как список таких ситуаций можно по нетерминалу получить за [math]O(1)[/math] следующим образом: каждый раз, когда мы добавляем ситацаию вида [math][A \rightarrow \alpha \cdot B \beta, i][/math] в [math]D_j[/math], мы просмотрим в заранее заготовленном массиве для [math]D_j[/math], есть ли в [math]D_j[/math] ситуации вида [math][B \rightarrow \eta \cdot, j][/math]. Если да, то добавим [math][A \rightarrow \alpha B \cdot \beta, i][/math] в [math]D_j[/math].). Тогда каждая такая ситуация будет добавлена в список и, исходя из леммы 2, попытка добавления будет единственной. А так как по лемме 1 всего в списке [math]D_j[/math] находится [math]O(j)[/math] ситуаций, то суммарно за все итерации внешнего цикла while внутри цикла [math](*)[/math] будет рассмотрено [math]O(j)[/math] ситуаций.
  3. Так как грамматика фиксирована, то при применении правила [math](3)[/math] при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому для каждой рассмотренной ситуации будет выполнено [math]O(1)[/math] операций.
Таким образом, на построение списка [math]D_j[/math] будет потрачено [math]O(j)[/math] операций. Тогда время работы алгоритма составляет [math]O(n^2)[/math].
[math]\triangleleft[/math]

См. также[править]

Источники информации[править]

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