Исключение цепных правил

Идея доказательства заключается в следующем. Если схема грамматики имеет вид
 

R = {...,<A> ®

<B>,...,<B> ®

<C>, ... , <C> ® a<X>

},

то такая грамматика  эквивалентна грамматике со схемой
 

R' = {...,<A> ®

a<X>,...},

поскольку вывод в грамматике со схемой R цепочки a<X> :

<A> Ю<

B> Ю <C>

Ю a<X>

может быть получен  в грамматике со схемой R' с помощью правила <A>

® a<X>.
В общем случае доказательство последнего утверждения можно выполнить так.
Разобьем R на два подмножества R1 и R2, включая в R1 все правила вида <A> ® < B>.
Для каждого правила из R1 найдем множество правил S(<Ai>), которые строятся так:
если <Ai> Ю

* <Aj> и в R2 есть правило <Aj>

® a

, где a - цепочка словаря (Vт

ИVA)* ,
то в S(<Ai>) включим правило <Ai>  ®   a .
Построим новую схему R' путем объединения правил R2 и всех построенных
множеств S(<Ai>). Получим грамматику Г' = {Vт ,Va , I , R'}, которая эквивалентна


заданной и не содержит правил вида <A> ®

<B>.
В качестве примера выполним исключение цепных правил из грамматики

Г1. 9


со схемой :

Г1. 9:     

R={<E> ®   <E> + <T> | <T>,


                  < T> ® < T> * <F> | <F>,



                   <F> ® ( <E> ) | a}.



Вначале разобьем правила грамматики на два подмножества:
 
R1 = { <E> ®

<T>,<T> ®   <F> } ,
R2 = { <E> ®

<E>+<T>, <T> ®

<T>*<F>, <F>® (<E>) | a }


Для каждого правила из R1 построим соответствующее подмножество.
 
S(<E>) = { <E> ®<

T>*<F>, <E> ® (<E>) | a },
S(<T>) = { <T> ®

(<E>) | a}


В результате получаем искомую схему грамматики без цепных правил в виде:

R2 U S(<E>) U S(<T>) = { <E> ®

--> <T>+<T> | <T>*<F> | (<E>) | a,



<T> ®

<T>*<F> | (<E>) | a,
<F> ®

(<E>) | a }


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


 

Определение. Правило вида <A> ® $ называется аннулирующим правилом.

Пред.Страница 

След.Страница   Раздел   Содержание

 


Содержание раздела






---