Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991 Материал к лекции 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); } Задачи для решения на ЭВМ: 1. Переделайте компилятор так, чтобы он не допускал ошибочных (т.е. не порождаемых грамматикой) цепочек. 2. Добавьте в компилятор операцию возведения в степень (право¦ ассоциативная операция "^" с наивысшим приоритетом). 3. Переделайте компилятор формул в интерпретатор. 4. Добавьте в компилятор операцию "унарный минус". - конец материала к лекции 5 -