Пример 18

Рассмотрим грамматику

S → аАВе

А → Abe | b

В → d

Предложение abbcde сводится к S с помощью следующих шагов:

abbcde

aAbcde

aAdle

аАВе

S

Строка abbcde сканируется слева направо в поисках подстроки, соответствующей правой части какой-либо продукции. Такими подстроками являются b и d. Выбираем крайнее слева b и заменяем его нетерминалом A, который представляет собой левую часть продукции A → b;таким образом, получаем строку aAbcde. Теперь правым частям продукций соот­ветствуют подстроки Abc, b и d. Выбираем для замены подстроку Abc и заме­няем ее нетерминалом А в соответствии с продукцией А→Аbс. В результате получаем строку aAde. Заменяя d на B, левую часть продукции В → d, получаем аABе, которая в соответствии с первой продукцией заменяется стартовым символом S. Итак, последова­тельность из четырех сверток позволяет привести строку abbcde к стартовому символу S. Эти сокращения представляют собой обращенное (т.е. записанное в обратном порядке) правое порождение S aABe aAde aAbcde abbcde.

Дата добавления: 2014-12-27