Разбор снизу-вверх. Сдвиг-свертка.

             Простое и операторное предшествование.

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

             -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[j]
   M[i][j] равно =', если f[i]=g[j]
Для получения этих векторов используется следующий метод:
   - построить ориентированный граф, содержащий n вершин типа F
     и n вершин типа G;
   - построить ребро графа F[i]->G[j], если i >' j
   - построить ребро графа F[i]<-G[j], если i <' j
   - склеить вершины F[i] и G[j], если i =' j
Если полученный граф циклический, то  линеаризация  невозможна.
Иначе положить f[i] равным длине самого длинного пути из  F[i],
g[i] равным длине самого длинного пути из G[i].
   Применив этот метод  для  построенной  матрицы  операторного
предшествования, получим:
        символ  # a + * ( )
        f       0 4 2 4 0 4
        g       0 5 1 3 5 0

   Еще один компилятор формул (операторное предшествование)

   Для реализации компилятора формул в польскую постфиксную за-
пись свяжем с каждой сверткой действие:
        a : Число или имя       - напечатать число или имя
        S : a | (S)             - ничего не делать
        S : S*S | S+S           - напечатать знак операции
Построенный частичный вывод x будем хранить в стеке:

%{                       /* Коды лексем и метасимволов */
#define EF      0          /* конец файла */
#define ID      1          /* идентификатор или число */
#define PLUS    2          /* '+' */
#define MULT    3          /* '*' */
#define LP      4          /* '(' */
#define RP      5          /* ')' */
%}

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

static char *view[] = { /* Постфиксное представление терминалов */
   "",    /* конец файла */      "",    /* идентификатор */
   "+ ",  /* '+' */              "* ",  /* '*' */
   "",    /* '(' */              "",    /* ')' */
};

/* Линеаризованная матрица операторного предшествования */
static f[] = { 0, 4, 2, 4, 0, 4, };
static g[] = { 0, 5, 1, 3, 5, 0, };

main() {
 register c, d;
  stinit(); stpush(EF);
  do {
    c = yylex();
    while ( f[sttop()] > 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); }

Задачи для решения на ЭВМ:
1. Переделайте компилятор так, чтобы он не  допускал  ошибочных
   (т.е. не порождаемых грамматикой) цепочек.
2. Добавьте в компилятор операцию возведения в степень  (право-
   ассоциативная операция "^" с наивысшим приоритетом).
3. Переделайте компилятор формул в интерпретатор.
4. Добавьте в компилятор операцию "унарный минус".