3.8 Преобразование грамматик к виду ll(1).

3.8.1 Исключение леворекурсивных правил.

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

• Допустим, что в схеме заданной грамматики имеются правила: <A>  <B> | <A><B>. Первое условие определения LL(1) грамматики говорит о том, что функции ПЕРВ для правил с одинаковой левой частью не должны иметь одинаковых элементов, но для заданной грамматики это не так, поскольку

ПЕРВ(<A><B>) = ПЕРВ(<A>) = ПЕРВ(<B>).

Следовательно, грамматика, содержащая рассматриваемые правила, не является LL(1) грамматикой.

• Возьмем другие правила, обеспечивающие получение такого же множества цепочек, что и в первом случае : <A>  <A><B> | $. Первое условие выполняется, но имеем: СЛЕД ( <A> ) = ПЕРВ (<B>) и ПЕРВ (<A>) = ПЕРВ (<B>), поскольку A можно заменить $. Эти равенства показывают, что нарушается второе условие из определения LL(1) грамматики. Из приведенных рассуждений можно сделать вывод о том, что LL(1) грамматика не должна содержать леворекурсивных правил. Конечно, лучше не использовать леворекурсивные правила еще на этапе построения грамматики, но если уж они появились, то их можно исключить, пользуясь приемом, описанным в предыдущем разделе.

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

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

<I>   a<I>,<I>   a.

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

<I>   a<A>,<A>  <I>|$.

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

<A>    µ₁ |  µ₂ | ... |  µ_n ,

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

<A>    <A'><A'>   µ₁ | µ₂ | ... | µ_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).