Пред.Страница След.Страница Раздел Содержание
1.3.2. Грамматики типа 1
Грамматики типа 1, которые называют также контекстно-зависимыми грамматиками,не допускают
использования любых правил. Правила вывода в таких грамматиках должны иметь
вид:
c1<A>c2 ® c1w
c2,
где c1, c2 - цепочки, возможно пустые, из множества (Vт È Va)*, символ <А> Î Va и цепочка w Î (Vт È Va)*. Цепочки c1 и c2 остаются неизменными при применении правила, поэтому их называют контекстом (соответственно левым и правым), а грамматику - контекстно зависимой.
Грамматики типа 1 значительно удобнее на практике, чем грамматики типа 0, поскольку в левой части правила заменяется всегда один нетерминальный символ, который можно связать с некоторым синтаксическим понятием, в то время как в грамматике типа 0 можно заменять сразу несколько символов, в том числе и терминальных.
Например, грамматика:
Г1. 4:
Vт = {a, b, c, d}, Va = {<I>, <A>, <B>}
R = { <I> ® aA<I>,
A<I> ® AA<I>,
AAA ® A<B>A,
A ® b,
b<B>A ® bcdA,
b<I> ® ba }
является контекстно-зависимой,
поскольку второе и шестое правила имеют непустой левый контекст, а третье и
пятое правила содержат оба контекста. Вывод в такой грамматике может иметь вид:
<I> Þ a<A><I> Þ a<A><A><I> Þ ab<A><I> Þ abb<I> Þ abba.