Delphi World - Основы компиляции - Лекция 5
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Основы компиляции - Лекция 5

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

Материал к лекции 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 -

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования