Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики — различия между версиями
AndrewD (обсуждение | вклад) |
AndrewD (обсуждение | вклад) |
||
Строка 28: | Строка 28: | ||
В циклах, помеченных <tex>(*)</tex> и <tex>(**)</tex> просматривается не весь список <tex>I_j</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>. Если в текущей ситуации <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>(**)</tex>. Так как для каждой ситуации <tex>[B \rightarrow \alpha \cdot A \eta, k]</tex> в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для <tex>[B \rightarrow \alpha \cdot A \eta, k]</tex>. |
+ | Таким образом, во все списки будут добавлены ситуации, которые были бы добавлены в ходе обычного алгоритма. Очевидно, что лишних ситуаций добавлено не будет, так как в циклах <tex>(*)</tex> и <tex>(**)</tex> просматривается подмножество полного списка. Значит два этих алгоритма эквивалентны. | ||
==Время работы для однозначной грамматики== | ==Время работы для однозначной грамматики== | ||
{{Лемма | {{Лемма |
Версия 09:11, 19 января 2012
Алгоритм
Для начала модифицируем алгоритм Эрли.
Удалим из входной грамматики и -правилабесполезные символы. В итоге получится грамматика .
= # Правило (0) — инициализация useful_loop(0) for i = 1..n for ∪= # Правило (1) useful_loop(j)
function useful_loop(j):while for # (*) for ∪= # Правило (2) for # (**) for ∪= # Правило (3) ∪=
В циклах, помеченных
и просматривается не весь список , а только те ситуации, которые еще не были просмотрены. Данная модификация является корректной.- Рассмотрим цикл . Если в текущей ситуации этого цикла , то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию в цикле рассматривать не нужно. Если же , то , что возможно, только если . Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как не встречается в правых частях правил.
- Теперь рассмотрим цикл . Так как для каждой ситуации в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для .
Таким образом, во все списки будут добавлены ситуации, которые были бы добавлены в ходе обычного алгоритма. Очевидно, что лишних ситуаций добавлено не будет, так как в циклах
и просматривается подмножество полного списка. Значит два этих алгоритма эквивалентны.Время работы для однозначной грамматики
Лемма (1): |
в списке находится ситуаций. |
Доказательство: |
Так как грамматика фиксирована, то | количество ситуаций вида не больше некоторой константы. Таким образом, поскольку в находятся ситуации, у которых , всего в будет ситуаций.
Лемма (2): |
Пусть — однозначная КС-грамматика без непорождающих нетерминалов и — цепочка из . Тогда алгоритм Эрли пытается включить в не более одного раза, если . |
Доказательство: |
Ситуацию можно включить в только по правилам (если последний символ — терминал) и (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что включается в , когда рассматриваются две различные ситуации и . Тогда ситуация должна оказаться одновременно в и в . Таким образом, получаем:
Следовательно
Заметим, что . Предположим, что . Тогда:
|
Теорема: |
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины составляет . |
Доказательство: |
Орагнизуем каждый список разбора таким образом, чтобы по любому символу , можно было за получить список тех и только тех ситуаций, содержащихся в , которые имеют вид .Время построения не зависит от входной строки.Рассмотрим .
|
Литература
- А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ.