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

Материал к лекции 5. Разбор снизу-вверх. Сдвиг-свертка. Простое и операторное предшествование.

Рассмотрим разбор снизу-вверх, при котором промежуточные выҰ воды перемещаются по дереву по направлению к корню. Если считыҰ вать символы цепочки слева направо, то дерево разбора будет выглядеть следующим образом:

             -S--
            /    \
           /-x¬   \
          /   Ұ    \
          --w-+b--u-

Промежуточный вывод имеет вид xbu, где x - цепочка терминалов и нетерминалов, из которой выводится просмотренная часть термиҰ нальной цепочки w, bu - непросмотренная часть терминальной цеҰ почки, b - очередной символ. Чтобы продолжить разбор, можно лиҰ бо добавить символ b к просмотренной части цепочки (выполнить так называемый "сдвиг"), либо выделить в конце x такую цепочку z (x=yz), что к z можно применить одно из правил грамматики B:z и заменить x на цепочку yB (выполнить так называемую "сверҰ тку"):

             -S--                            -S--
            /    \                          /    \
           /-x-b¬ \                        /yB¬   \
          /     Ұ  \                      /   Ұ    \
          --w--b+-u-                      --w-+b--u-
         После сдвига                    После свертки

Если свертку применять только к последним символам x, то мы будем получать правые выводы цепочки. Такой разбор получил назҰ вание LR, где символ L (Left,левый) относится к просмотру цеҰ почки слева направо, а R (Right, правый) относится к получаемым выводам. Упражнение: докажите, что все правые выводы находятся во взаимно-одназначном соотвествии с последовательностями сдвиҰ гов и сверток.

Пример LR-разбора цепочки aabb в соответствии с грамматикой S : SaSb | e. Символ _ указывает на границу между просмотренной и непросмотренной частями цепочки: _aabb : S_aabb : Sa_abb : SaS_abb : SaSa_bb : SaSaS_bb : SaSaSb_b : SaS_b : SaSb_ : S_ Последовательность операций сдвига и свертки существенна - если бы в приведенном примере первой операцией был бы сдвиг, разбор не удалось бы довести до конца. Поэтому для детерминироҰ ванного разбора требуется в каждый момент выбирать между сдвиҰ гом и сверткой (и различными правилами свертки). В курсе будут рассмотрены три способа выбора: простое и операторное предшесҰ твования и LR(k)-разбор.

Грамматики простого предшествования

Грамматика называется обратимой, если в ней нет двух правил с одинаковыми правыми частями. Напомним, что грамматика называҰ ется приведенной, если в ней нет e-правил, бесполезных символов и циклов.

Зададимся целью ввести на множестве терминальных и нетермиҰ нальных символов три отношения (так называемые "отношения предҰ шествования") (будем обозначать их <', =' и >' ) так, чтобы в момент, когда требуется свертка цепочки z, отношения между симҰ волами построенной части вывода (цепочки x в обозначениях из начала лекции) и очередным символом b были следующими:

        <' или =' <' =' =' >'
       L----------+--------+---+---------
            y         z      b     u

Если удастся построить такие отношения, то LR-разбор для обраҰ тимой грамматики можно проводить очень просто:

   - сделать сдвиг, если последний символ x <' b или  последний
     символ x =' b
   - сделать свертку, если последний символ x >'  b,  при  этом
     правая часть правила z заключена между  отношениями  <'  и
     >'.

Грамматика называется грамматикой простого предшествования, если она приведенная, обратимая и между любыми двумя терминалаҰ ми или нетерминалами выполняется не более одного отношения предшествования.

Практически отношения предшествования можно вычислить следуҰ ющим образом (X,Y - терминалы или нетерминалы, A,B,C-нетерминаҰ лы, y - терминал, ... - любая цепочка (м.б. пустая)):

     X =' Y, если в грамматике есть правило A : ...XY...
     X <' Y, если в грамматике есть правило A : ...XB...
                                          и B :: Y...
     X >' y, если в грамматике есть правило A : ...By...
                                        или A : ...BC...
                                          и B :: ...X
                                          и C :: y...

Вычисляя отношения предшествования для грамматики S:aSSb|c, получим: a='S, S='S, S='b, {a,S} <' {a,c}, {b,c} >' {a,b,c}. Эта грамматика является грамматикой простого предшествования.

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

        # <' X, если S :: X...
        X >' #, если S :: ...X

В нашем примере {b,c} >' #, # <' {a,c}.
   Отметим, что отношения <',>',=' не похожи на обычные арифмеҰ
тические отношения <, >, = : =' не является отношением  эквиваҰ
лентности, <' и >' не обязательно транзитивны.

Отношения предшествования удобно занести в матрицу, в котоҰ рой строки и столбцы помечены терминалами и нетерминалами грамҰ матики. Упражнение: заполните эту матрицу. Что значит ситуация, в которой между символами не выполняется ни одного из отношений предшествования?

Грамматики операторного предшествования

Если в правилах приведенной обратимой грамматики не встречаҰ ются рядом два нетерминала, говорят, что грамматика является операторной. Классический пример - грамматика арифметических формул. Для таких грамматик можно вычислять отношения предҰ шествования только на множестве терминальных символов. Для этоҰ го модифицируем правила вычисления отношений предшествования:

   a =' b, если в грамматике имеется правило A : ...ab...
                                         или A : ...aBb...
   a <' b, если в грамматике имеется правило A : ...aB...
                                           и B :: b...
                                         или B :: Cb...
   a >' b, если в грамматике имеется правило A : ...Bb...
                                           и B :: ...a
                                         или B :: ...aC
   # <' a, если в грамматике имеется вывод   S :: Ca...
                                         или S :: a...
   a >' #, если в грамматике имеется вывод   S :: ...aC
                                         или S :: ...a

Если между любыми двумя терминалами выполняется не более одҰ ного отношения предшествования, операторная грамматика называҰ ется грамматикой операторного предшествования.

Вычислим матрицу операторного предшествования для грамматики арифметических формул:

                        ----T------------¬
                        Ұ   Ұ ( a * + ) #Ұ
    S : S + T | T       +---+------------+
    T : T * E | E       Ұ ) Ұ     > > > >Ұ
    E : (S)   | a       Ұ a Ұ     > > > >Ұ
                        Ұ * Ұ < < > > > >Ұ
                        Ұ + Ұ < < < > > >Ұ
                        Ұ ( Ұ < < < < =  Ұ
                        Ұ # Ұ < < < <    Ұ
                        L---+-------------

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

   S : S+S | S*S | (S) | a

и получить разбор, обрабатывая все нетерминалы одинаково.

Линеаризация матрицы предшествования

   Для компактного хранения матрицы предшествования часто можно
использовать следующий прием. По матрице M[n][n], элементы  коҰ
торой принимают только три  значения  (<'  ='  >'),  попытаемся
построить два целочисленных вектора f и g:
   M[i][j] равно >', если f[i]>g[j]
   M[i][j] равно <', если f[i] g[c] ) {
      do {
         d = stpop();
         printf ("%s",view[d]);
      } while ( f[sttop()]==g[d] );
    }
    stpush(c);
  } while(c!=EF);
}

/* Реализация стека терминалов */
#define MAXSTK  100
static int stack[MAXSTK], *stptr;

stinit()  { stptr = stack+MAXSTK; }
stpush(e) {
  if ( stptr==stack ) error(1);
  *--stptr = e;
}
sttop() { stcheck(); return(*stptr);   }
stpop() { stcheck(); return(*stptr++); }
stcheck() { if (stptr==stack+MAXSTK) error(1); }

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

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

Задачи для решения на ЭВМ:

• Переделайте компилятор так, чтобы он не допускал ошибочных (т.е. не порождаемых грамматикой) цепочек.
• Добавьте в компилятор операцию возведения в степень (правоҰ ассоциативная операция "^" с наивысшим приоритетом).
• Переделайте компилятор формул в интерпретатор.
• Добавьте в компилятор операцию "унарный минус".

- конец материала к лекции 5 -