Алгоритм Эрли — различия между версиями
Gaporf (обсуждение | вклад) (Исправил многоточия) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 19: | Строка 19: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | Последовательность списков ситуаций <tex>D_0, D_1, | + | Последовательность списков ситуаций <tex>D_0, D_1, \ldots, D_{n-1} \ </tex> называется <b>списком разбора</b> для входной цепочки <tex>w</tex>. |
}} | }} | ||
Текущая версия на 19:27, 4 сентября 2022
Алгоритм Эрли позволяет определить, выводится ли данное слово контекстно-свободной грамматике .
в даннойВход: КС грамматика
Выход: , если выводится в ; — иначе.
Определение: |
Пусть контекстно-свободная грамматика и — входная цепочка из . Объект вида , где — правило из и — позиция в , называется ситуацией, относящейся к цепочке , где — вспомогательный символ, который не явлется терминалом или нетерминалом ( ). | —
Определение: |
Ситуации хранятся в множествах | , называемых списками ситуаций. Причем наличие ситуации в -м списке ситуаций равносильно тому, что .
Определение: |
Последовательность списков ситуаций | называется списком разбора для входной цепочки .
Алгоритм Эрли
Чтобы воспользоваться леммой, необходимо найти динамическим алгоритмом: он последовательно строит список разбора, причём при построении используются (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).
для . Алгоритм Эрли являетсяАлгоритм основывается на следующих трёх правилах:
- Если (где — -ый символ строки), то .
- Если и , то .
- Если и , то .
Псевдокод
Для простоты добавим новый стартовый вспомогательный нетерминал
и правило .function: // Инициализация for to = // Вычисление ситуаций for to while изменяется // Результат if return true else return false
function: if == return for if == =
function: for for =
function: for for =
Корректность алгоритма
Теорема: |
Приведенный алгоритм правильно строит все списки ситуаций.
То есть алгоритм поддерживает инвариант |
Доказательство: |
1. Включаем по правилу 2. Включаем по правилу 3. Включаем по правилу
1. 2. 3. |
Пример
Построим список разбора для строки
в грамматике со следующими правилами:
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
Так как
См. также
Источники информации
- Алексей Сорокин — Алгоритм Эрли
- Ахо А., Ульман Д.— Теория синтакcического анализа, перевода и компиляции. Том 1. Синтаксический анализ. Пер. с англ. — М.:«Мир», 1978. С. 358 — 364.