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



LL( - грамматики - часть 2


Для этого необходимо вначале проверить наличие одинаковых значений функций ПЕРВ для правил с одинаковой левой частью. Для правил (1) и (2) имеем
 

      ПЕРВ(<B><C>a) = ПЕРВ(<B>) И

      ПЕРВ(<C>) = {a,b,d,c},
      ПЕРВ(g<D><B>) = {g},

    а для правил (5) и (6) имеем
     

        ПЕРВ(<D>a<B>) = ПЕРВ(<D>) И

        ПЕРВ(a<B>) = {a,d},
        ПЕРВ(ca) = {c}.

      Полученные результаты показывают, что первое условие LL(1) грамматики выполняется.
      Второе условие необходимо проверить для правил (3) и (7) рассматриваемой грамматики. Вычисляя функции ПЕРВ и СЛЕД для правила (8), имеем:

          ПЕРВ(<B>) = {b} и СЛЕД(<B>) = {a,c,d,g,f}.

        Эти функции не имеют одинаковых значений, следовательно грамматика Г43

        является грамматикой LL(1).
        Рассматриваемый класс грамматик можно определить также с помощью множеств выбора следующим образом:
         

        Определение

        . КС-грамматика называется LL(1) грамматикой тогда  и только тогда, когда 
                                  множества ВЫБОР, построенные  для правил с одинаковой левой 
                                  частью, не содержат одинаковых элементов. 

         
         

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

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




      Содержание  Назад  Вперед