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

Выделение общих частей


    Второй вид преобразований, который называют выделением общих частей, применяют для устранения правил с одинаковыми левыми частями, правые части которых  начинаются одинаковыми последовательностями символов.
    Например, рассмотрим грамматику с правилами

        <I> 

        ® a<I>,


        <I> 

        ® a.

      Эта грамматика не является LL(1) грамматикой, т.к. значения функций ПЕРВ(a<I>) и ПЕРВ(a) совпадают. Введем дополнительный нетерминал A и преобразуем грамматику так:

          <I> 

          ® a<A>,


          <A> ®

          <I>|$.

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

            <A> 



            ® a

            µ1 | a µ2 | ... | a

            µn ,

          то, вводя дополнительный нетерминал <A'>, их можно преобразовать к виду:

              <A> 

              ® a

              <A'>


              <A'> 

              ® µ1

              | µ2 | ... | µn.

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

                Г3. 6:    R = { <I>  ®

                b<A><I><B>,

                            <I>  ®

                  b<A>,

                    <A> 

                    ® d<I>ca,


                    <A> 

                    ® f,
                    <B> 

                    ®c<A>a,


                    <B> 

                    ® c  }.

                       

                    Эта грамматика не является LL(1) грамматикой, поскольку нарушено первое условие. Воспользуемся способом выделения общих частей: введем нетерминалы D, E и построим правила:

                        <D> 

                        ® <I><B>

                        | $


                        <E> 

                        ® <A>a | $ .

                      В результате включения этих правил в схему грамматики получаем:

                          <I> 

                          ® b<A><D>


                          <D> ®

                          <I><B>


                          <D> ®

                          $


                          <A> ®

                          d<I>ca


                          <A> ®

                          f


                          <B> ®

                          c<E>


                          <E> ®

                          <A>a


                          <E> ®

                          $

                        Для этой грамматики первое условие принадлежности грамматики к классу LL(1) выполняется.
                        Чтобы проверить второе условие, найдем функции ПЕРВ и СЛЕД для аннулирующих правил.

                          СЛЕД(<D>) = СЛЕД(<I>) = ПЕРВ(<B>) И

                          ПЕРВ(ca) = {c},
                          ПЕРВ(<D>) = ПЕРВ(<I>) = {b},
                          СЛЕД(<E>) = СЛЕД(<B>) = СЛЕД(<D>) = {c},
                          ПЕРВ(<E>) = ПЕРВ(<A>) = {d,f}.


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


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

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


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