Теория и реализация языков программирования



             

Преобразования КС-грамматик - часть 2


(4) Положить G1 = ((N

Ne)
{S}, T, P1, S), где P1 состоит из правил множества P, содержащих только символы из Ne
T,

Чтобы устранить все бесполезные символы, необходимо применить к исходной грамматике сначала Алгоритм 4.2, а затем Алгоритм 4.1.

Пример. Все символы следующей грамматики

S

AS | b

A

AB

B

a

являются достижимыми. Поэтому нарушение предложенного порядка применения к ней алгоритмов приведет лишь к частичному решению задачи.

КС-грамматика без бесполезных символов называется приведенной. Легко видеть, что для любой КС-грамматики существует эквивалентная приведенная. В дальнейшем будем предполагать, что все рассматривамые грамматики - приведенные.




Содержание  Назад  Вперед