Изменения

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

На вход подается Будем рассматривать грамматику [[КонтекстноУдаление eps-свободные правил из грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КСбез &epsilon;-грамматикаправил]] <tex>G = (N, \Sigma, P, S)</tex> и строка <tex>w = a_1 a_2 \ldots a_n</tex> из <tex>\Sigma^*</tex>. Результатом работы алгоритма является [[Алгоритм Эрли#ОпределенияУдаление бесполезных символов из грамматики|список разборабесполезных символов]] <tex>I_0, I_1, \ldots , I_n</tex> для строки <tex>w</tex>.

Для простоты добавим новый стартовый вспомогательный нетерминал '''function''' <tex>S'\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)

'''function''' <tex>\mathtt{rulesLoop(j)}</tex>: <tex>D_j'' = D_j</tex> '''while''' <tex>I_0D_j'' \ne \varnothing</tex> &cup; <tex>D_j' = D_j''</tex> <tex>D_j'' = \varnothing</tex> '''for''' <tex>[S' B \rightarrow \eta \cdot S, 0i]\in D_j'</tex> # Правило <font color=green>// Цикл (0*) — инициализация</font> useful_loop(0) for i = 1..n '''for ''' <tex>[A \rightarrow \alpha \cdot a_{j} B \beta, ik] \in I_D_{j-1i}</tex> <tex>I_jD_j''</tex> &<tex> \cup;</tex> = <tex>[A \rightarrow \alpha a_{j} B \cdot \beta, ik] </tex> <font color=green>// Второе правило </font> '''for''' <tex>[B \rightarrow \alpha \cdot A \eta, k]\in D_j'</tex> # Правило <font color=green>// Цикл (1**)</font> useful_loop '''for''' <tex>\beta : (A \rightarrow \beta) \in P</tex> <tex>D_j''</tex> <tex> \cup</tex> = <tex>[A \rightarrow \cdot \beta, j)]</tex> <font color=green>// Третье правило </font> <tex>D_j</tex> <tex> \cup</tex> = <tex>D_j''</tex>

function useful_loop== Доказательство эквивалентности == В циклах, помеченных <tex>(*)</tex> и <tex>(j**):</tex>, просматривается не весь список <tex>D_j</tex>, а только те ситуации, которые были добавлены на предыдущей итерации цикла <tex>\mathrm{while}</tex>. Данная модификация является корректной. do for # Рассмотрим цикл <tex>(*)</tex>. Если в текущей ситуации <tex>[B \rightarrow \eta \cdot , i] </tex> этого цикла <tex>i \in I_jne j</tex> for , то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию <tex>[A B \rightarrow \alpha eta \cdot B \beta, ki] \in I_{i}</tex> в цикле <tex>I_j(*)</tex> &cup;рассматривать не нужно. Если же <tex>i = j</tex>, то <tex>[A \rightarrow eta \Rightarrow^* \alpha varepsilon</tex>, что возможно, только если <tex>B = S', \cdot eta = \betavarepsilon</tex>. Тогда во внутреннем цикле не будет добавлено ни одной ситуации, k]так как <tex>S'</tex> не встречается в правых частях правил.# Правило Теперь рассмотрим цикл <tex>(2**) for </tex>. Так как для каждой ситуации <tex>[B \rightarrow \alpha \cdot A \eta, k] \in I_j</tex> for в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для <tex>[B \beta : (A rightarrow \rightarrow alpha \beta) cdot A \in Peta, k]</tex>. Таким образом, во все списки будут добавлены ситуации, которые были бы добавлены в ходе обычного алгоритма. Очевидно, что лишних ситуаций добавлено не будет, так как в циклах <tex>I_j(*)</tex> &cup;= и <tex>[A \rightarrow \cdot \beta, j](**)</tex> # Правило (3) while на данной итерации какое-то множество изменилосьпросматривается подмножество полного списка. Значит этот алгоритм эквивалентен оригинальному.

<tex>\forall\,j: 1 \le leqslant j \le leqslant n</tex> в списке <tex>I_jD_j</tex> находится <tex>O(j)</tex> ситуаций.

Так как грамматика фиксирована, то <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> ситуаций.

Пусть <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>.

Ситуацию <tex>[A \rightarrow \alpha \cdot \beta, i]</tex> можно включить в <tex>I_jD_j</tex> только по правилам <tex>(1)</tex> (если последний символ <tex>\alpha</tex> — терминал) и <tex>(2)</tex> (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что <tex>[A \rightarrow \alpha'B \cdot \beta, i]</tex> включается в <tex>I_jD_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>I_D_{k_1}</tex> и в <tex>I_D_{k_2}</tex>.Таким образом, получаем:# Пусть * <tex>\alpha' \Rightarrow^* a_{i+1} \ldots a_{k_1 }</tex> и <tex>\alpha' \Rightarrow^* a_{i+1} \ne ldots a_{k_2}</tex>. Тогда существуют такие ;* <tex>\gamma_1, eta_1 \delta_1, Rightarrow^* a_{k_1+1} \gamma_2ldots a_j</tex> и <tex>\delta_2eta_2 \Rightarrow^* a_{k_2+1} \ldots a_j</tex>.Следовательно, что <tex>S \alpha' \eta_1 \Rightarrow^* a_{i+1} \gamma_1 A \delta_1 \Rightarrow \gamma_1 ldots a_j</tex> и <tex>\alpha' B \beta eta_2 \Rightarrow^* a_{i+1} \delta_1ldots a_j</tex> и .<br/>Заметим, что <tex>S \Rightarrow^* \gamma_2 gamma A \delta_2 delta \Rightarrow ^* a_1 \gamma_2 ldots a_i A \delta \Rightarrow a_1 \ldots a_i \alpha' B \beta \delta_2delta</tex>. Но в первом выводе Предположим, что <tex>\gamma_1 beta \alpha' delta \Rightarrow^* a_1 \dots a_{k_1}w'</tex>, а во втором (ведь в грамматике нет непорождающих нетерминалов). Тогда <tex>S \Rightarrow^* a_1 \gamma_2 ldots a_i \alpha' \eta_1 w'</tex> и аналогично <tex>S \Rightarrow^* a_1 \dots a_{k_2}ldots 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_1 = k_2\alpha' \eta_2</tex>. Тогда (поскольку в первом случае <tex>\eta_1 alpha' \ne Rightarrow^* a_{i+1} \eta_2ldots a_{k_1}</tex>. Тогда, так как а во втором <tex>[B \rightarrow alpha' \eta_1 Rightarrow^* a_{i+1} \cdotldots a_{k_2}</tex>), k_1] то есть у строки <tex>a_1 \in I_jldots a_jw'</tex> и есть два различных вывода, что противоречит однозначности грамматики. Если же <tex>[B \rightarrow \eta_2 \cdot, k_1] \in I_j= k_2</tex>, то <tex>\eta_1 \Rightarrow^* a_{k_1 + 1} ne \dots a_jeta_2</tex> и , что приводит к аналогичному противоречию.  Суммируя выше сказанное, отметим, что противоречие получается из того факта, что в некоторый момент времени (то есть для подстроки <tex>\eta_2 \Rightarrow^* a_{k_1 + 1} a_1 \dots a_ja_i</tex>) мы получаем два различных дерева вывода. Поэтому, в дальнейшем, то есть при выводе суффикса <tex>a_{k_1 i+ 1} \dots a_ja_n</tex> выводится двумя разными способами., каким образом мы его не получим, деревьев вывода будет как минимум два, поскольку они будут получаться заменой какого-то листа (терминального символа) на какое-то правило (поддерево из нетерминалов и терминалов),таким образом, получаем противоречие с однозначностью (по определению [[Существенно_неоднозначные_языки | неоднозачной грамматики]])

Орагнизуем каждый список разбора <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>I_0D_0</tex> входная строка не учитывается, поэтому этот список можно построить за константное времязависит от входной строки.

Рассмотрим <tex>I_jD_j, \, j > 0</tex>.# При включении ситуации ситуаций по правилу <tex>(1)</tex> исследуется необходимо лишь просмотреть предыдущий список и для каждого его элемента выполнить константное число операций.# Рассмотрим правило <tex>a_j(2)</tex> и предыдущий список. Для каждой ситуации из Можно считать, что внутри цикла <tex>I_{j-1}(*)</tex> с символом рассматриваются те и только те ситуации, которые удовлетворяют условию (так как список таких ситуаций можно по нетерминалу получить за <tex>a_jO(1)</tex>следующим образом: каждый раз, расположенным справа от точки, в когда мы добавляем ситацаию вида <tex>I_j[A \rightarrow \alpha \cdot B \beta, i]</tex> включается некоторая ситуация. Так как список в <tex>I_{j-1}D_j</tex> можно найти за , мы просмотрим в заранее заготовленном массиве для <tex>O(1)D_j</tex> по символу , есть ли в <tex>a_jD_j</tex>, то на включение каждой ситуации в вида <tex>I_j[B \rightarrow \eta \cdot, j]</tex> будет потрачено . Если да, то добавим <tex>O(1)[A \rightarrow \alpha B \cdot \beta, i]</tex> операций.#Если применяется правило в <tex>(2)D_j</tex>.). Тогда каждая такая ситуация будет добавлена в список и, исходя из леммы 2, то попытка добавления будет единственной. А так как по лемме 1 всего в некотором списке <tex>I_kD_j</tex> для находится <tex>k \le O(j)</tex> надо просмотреть ситуаций, то суммарно за все ситуации, содержащие итерации внешнего цикла while внутри цикла <tex>"\cdot B"(*)</tex> для некоторого конкретного будет рассмотрено <tex>BO(j)</tex>. Для каждой такой ситуации в <tex>I_j</tex> включается другая ситуация, и это время относится не к рассматриваемой ситуации, а к включаемой. Кроме того, так как по второй лемме для каждой ситуации предпринимается только одна попытка включить ее в список, то не нужно тратить время на проверку того, что включаемая ситуация уже есть в спискеситуаций.#Так как грамматика фиксирована, то при применении правила <tex>(3)</tex> при рассмотрении любой ситуации количество включаемых ситуаций не превосходит некоторой константы, поэтому на рассматриваемую ситуацию для каждой рассмотренной ситуации будет потрачено выполнено <tex>O(1)</tex> операций.Таким образом, на каждую ситуацию в каждом списке тратится построение списка <tex>D_j</tex> будет потрачено <tex>O(1j)</tex> операций. Тогда, учитывая лемму 1, получаем, что время работы алгоритма составляет <tex>O(n^2)</tex>.

==ЛитератураСм. также ==* [[Алгоритм_Эрли | Алгоритм Эрли]]* [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ | Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ ]] == Источники информации==*А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.Издательство "Мир", Москва, 1978г., стр. 364-366 [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Алгоритмы разбора]]