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

       

LL( - грамматики


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

    Определение. КС-грамматика является LL(1) грамматикой тогда и  только тогда, когда 
                             выполняются следующие два условия: 
                       1 . Для каждого нетерминала, являющегося левой  частью нескольких правил: 
                             <A>  ®a 1

    | a 2 | ... | a

    n,  
                            необходимо, чтобы пересечение функций ПЕРВ(a

    i) и ПЕРВ(a j) было 
                            пусто для всех i =/= j. 
                       2 . Для каждого аннулирующего нетерминала <A>,такого что <A> ==>* $, 
                            необходимо, чтобы пересечение  множеств ПЕРВ(<A>) и СЛЕД(<A>) было 
                            пустым. 

    Из определения следует, что грамматики LL(1), в отличие от разделенных грамматик и слаборазделенных, могут содержать правила, начинающиеся нетерминальными символами. Проверим относится ли рассмотренная ранее грамматика Г43  к классу LL(1).


    Для этого необходимо вначале проверить наличие одинаковых значений функций ПЕРВ для правил с одинаковой левой частью. Для правил (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) грамматикой тогда  и только тогда, когда 
                                    множества ВЫБОР, построенные  для правил с одинаковой левой 
                                    частью, не содержат одинаковых элементов. 
           
           


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

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


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