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

1.3.2. Грамматики типа 1

Грамматики типа 1, которые называют также контекстно-зависимыми грамматиками,не допускают использования любых правил. Правила вывода в таких грамматиках должны иметь вид:
 
c₁<A>c₂ ® c₁w c₂,
 
где c₁, c₂ - цепочки, возможно пустые, из множества (V_т И V_a)*, символ <А> О V_a и цепочка                 w О (V_т И V_a)*. Цепочки c₁ и c₂ остаются неизменными при применении правила, поэтому их называют контекстом (соответственно левым и правым), а грамматику - контекстно зависимой.

Грамматики типа 1 значительно удобнее на практике, чем грамматики типа 0, поскольку в левой части правила заменяется всегда один нетерминальный символ, который можно связать с некоторым синтаксическим понятием, в то время как в грамматике типа 0 можно заменять сразу несколько символов, в том числе и терминальных.

Например, грамматика:

Г_{1. 4}:
V_т = {a, b, c, d}, V_a = {<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.

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