Алгоритм работает следующим образом. Пусть – КС-грамматика и - входная цепочка. Объект вида назовем ситуацией к цепочке , если - правило из и . Точка «» между и является метасимволом, для которого имеет место условие . Число может быть любым целым числом от нуля (в этом случае точка – первый символ) до (в этом случае она последний символ. Примечание. Если правило имеет вид , то ситуация будет такой: ).
Для каждого построим такой список ситуаций , что тогда и только тогда, когда для некоторых и существуют выводы и . Таким образом, между второй компонентой ситуации и номером списка, где она появляется, заключена часть входной цепочки, выводимая из . Другие условия, налагаемые на ситуацию, просто гарантируют возможность применения правила в выводе некоторой входной цепочки, совпадающей с до позиции .
Последовательность списков будем называть списком разбора для входной цепочки . Заметим, что принадлежит тогда и только тогда, когда в есть ситуация вида .
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2025) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление