Автор: А.Г.Дымченко

Материал к лекции 4. КС-языки и грамматики. LL(k)-грамматики. Простейший LL(1)-компилятор.

Контекстно-свободные языки

Класс контекстно-свободных языков допускает распознавание с помощью недетерминированного КА со стековой (или магазинной) памятью.

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

Автомат со стековой памятью в отличие от обычного КА имеет стек, в который можно помещать специальные т.н. "магазинные" символы. Переход из одного состояния в другое зависит не только от входного символа, но и от верхних символов магазина (на риҰ сунке в круглых скобках). В начале работы в магазине лежит спеҰ циальный символ S.

При выполнении перехода из магазина удаляются верхние симвоҰ лы, соответствующие правилу, и добавляется цепочка символов, соответствующих переходу (на рисунке изображены в квадратных скобках, первый символ цепочки становится верхним символом маҰ газина). Допускаются также переходы, при которых входной символ игнорируется (и, тем самым, будет входным символом при следуҰ ющем переходе). Эти переходы называются e-переходами. Автомат называется недетерминированным, если при одних и тех же состоҰ янии, входном символе и вершине магазина возможен более чем один переход. Если при окончании цепочки автомат находится в одном из конечных состояний, а стек пуст, цепочка считается доҰ пущенной (после окончания цепочки могут быть сделаны e-перехоҰ ды).

            -------¬0(S) ------¬1(0) -T---T¬
            ҰНачало+---->+  1  +---->+Ұ 2 ҰҰ
            L-------[0]  LT---T- []  L+---+-
                          L-<--       L-<--
                         0(0)[00]     1(0)[]

Какие цепочки допускает этот автомат? - упражнение.

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

     e(A)[x] для каждого правила грамматики A:x
     а(а)[]  для каждого терминала а

Можно построить и другой автомат, который также содержит одҰ но состояние и имеет следующие переходы:

     а(е)[а] для каждого терминала а
     е(x)[A] для каждого правила грамматики A:x

Удобно считать, что в начале разбора магазин этого автомата пуст. Тогда в конце разбора в магазине останется символ S. КаҰ кие (правые или левые) выводы делают (для однозначной грамматиҰ ки) только что построенные автоматы? - упражнение.

По недетерминированному КА с магазинной памятью можно построить КС-грамматику (упражнение). Таким образом класс КС-языков и класс языков, допускаемых автоматами с магазинной памятью, эквивалентны.

К сожалению, не каждый КС-язык допускает разбор с помощью детерминированного автомата. Например, язык цепочек-палиндромов из 0 и 1 не может быть допущен детерминированным КА с магазинҰ ной памятью (как выглядит недетерминированный автомат, допускаҰ ющий этот язык? - упражнение). Таким образом, недетерминированҰ ные автоматы со стеком могут распознавать более широкий класс языков, чем детерминированные автоматы со стеком - в этом их существенное отличие от КА. Практический интерес для реализации компиляторов представляют детерминированные КС-языки - собственное подмножество КС-языков, допускающее распознавание с помощью детерминированных автоматов с магазинной памятью.

Два (недетерминированных) автомата, построенных выше для КС-грамматики определяют два класса методов разбора КС-языков: сверху-вниз снизу вверх.

В первом случае (пример - рекурсивный спуск) при просмотре цепочки слева направо естественно будут получаться левые вывоҰ ды. При детерминированном разборе проблема будет состоять в том, какое правило применить для раскрытия самого левого нетерҰ минала.

Во втором случае детерминированный разбор удобно формализоҰ вать в терминах "сдвиг" (перенос символа из входной цепочки в магазин) и "свертка" (применение к вершине магазина какого-либо правила грамматики). При просмотре входной цепочки слева напраҰ во при этом будут получаться правые выводы. Проблема в этом случае состоит в выборе между сдвигом и сверткой и в выборе правила для свертки. Следующие лекции будут посвящены практиҰ ческим методам разбора детерминированных КС-языков сверху вниз и снизу-вверх.

Лемма о разрастании для КС-языков

Для каждого КС-языка существует такое число m, что любую принадлежащую языку цепочку z : |z|>m можно разбить на 5 частей

                                                 n   n
z = uvwxy : |vx| > 0, |vwx|<=m и цепочки вида  uv  wx  y,  n>=0
также принадлежат языку.

Доказательство: Пусть КС-грамматика языка содержит q нетерҰ миналов, а самая длинная цепочка в правой части правил имеет длину k. Рассмотрим дерево вывода для цепочки длины k**(2*q+3) и оставим в нем только те ветвления, которые ведут к терминальҰ ным листьям (игнорируем e-правила). Утверждение: Существует маршрут от корня до кроны, который имеет по крайней мере q+2 левых (или q+2 правых) ветвления (упражнение). Если все вершины дерева пометить раскрытыми нетерминалами, то по крайней мере один из них (например, A) встретится на этом маршруте два раза (упражнение). При это крона дерева естественным образом разобьҰ ется на 5 частей:

                          S
                        / Ұ \
                       /  A  \
                      / / Ұ \ \
                     / /  A  \ \
                    / / /   \ \ \
                   --------------
                    u v   w  x  y

Это и будет искомое разбиение цепочки, так как uvwxy будут удовлетворять требованиям леммы (упражнение).

                                  n  n  n
Упражнение: показать, что  язык  0  1  2  не  является  контекҰ
стно-свободным.

Преобразование КС-грамматик.

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

Удаление бесполезных символов и правил

Назовем символ А бесполезным, если он не встречается ни в одном выводе цепочки терминалов из начального символа грамматиҰ ки. Oчевидно, что бесполезные символы и все содержащие их праҰ вила могут быть удалены из грамматики. Например, в грамматике

   S : a | A ;   A : Ab ;   B : b

из нетерминала A нельзя вывести ни одной терминальной цепочки, а нетерминал B не может быть выведен из начального символа S.

Множество нетерминалов, из которых выводятся терминальные цепочки легко вычислить:

    K := { A | существует правило A:терминалы }; К1 := пусто;
    цикл пока К != К1 выполнять
      К1 := К
      К := К U { A | существует правило
                     A:(нетерминалы из К1 и и терминалы) }
    конец цикла

Следствие: проблема пустоты КС-языка разрешима - язык пуст, если и только если S не принадлежит K.

После удаления из грамматики нетерминалов, не принадлежащих К, несложно найти множество L небесполезных символов:

    L := {S}; L1 := пусто;
    цикл пока L != L1 выполнять
      L1 := L
      L := L U { B | сущ. правило A:..B.., и А принадлежит L1 }
    конец цикла

После удаления дополнения L из грамматики, она не будет соҰ держать бесполезных символов (доказательство - упражнение). БуҰ дут ли удалены все бесполезные символы из грамматики, если если применить сначала второй, а затем первый алгоритм?

Устранение е-правил

Правило вида A:e будем называть e-правилом. Если язык не соҰ держит пустой цепочки, то из грамматики можно удалить все e-правила, в противном случае можно ввести новый начальный симҰ вол S1, правилo S1 : S | e, и удалить все остальные e-правила. Описание алгоритма - упражнение. Указание: вычислить вначале множество нетерминалов, из которых выводится пустая цепочка. Следствие: КС-язык, не содержащий пустой цепочки, может быть описан неукорачивающей грамматикой.

Устранение циклов и цепных правил

Обозначим символом :: выводимость одной цепочки из другой с помощью непустой последовательности правил. Назовем циклом выҰ вод вида A::A... . Для устранения циклов можно удалить из грамҰ матики все цепные правила вида A:B. Для каждого нецепного праҰ вила вида А:..., добавим в грамматику правила B:..., для всех B, из которых с помощью цепных правил выводится А. После этого удаление цепных правил не изменит языка. Грамматику без циклов, e-правил и лишних символов называют приведенной.

Упражнение. Грамматика в нормальной форме Хомского содержит только правила вида A:BC, A:a и S:e, если язык содержит пустую цепочку. Покажите, что любой КС-язык можно описать грамматикой в нормальной форме Хомского.

Устранение левой рекурсии

Нетерминал A называется рекурсивным, если существует вывод: Если x=e, то A называется леворекурсивным, если y=e, то правоҰ рекурсивным.

        A :: xAy

Упражнение: что можно сказать про язык, описанной грамматиҰ кой без рекурсивных нетерминалов?

Метод рекурсивного спуска не работал для леворекурсивных грамматик. От левой рекурсии всегда можно избавится (Это не озҰ начает, что метод рекурсивного спуска применим к любому языку.) Покажем вначале, как 8устранить прямую левую рекурсию, т.е. правила вида A:A... . Пусть

        A : Aa1|...|Aan | b1|...|bn 

все A-правила грамматики, и ни одна из цепочек bi не начинается с A. Тогда, применяя A-правила к самому левому нетерминалу, из А можно вывести следующее регулярное множество цепочек:

        (b1|...|bn)(a1|...|an)*

Это множество выводится и из преобразованной грамматики:

        A : b1|...|bn | b1T|...|bnT
        T : a1|...|an | a1T|...|anT

Устранить общую левую рекурсию можно с помощью следующего процесса, напоминающего последовательное исключение переменных при решении системы уравнений методом Гаусса.

    цикл для i от 1 до n
      инвариант: для всех k < i (сущ. правило Ak:Al...) = > l > k
      цикл для j от 1 до i-1
        инвариант: для всех k < j (сущ. правило Ak:Al...) = > l > k
        каждое правила Ai:Aj... заменить на правила Ai:Lj...,
        где Lj - все правые части Aj-правил
      конец цикла
      устранить прямую левую рекурсию для Ai
    конец цикла

Упражнение. Грамматика в нормальной форме Грейбах содержит только правила вида A:aB, где a-терминал, B - последовательҰ ность (может быть пустая) нетерминалов, а также S:e, если язык содержит пустую цепочку. Покажите, что любой КС-язык можно опиҰ сать грамматикой в нормальной форме Грейбах.

Алгоритм Кока-Янгера-Касами

Даны: КС-грамматика и цепочка символов. Требуется опредеҰ лить, выводима ли данная цепочка из грамматики. Напомним, что для регулярных языков аналогичная проблема решалась за линейное от длины цепочки время. Рассмотренный ниже алгоритм решает проблему принадлежности цепочки КС-языку за полиномиальное от длины цепочки время.

Вначале преобразуем грамматику в нормальную форму Хомского, т.е. в грамматику с правилами вида A:BC и A:a. Пусть a1a2...an - исходная цепочка символов. Построим треугольную таблицу Ti,j: 1<=i<=n, 1<=j<=n-i+1. Тi,j - множество нетерминалов, из которых выводится цепочка терминалов aj...aj+i-1. (подцепочка длины i, левый символ которой имеет индекс j).

| T1,j нетерминалы, из которых выводятся односимвольные цепочки
   цикл для j от 1 до n
     T1,j := { A | существует правило A:aj }
   конец цикла
| первым шагом вывода из А  i-символьной  цепочки  (i>1)  может
| быть только применение правила A:BC, где из B выводится левая
| подцепочка, а из C - правая, причем обе подцепочки имеют длиҰ
| ну меньшую i. Так называемое "динамическое программирование":
   цикл для i от 2 до n
     цикл для j от 1 до n-i+1
       Tij := пусто
       цикл для k от 1 до i-1
         Tij := Tij U { A | (существует правило A:BC)
                          и (B принадлежит Тk,j)
                          и (C принадлежит Тi-k,j+k) }
       конец цикла
     конец цикла
   конец цикла
   цепочка выводима из грамматики := S принадлежит Tn,1

Алгоритм требует времени порядка n**3 и памяти n**2, где n - длина цепочки (докажите!). Это делает его малопригодным для практических целей. На практике применяются специальные подклассы КС-грамматик, для которых существуют линейные алгоҰ ритмы разбора.

LL(k) языки и грамматики

Рассмотрим дерево вывода в процессе получения левого вывода цепочки. Промежуточная цепочка в процессе вывода состоит из цеҰ почки из терминалов w, самого левого нетерминала A, недовывеҰ денной части x:

             -S--
            /    \
           / -А-x-\
          /  Ұ     \
          -w-+-u----

Для продолжения разбора требуется заменить нетерминал A по одному из правил вида A:y. Если требуется, чтобы разбор был деҰ терминированным (без возвратов), это правило требуется выбирать специальным способом. Говорят, что грамматика имеет свойство LL(k), если для выбора правила оказывается достаточно рассмотҰ реть только wAx и первые k символов непросмотренной цепочки u. Первая буква L (Left, левый) относится к просмотру входной цеҰ почки слева направо, вторая - к используемому левому выводу.

   Определим два множества цепочек:
     FIRST(x) - множество терминальных цепочек, выводимых из x,
                укороченных до k символов.
     FOLLOW(A)- множество укороченных до k символов  терминальҰ
                ных цепочек,  которые  могут  следовать  непосҰ
                редственно за A в выводимых цепочках.

Грамматика имеет свойство LL(k), если из существования двух цеҰ почек левых выводов:

       S :: wAx : wzx :: wu
       S :: wAx : wtx :: wv

из условия FIRST(u)=FIRST(v) следует z=t.
   В случае k=1 для выбора  правила  для  А,  достаточно  знать
только нетерминал A и а - первый символ цепочки u:
   следует выбрать правило A:x, если а входит в FIRST(x)
   следует выбрать правило A:е, если а входит в FOLLOW(A)
Покажите, что такой выбор правил непротиворечив  -  упражнение.
Указание: Воспользуйтесь фактом,  что  для  LL(1)-грамматики  с
правилами   A:x   и   A:y   множества    FIRST(xFOLLOW(A))    и
FIRST(yFOLLOW(A)) не пересекаются (упражнение). Для k>1 это утҰ
верждение  неверно   (упражнение).
   Упражнение: предложите алгоритм, вычисляющий множества FIRST
и FOLLOW для символов КС-грамматики
   LL(к)-свойство накладывает довольно сильные  ограничения  на
грамматику. Например, LL(2) грамматика

        S : aS | a

не обладает свойством LL(1), т.к. FIRST(aS)=FIRST(a)={a}. В данном случае можно понизить величину k с помощью "факторизаҰ ции" (вынесения множителя за скобку):

        S : aA
        A : S | e

Любая LL(k)-грамматика однозначна. Леворекурсивная грамматика не принадлежит классу LL(k) ни для какого k. (Доказательство этих двух фактов - упражнение). Иногда удается преобразовать не LL(1)-грамматику в эквивалентную ей LL(1)-грамматику с помощью устранения левой рекурсии и факторизации. Однако проблема суҰ ществования эквивалентной LL(k)-грамматики для произвольной не LL(k)-грамматики неразрешима. Существуют детерминированные языки, которые не являются

                                     n  n   n  2n
LL(k) ни для какого k, например  - {0 10 U 0 10 | n>=1}.

Пример

Грамматика для арифметических формул:

        Ф : Т | Ф + Т
        Т : М | Т * М
        M : ( Ф ) | а

не является LL(1), т.к. правила для Ф и Т содержат прямую левую рекурсию, устраним ее:

      ------------------------T------------T------------¬
      Ұ                       Ұ FIRST      Ұ   FOLLOW   Ұ
      +-----------------------+------------+------------+
      Ұ Ф  : Т Ф1             Ұ  ( a       Ұ    ) e     Ұ
      Ұ Ф1 : е | + Т Ф1       Ұ  + e       Ұ    ) e     Ұ
      Ұ Т  : М Т1             Ұ  ( a       Ұ    + ) e   Ұ
      Ұ Т1 : е | * М Т1       Ұ  * e       Ұ    + ) e   Ұ
      Ұ M  : ( Ф ) | а        Ұ  ( a       Ұ    * + ) e Ұ
      L-----------------------+------------+-------------

Пустые цепочки порождают только нетерминалы Ф1 и Т1. Более одного правила имеется для нетерминалов Ф1 и Т1; множества FIRST(Ф1), FOLLOW(Ф1) и FIRST(T1), FOLLOW(T1) не пересекаются. Таким образом, преобразованная грамматика является LL(1).

Символы e, помещенные в множества FIRST и FOLLOW имеют разҰ ный смысл и не приводят к конфликтам: e в множестве FIRST исҰ пользуется для обозначения возможности вывода пустой цепочки из данного нетерминала, e в множестве FOLLOW означает отсутствие следующего символа в конце строки терминалов. На практике роль e во втором случае может играть терминатор строки.

Простейший LL(1)-компилятор формул

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

Компилятор преобразует цепочки языка, соответствующего грамҰ матике:

      S: T {+T}
      Т: E {*Е}
      Е: <операнд>|(S)

в постфиксную запись.

%{                       /* Коды лексем и метасимволов */
#define ID      1          /* Лексема - идентификатор */
#define META    100        /* Метасимволы грамматики */
#define S       (META+0)
#define T       (META+1)
#define E       (META+2)
                         /* Коды переходов */
#define NOGO    100        /* Коды завершения разбора */
#define OK      (NOGO+1)
#define ERR     110        /* Коды ошибок */
%}

%%
"+"|"*"|"("|")" { return(*yytext); }
[A-Z0-9]+       { printf("%s ",yytext); return(ID); }
\n              { }
.               { printf("%s: ",yytext); error(0); }
%%

static lexcode, oldcode;  /* Коды очередной и предыдущей лексем */

main() {
  lexcode = yylex();
  parse( S ); printf("\n");
  if ( lexcode ) error(4);  /* Завершился ли разбор по концу файла? */
}

/*
 * LL(1)-таблицы состоят из четырех полей:
 *   - номер лексемы или метасимвола для сопоставления
 *   - номер действия при успехе (семантическая программа)
 *   - переход при   успехе (номер строки/успех/неуспех/ошибка)
 *   - переход при неуспехе
 */
static char stable[] = {    /* LL(1) - таблица для S */
   /* 00 */ T,     0,      1,      ERR+1,
   /* 01 */ '+',   1,      2,      OK,
   /* 02 */ T,     2,      1,      ERR+1,
};
static char ttable[] = {   /* LL(1) - таблица для T */
   /* 00 */ E,     0,      1,      ERR+2,
   /* 01 */ '*',   1,      2,      OK,
   /* 02 */ E,     2,      1,      ERR+2,
};
static char etable[] = {   /* LL(1) - таблица для E */
   /* 00 */ ID,    0,      OK,     1,
   /* 01 */ '(',   0,      2,      NOGO,
   /* 02 */ S,     0,      3,      ERR+1,
   /* 03 */ ')',   0,      OK,     ERR+3,
};
/* Указатели на LL(1) - таблицы */
static char *blocks[] = { stable, ttable, etable, };

/*
 * Интерпретатор LL(1)-таблиц
 * Вход:      m - лексема или метасимвол
 * Результат: 1, когда сопоставление удалось
 */
parse (m) {
 register char *block, *p, sign;
  if ( m < META ) {
    if (lexcode != m) return(0);
    oldcode = lexcode; lexcode = yylex();
    return(1);
  }
  p = block = blocks[m-META];
  for(;;) {
    if ( parse( *p++ ) ) {
      switch ( *p++ ) {   /* Семпы */
        case 0:  break;
        case 1:  sign = oldcode; break;
        case 2:  printf("%c ", sign); break;
        default: error(1);
      }
    } else p += 2;
    if      ( *p <  NOGO ) p = block+*p*4;
    else if ( *p <= OK ) return (*p-NOGO);
    else error(*p-ERR);
  }
}

static char *ermsg[] = { /* Тексты сообщений об ошибках */
  /* 00 */ "ошибочный символ",   /* 01 */ "отказ",
  /* 02 */ "не найден операнд",  /* 03 */ "не хватает )",
  /* 04 */ "не найден знак",
};

error(e) { printf ("%s\n", ermsg[e]); exit(1); }
yywrap() { return(1); }

Упражнение по программированию: интерпретатор LL(1)-таблиц разбора интенсивно пользуется рекурсией, что делает парсер не слишком эффективным. Реализуйте нерекурсивный интерпретатор таблиц.