Алгоритм Эрли

Алгоритм работает следующим образом. Пусть – КС-грамматика и - входная цепочка. Объект вида назовем ситуацией к цепочке , если - правило из и . Точка «» между и является метасимволом, для которого имеет место условие . Число может быть любым целым числом от нуля (в этом случае точка – первый символ) до (в этом случае она последний символ. Примечание. Если правило имеет вид , то ситуация будет такой: ).

Для каждого построим такой список ситуаций , что тогда и только тогда, когда для некоторых и существуют выводы и . Таким образом, между второй компонентой ситуации и номером списка, где она появляется, заключена часть входной цепочки, выводимая из . Другие условия, налагаемые на ситуацию, просто гарантируют возможность применения правила в выводе некоторой входной цепочки, совпадающей с до позиции .

Последовательность списков будем называть списком разбора для входной цепочки . Заметим, что принадлежит тогда и только тогда, когда в есть ситуация вида .

Дата добавления: 2014-01-07