5.6. Приведение грамматик к ll - форме

Из рассмотренного материала ясно, что методика конструирования левого анализатора для заданной LL(k) - грамматики G сводится к выполнению двух этапов.

На первом этапе необходимо получить управляющую таблицу M для k - предсказывающего алгоритма разбора. Этот этап может быть полностью автоматизирован при помощи алгоритма (программы) - А2, выполняющего соответствующее преобразование А2: G®M.

На втором этапе требуется написать программу - анализатор, моделирующую работу k - предсказывающего алгоритма разбора, в котором используется управляющая таблица М, полученная на первом этапе.

Для разработчика компилятора основные трудности связаны не столько с реализацией этих двух этапов, сколько с получением LL - грамматики, для которой можно применить эту методику.

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

В п.5.3 было показано, что существуют признаки (условия), проверив которые можно определить, обладает ли грамматика LL(1) - свойствами. Практика показывает, что для большинства формальных языков “очевидной” (наиболее естественной) оказывается не LL(1) - грамматика. В то же время, очень большое количество синтаксических конструкций языка можно описать при помощи LL(1) - грамматики. Для разработчика компилятора проблема заключается в том, чтобы имея грамматику G, не обладающую признаками LL(1), получить эквивалентную ей LL(1) - грамматику , генерирующую тот же язык так, что L( )=L(G) - LL(1) -язык.

В связи с этим возникает два вопроса:

1. Все ли языки обладают LL(1) - грамматикой ?

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

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

Таким образом, общего решения этой проблемы не существует. Однако на практике встречается очень много частных случаев, когда решение все же удается найти, путем применения определенных приемов преобразования исходной грамматики, в результате которых из нее устраняются нежелательные свойства. К таким нежелательным свойствам относятся:

- наличие леворекурсивных циклов;

- наличие леворекурсивных правил;

- наличие правил, в которых альтернативные правые части начинаются одной и той же цепочкой символов.

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

Определение. Нетерминал А КС-грамматики G=(N,S,P,S) называется рекурсивным, если AÞ⁺ a A b для некоторых a и b. Если a = e, А называется леворекурсивным, если b = e, А называется праворекурсивным. Грамматика, имеющая хотя бы один леворекурсивный нетерминал, называется леворекурсивной (аналогично определяется праворекурсивная грамматика). ¨

Рассмотрим следующие преобразования:

Устранение леворекурсивных циклов и правил. Если для некоторого А имеет место А Þ ^k Ab, k>1, то говорят, что грамматика имеет леворекурсивный цикл. Например, грамматика с правилами

А®ВС,

В®СD,

C®AE,

содержит леворекурсивный цикл по А, поскольку

AÞ BC Þ CDC Þ AEDC или AÞ ³ AEDC.

Чтобы избавиться от леворекурсивного цикла используют следующую процедуру. Возьмем в качестве примера грамматику G c правилами

S®Aa,	C® Dd,
A®Bb,	C® e,
B®Cc,	D® Az,

которая имеет леворекурсивный цикл по А.

Упорядочим нетерминалы S=A₁, A=A₂ , ..., D=A₅ и перепишем грамматику в виде:

A1®A2a,	A4®A5d,
A2®A3b,	A4®c,
A3®A4c,	A5®A2z.

Правила вида: A_i®A_ja , для которых i³j, оставим без изменения. В правилах, где это условие нарушено, выполняем замещение A_j, используя все правила, содержащие A_j в левой части. Эта процедура выполняется до тех пор, пока все правила грамматики не будут приведены к требуемому виду. В нашем примере условие нарушено в правиле (A₅®A₂z ) и последовательность преобразований выглядит следующим образом:

(A₅®A₂z ) Þ(A₅®A₃bz ) Þ(A₅®A₄cbz ) Þ (A₅® A₅dcbz; A₅® ecbz).

Преобразованная грамматика имеет вид:

S®Aa,	C®Dd,
A®Bb,	C®c,
B®Cc,	D® ecbz,
	D®Ddcbz.

В этой грамматике нет леворекурсивных циклов, но появилось леворекурсивное правило D®Ddcbz.

Для устранения непосредственной левой рекурсии в правилах грамматики можно воспользоваться результатами следующей леммы.

Лемма 5.1. Пусть G=(N,S,P,S) КС-грамматика, в которой

A® Aa₁ | Aa₂ | ... | Aa_m | b₁ | b₂ | ... | b_n

все А - правила из P и ни одна из цепочек b_i не начинается с A.

Пусть =( NÈ { }, S , ,S), где - новый нетерминал, а получается из P заменой A - правил на правила

A® b₁ | b₂ | ... | b_n | b₁ | b₂ | ... | b_n

® a₁ | a₂ | ... | a_m | a₁ | a₂ | ... | a_m .

Тогда L( )=L(G). ¨

В рассмотренном выше примере мы имеем D - правила вида D®Ddcbz / ecbz. Согласно лемме, их можно заменить на правила

D® ecbz / ecbz

® dcbz / dcbz ,

где - новый нетерминал. В результате этих преобразований мы избавились от леворекурсивного цикла и устранили из правил непосредственно левую рекурсию. Левая рекурсия заменена теперь на правую (в правиле ® dcbz ), которая не представляет проблемы для левого анализатора.

Факторизация. Процедура факторизации используется для преобразования A - правил грамматики G с альтернативными правыми частями, начинающимися с одной и той же цепочки a:

A® ab₁ | ab₂ | ... | ab_n .

Сама процедура состоит из двух этапов:

1. Цепочка a выносится за скобки

A® a(b₁ | b₂ | ... | b_n),

причем скобки в такой записи являются метасимволами (т.е. не принадлежат множеству символов грамматики).

2. Для выражения в скобках вводится новый нетерминал , что приводит к получению правил новой грамматики :

A®a ,

® b₁ | b₂ | ... | b_n .

В рассматриваемом примере факторизацию следует применить к D - и - правилам, после чего будет получена грамматика с правилами

S®Aa,	C® e,
A®Bb,	D® cbz ,
B®Cc,	®dcbz ,
C®Dd,	® e.

Итак, мы устранили из исходной грамматики G нежелательные свойства. В качестве упражнения убедитесь, что полученная грамматика все же не является LL(1) - грамматикой, зато является LL(2) - грамматикой (проверьте также условие строгости).

В заключение рассмотрим одну из разновидностей леворекурсивных правил, а именно правила вида

A® Aa B | B.

Такие правила могут порождать цепочки, задаваемые регулярным выражением

B(a B)^* ,

обозначающим множество цепочек

{B, Ba B, Ba Ba B, Ba Ba Ba B,..., и т.д.}.

Каждое правило такого вида можно заменить тремя правилами

A® B ,.

® a B ,

® e.

Эти правила не содержат левой рекурсии ( она заменена на правую рекурсию), но содержат новый нетерминал . Например, применяя эти преобразования к правилам (1), (3) грамматики G из примера 5.2

(1) E®E+T,

(3) T® T*F,

мы получим правила

E® T ,	T® F ,
® +T ,	® *F ,
® e,	® e.

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