Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики — различия между версиями
Zernov (обсуждение | вклад) (→Время работы для однозначной грамматики) |
м (rollbackEdits.php mass rollback) |
||
(не показано 6 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
==Алгоритм== | ==Алгоритм== | ||
− | Для начала модифицируем [[Алгоритм Эрли|алгоритм Эрли]]. | + | Для начала модифицируем [[Алгоритм Эрли|алгоритм Эрли]]. Главным отличием от базовой версии алгоритма является функция <tex>\mathtt{rulesLoop}</tex>, внутри которой мы, как и в базовой версии, просматриваем второе и третье правило, однако, в отличие от базовой версии, где при каждом изменении <tex>D_j</tex> мы просматривали весь список <tex>D_j</tex> и применяли к нему второе и третье правило, в модифицированной версии мы применяем правила внутри <tex>\mathtt{rulesLoop}</tex>, просматривая только те ситуации, которые были добавлены на предыдущей итерации цикла <tex>\mathtt{while}</tex>. |
Будем рассматривать грамматику [[Удаление eps-правил из грамматики|без ε-правил]] и [[Удаление бесполезных символов из грамматики|бесполезных символов]]. | Будем рассматривать грамматику [[Удаление eps-правил из грамматики|без ε-правил]] и [[Удаление бесполезных символов из грамматики|бесполезных символов]]. | ||
− | '''function''' <tex>\mathtt{ | + | '''function''' <tex>\mathtt{earleyMod}(G, w)</tex>: |
<font color=green>// Инициализация </font> | <font color=green>// Инициализация </font> | ||
<tex> D_{0} = \lbrace [S' \rightarrow \cdot S, 0] \rbrace </tex> | <tex> D_{0} = \lbrace [S' \rightarrow \cdot S, 0] \rbrace </tex> | ||
− | + | rulesLoop(0) | |
'''for''' j = 1 .. n | '''for''' j = 1 .. n | ||
'''for''' <tex>[A \rightarrow \alpha \cdot a_{j} \beta, i] \in D_{j-1}</tex> | '''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> | <tex>D_j</tex> <tex> \cup</tex> = <tex>[A \rightarrow \alpha a_{j} \cdot \beta, i]</tex> <font color=green>// Первое правило </font> | ||
− | + | rulesLoop(j) | |
− | '''function''' | + | '''function''' <tex>\mathtt{rulesLoop(j)}</tex>: |
<tex>D_j'' = D_j</tex> | <tex>D_j'' = D_j</tex> | ||
'''while''' <tex>D_j'' \ne \varnothing</tex> | '''while''' <tex>D_j'' \ne \varnothing</tex> | ||
Строка 29: | Строка 29: | ||
== Доказательство эквивалентности == | == Доказательство эквивалентности == | ||
− | В циклах, помеченных <tex>(*)</tex> и <tex>(**)</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 \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>[B \rightarrow \alpha \cdot A \eta, k]</tex> в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для <tex>[B \rightarrow \alpha \cdot A \eta, k]</tex>. | ||
Строка 38: | Строка 38: | ||
|about=1 | |about=1 | ||
|statement= | |statement= | ||
− | <tex>\forall\,j: 1 \ | + | <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>D_j</tex> находятся ситуации, у которых <tex>0 \ | + | Так как грамматика фиксирована, то <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> ситуаций. |
}} | }} | ||
Строка 80: | Строка 80: | ||
== Источники информации== | == Источники информации== | ||
− | *А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ. | + | *А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ. Издательство "Мир", Москва, 1978г., стр. 364-366 |
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Контекстно-свободные грамматики]] | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: Алгоритмы разбора]] |
Текущая версия на 19:12, 4 сентября 2022
Содержание
Алгоритм
Для начала модифицируем алгоритм Эрли. Главным отличием от базовой версии алгоритма является функция , внутри которой мы, как и в базовой версии, просматриваем второе и третье правило, однако, в отличие от базовой версии, где при каждом изменении мы просматривали весь список и применяли к нему второе и третье правило, в модифицированной версии мы применяем правила внутри , просматривая только те ситуации, которые были добавлены на предыдущей итерации цикла .
Будем рассматривать грамматику без ε-правил и бесполезных символов.
function: // Инициализация rulesLoop(0) for j = 1 .. n for = // Первое правило rulesLoop(j)
function: while for // Цикл (*) for = // Второе правило for // Цикл (**) for = // Третье правило =
Доказательство эквивалентности
В циклах, помеченных
и , просматривается не весь список , а только те ситуации, которые были добавлены на предыдущей итерации цикла . Данная модификация является корректной.- Рассмотрим цикл . Если в текущей ситуации этого цикла , то во внутреннем цикле просматривается список с меньшим индексом, в который новые ситуации больше не добавляются. Поэтому после первого просмотра этого списка будут добавлены все ситуации, удовлетворяющие условию, и больше ситуацию в цикле рассматривать не нужно. Если же , то , что возможно, только если . Тогда во внутреннем цикле не будет добавлено ни одной ситуации, так как не встречается в правых частях правил.
- Теперь рассмотрим цикл . Так как для каждой ситуации в список добавляется новая ситуация, соответствующая правилу из грамматики, а грамматика фиксирована, то после первого просмотра будут добавлены все возможные ситуации для .
Таким образом, во все списки будут добавлены ситуации, которые были бы добавлены в ходе обычного алгоритма. Очевидно, что лишних ситуаций добавлено не будет, так как в циклах
и просматривается подмножество полного списка. Значит этот алгоритм эквивалентен оригинальному.Время работы для однозначной грамматики
Лемма (1): |
в списке находится ситуаций. |
Доказательство: |
Так как грамматика фиксирована, то | количество ситуаций вида не больше некоторой константы. Таким образом, поскольку в находятся ситуации, у которых , всего в будет ситуаций.
Лемма (2): |
Пусть — однозначная КС-грамматика без непорождающих нетерминалов и — цепочка из . Тогда алгоритм Эрли пытается включить в не более одного раза, если . |
Доказательство: |
Ситуацию можно включить в только по правилам (если последний символ — терминал) и (если нетерминал). В первом случае результат очевиден. Во втором случае допустим, что включается в , когда рассматриваются две ситуации и (они различны, так как в цикле каждая ситуация из каждого списка рассматривается по одному разу). Тогда ситуация должна оказаться одновременно в и в . Таким образом, получаем:
Следовательно, |
Теорема: |
Если входная грамматика однозначна, то время выполнения алгоритма Эрли для слова длины составляет . |
Доказательство: |
Орагнизуем каждый список разбора таким образом, чтобы по любому символу , можно было за получить список тех и только тех ситуаций, содержащихся в , которые имеют вид .Время построения не зависит от входной строки.Рассмотрим .
|
См. также
Источники информации
- А. Ахо, Дж. Ульман. Теория синтакcического анализа, перевода и компиляции. Том 1. Синтакcический анализ. Издательство "Мир", Москва, 1978г., стр. 364-366