Исключение цепных правил
<B>, где <A>,<B> ОVA, |
| |
- Идея доказательства заключается в следующем. Если схема грамматики имеет вид
- 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 }
Последний вид рассматриваемых преобразований связан с удалением из
грамматики правил с пустой правой частью.
$ называется аннулирующим правилом. |
След.Страница Раздел Содержание
