Алгоритм Эрли
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Алгоритм Эрли позволяет определить, выводится ли данное слово контекстно-свободной грамматике .
в даннойВход: КС грамматика
Выход: , если выводится в ; — иначе.
Определение: |
Пусть контекстно-свободная грамматика и — входная цепочка из . Объект вида , где — правило из и — позиция в , называется ситуацией, относящейся к цепочке , где — вспомогательный символ, который не явлется терминалом или нетерминалом ( ). | —
Определение: |
Ситуации хранятся в множествах | , называемых списками ситуаций. Причем наличие ситуации в -м списке ситуаций равносильно тому, что .
Определение: |
Последовательность списков ситуаций | называется списком разбора для входной цепочки .
Алгоритм Эрли
Чтобы воспользоваться леммой, необходимо найти динамическим алгоритмом: он последовательно строит список разбора, причём при построении используются (то есть элементы списков с меньшими номерами и ситуации, содержащиеся в текущем списке на данный момент).
для . Алгоритм Эрли являетсяАлгоритм основывается на следующих трёх правилах:
- Если (где — -ый символ строки), то .
- Если и , то .
- Если и , то .
Псевдокод
Для простоты добавим новый стартовый вспомогательный нетерминал
и правило .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.