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


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


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

            <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) выполняется.


    - Начало -  - Назад -  - Вперед -