Формальные языки

       

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




    Грамматики типа 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.


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

             
             


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