Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991 Материал к лекции 6. LR(k)-грамматики. SLR(1), LALR(1) - грамматики. Если в процессе LR-разбора принять детерминированное решение о сдвиге/свертке удается, рассматривая только цепочку x и пер¦ вые k символов непросмотренной части входной цепочки u (эти k символов называют аванцепочкой), говорят, что грамматика обла¦ дает LR(k)-свойством. -S-- / \ /-x¬ \ --w-+--u-- Различие между LL(k)- и LR(k)-грамматиками в терминах дерева вывода: -S- / ¦ \ / A \ / / \ \ -w-+-v-+-u- В случае LL(k)-грамматик однозначно определить правило, приме¦ ненное к A, можно по w и первым k символам vu, а в случае LR(k)-грамматик - по w,v и первым k символам u. Это нестрогое рассуждение показывает, что LL(k)-языки < LR(k)-языки (опро¦ вергните его для k=0). LR(0)-грамматики Рассмотрим вначале наиболее простые грамматики этого класса - LR(0). При разборе строки LR(0)-языка можно вообще не исполь¦ зовать аванцепочку - выбор между сдвигом и сверткой делается на основании цепочки x (см.картинку). Так как в процессе разбора она изменяется только с правого конца, ее называют стеком. Бу¦ дем считать, что в грамматике нет бесполезных символов и на¦ чальный символ не встречается в правых частях правил - тогда свертка к начальному символу сигнализирует об успешном заверше¦ нии разбора. Попробуем описать множество цепочек из терминалов и нетерминалов, появляющихся в стеке в процессе всех LR-разбо¦ ров (другими словами - всех правых выводов из грамматики). Определим следующие множества: L(A:v) - левый контекст правила A:v - множество состояний стека, непосредственно перед сверткой v в A в ходе всех успеш¦ ных LR-разборов. Очевидно, каждая цепочка из L(A:v) кончается на v. Если у всех таких цепочек отрезать хвост v, то получится множество цепочек, встречающихся слева от A в процессе всех ус¦ пешных правых выводов. Обозначим это множество L(A) - левый контекст нетерминала A. Упражнение: показать, что данное определение корректно, т.е. множество L(A) не зави¦ сит от выбора правила A:v. Построим грамматику для множества L(A). Терминалами новой грамматики будут терминалы и нетерминалы исходной грамматики, нетерминалы новой грамматики обозначим ,... - их значени¦ ями будут левые контексты нетерминалов исходной грамматики. Ес¦ ли S - начальный символ исходной грамматики, то грамматика ле¦ вых контекстов будет содержать правило : e - левый контекст S содержит пустую цепочку Для каждого правила исходной грамматики, например, A : B C d E добавим в новую грамматику правила: : - L(B) включает L(A) : B - L(C) включает L(A) B : B C d - L(E) включает L(A) B C d Упражнение: показать, что L(A) не содержит других цепочек, кро¦ ме выводимых из грамматики. Полученная грамматика имеет специальный вид (такие граммати¦ ки называются леволинейными), следовательно, множества левых контекстов - регулярны. Из этого следует, что принадлежность цепочки левому контексту какого-либо нетерминала можно вычис¦ лять индуктивно с помощью конечного автомата, просматривая це¦ почку слева направо. Опишем этот процесс конструктивно. Назовем LR(0)-ситуацией правило грамматики с одной отмечен¦ ной позицией между символами правой части правила. Например, для грамматики S:A ; A:aAA ; A:b существуют следующие LR(0)-си¦ туации: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (позиция обозначена символом подчеркивания). Будем говорить, что цепочка x согласована с ситуацией А:b_c, если x=ab и a принадлежит L(A). (Другими словами, LR-вывод мо¦ жет быть продолжен x_... = ab_... :: abc_... :: aA_... :: S_ .) В этих терминах L(A:b) - множество цепочек, согласованных с си¦ туацией A:b_, L(A) - цепочки, согласованные с ситуацией A:_b, для любого правила A:b. Пусть V(u) - множество ситуаций, согласованных с u. Покажем, что функция V - индуктивна. Если в множество V(u) входит ситуация A:b_cd, то ситуация A:bc_d принадлежит V(uc). (c - терминал или нетерминал; b, d - последовательности (может быть пустые) терминалов и нетермина¦ лов). Других ситуаций вида A:b_d, с непустым b в V(uc) нет. Ос¦ талось добавить в V(uc) ситуации вида C:_..., для каждого не¦ терминала C, левый контекст которого содержит uc. Если ситуация A:..._C... (C-нетерминал) принадлежит множеству V(uc), то uc принадлежит L(C) и V(uc) включает в себя ситуации вида C:_... для всех C-правил грамматики. Упражнение: показать, что других ситуаций V(uc) не содержит. V(e) содержит ситуации S:_... (S-начальный символ), а также ситуации A:_..., если нетерминал A встречается непосредственно после _ в ситуациях, уже включенных в V(e). Пример: построим функцию V для грамматики S:A; A:aAA; A:b. 0 V(e) = { S:_A; A:_aAA, A:_b } 1 V(A) = { S:A_ } 2 V(a) = { A:a_AA; A:_aAA, A:_b } V(aa)=V(a); V(ab)=V(b); 3 V(b) = { A:b_ } 4 V(aA) = { A:aA_A; A:_aAA, A:_b } V(aAa)=V(a);V(aAb)=V(b); 5 V(aAA) = { A:aAA_ } Наконец, мы готовы дать определение LR(0)-грамматики. Пусть u - содержимое стека в процессе LR-разбора, V(u)-множество LR(0) ситуаций, согласованных с u. Если V(u) содержит ситуацию вида А:x_ (x-последовательность терминалов и нетерминалов), то u принадлежит L(A:x) и допустима свертка x в A. Если V(u) со¦ держит ситуацию A:..._a... (а-терминал), то допустим сдвиг. Го¦ ворят о конфликте сдвиг-свертка, если для одной цепочки u до¦ пустимы и сдвиг, и свертка. Говорят о конфликте свертка- свертка, если допустимы свертки по различным правилам. Грамматика называется LR(0), если для всех состояний стека в процессе LR-вывода нет конфликтов сдвиг-свертка или свертка-свертка. Рассмотренная выше грамматика является LR(0)-грамматикой. Ее функция V принимает 6 различных значений (вычисляется конечным автоматом с 6 состояниями). В состояниях 0,2,4 возможен только сдвиг, в состоянии 3 - свертка по правилу A:b, в состоянии 5 - свертка A:aAA, в состоянии 1 - свертка S:A - т.е. успешное за¦ вершение разбора. Остается показать, как можно построить парсер, разбирающий предложения LR(0)-языка. Чтобы не вычислять значение функции V заново для каждого нового состояния стека, будем хранить в сте¦ ке вместе с каждым символом xi значение V на цепочке (x0...xi). стек.сделать пустым стек.добавить ( '#', начальное состояние ) цикл . выбор из V ( стек.вершина.состояние ).действие . . "сдвиг" => . . прочитать очередной символ в ( новый символ ) . . "свертка" => . . удалить правую часть правила из стека . . новый символ := левая часть правила . . "успех" => . . стоп( "успех" ) . конец выбора . старое состояние := V ( стек.вершина.состояние ) . новое состояние := старое состояние . переход [новый символ] . если новое состояние = "Ошибка" то стоп( "ошибка" ) кесли . стек.добавить ( новый символ, новое состояние ) конец цикла Таблицы LR(0)-парсера для грамматики 1) S:A; 2) A:aAA; 3) A:b. --T------T-------------T----------------------¬ ¦ ¦ Пре¦ ¦ Действие ¦ Переход ¦ ¦ ¦ фикс ¦ ¦ A a b ¦ +-+------+-------------+----------------------+ ¦0¦ e ¦ сдвиг ¦ 1 2 3 ¦ ¦1¦ A ¦ успех ¦ Ошибка Ошибка Ошибка ¦ ¦2¦ a ¦ сдвиг ¦ 4 2 3 ¦ ¦3¦ b ¦ свертка 3,А ¦ Ошибка Ошибка Ошибка ¦ ¦4¦ aA ¦ сдвиг ¦ 5 2 3 ¦ ¦5¦ aAA ¦ свертка 2,А ¦ Ошибка Ошибка Ошибка ¦ L-+------+-------------+----------------------- LR(k)-грамматики Для выбора между сдвигом или сверткой в LR(0) разборе ис¦ пользуется только состояние стека. В LR(k) разборе учитывается также k-первых символов непросмотренной части входной цепочки (так называемая аванцепочка). Для обоснования метода следует аккуратно повторить рассуждения предыдущего параграфа, внеся изменения в определения. Будем включать в левый контекст правила также аванцепочку. Если в правом выводе применяется вывод wAu : wvu, то пара {wv,FIRSTk(u)} принадлежит Lk(A:v), а пара {w,FIRSTk(u)} - Lk(A). Множество левых контекстов, как и в случае LR(0), можно вычислять с помощью индукции по левой цепочке. Назовем LR(k)-ситуацией пару: правило грамматики с отмеченной позицией и аванцепочку длины не более k. Отделять правило от аванцепочки будем вертикальной чертой. Будем говорить, что цепочка x согласована с ситуацией А:b_c|t если существует LR-вывод: x_yz = ab_yz :: abc_z :: aA_z :: S_, и FIRSTk(z)=t. Правила индуктивного вычисления множества состояний Vk следующие: Vk(e) содержит ситуации S:_a|e для всех правил S:a, где S-начальный символ. Для каждой ситуации А:_Ba|u из Vk(e), каж¦ дого правила B:b и цепочки x, принадлежащей FIRSTk(au), надо добавить в Vk(e) ситуацию B:_b|x. Если в Vк(w) входит ситуация A:b_cd|u, то ситуация A:bc_d|u будет принадлежать Vk(wc). Для каждой ситуации А:b_Cd|u из Vk(wc), каждого правила C:f и цепочки x, принадлежащей FIRSTk(du) надо добавить в Vk(wc) ситуацию C:_f|x. Пример: построим функцию V1 для грамматики S:A; A:AaAb|e. 0 V1(e) = { S:_A|e; A:_AaAb|e,a, A:_|e,a } 1 V1(A) = { S:A_|e, A:A_aAb|e,a } 2 V1(Aa) = { A:Aa_Ab|e,a; A:_AaAb|a,b, A:_|a,b } 3 V1(AaA) = { A:AaA_b|e,a, A:A_aAb|a,b } 4 V1(AaAa) = { A:Aa_Ab|a,b; A:_AaAb|a,b, A:_|a,b } 5 V1(AaAb) = { A:AaAb_|e,a } 6 V1(AaAaA) = { A:AaA_b|a,b A:A_aAb|a,b } V1(AaAaAa)=V1(AaAa) 7 V1(AaAaAb)= { A:AaAb_|a,b } ( A:_AaAb|e,a - сокращенная запись двух LR(1)-ситуаций: A:_AaAb|e и A:_AaAb|а ) Используем построенные множества LR(k)-состояний для разре¦ шения вопроса сдвиг-свертка. Пусть u - содержимое стека, а x - аванцепочка. Очевидно, что свертка по правилу A:b может быть проведена, если Vk(u) содержит ситуацию A:b_|x. Решение вопроса о допустимости сдвига требует аккуратности, если в грамматике имеются e-правила. В ситуации A:b_c|t (c не пусто) сдвиг возмо¦ жен, если c начинается с терминала и x принадлежит FIRSTk(ct). Неформально говоря, можно занести в стек самый левый символ правой части правила, подготавливая последующую свертку. Если c начинается с нетерминала (ситуация имеет вид A:b_Cd|t), то за¦ нести в стек символ, подготавливая свертку в C, можно только в случае, если C не порождает пустую цепочку. Например, в состо¦ янии V(e)={ S:_A|e; A:_AaAb|e,a, A:_|e,a } нет допустимых сдви¦ гов, т.к. при выводе из A терминальных цепочек на некотором ша¦ ге требуется применить правило A:e к нетерминалу A, находящему¦ ся на левом конце цепочки. Определим множество EFFk(x), состоящее из всех элементов множества FIRSTk(x), при выводе которых нетерминал на левом конце x (если он есть) не заменяется на пустую цепочку. В этих терминах сдвиг допустим, если в множестве Vk(u) есть ситуация А:b_c|t, c не пусто и x принадлежит EFFk(ct). Грамматика называется LR(k)-грамматикой, если ни одно LR(k) состояние не содержит двух ситуаций A:b_|u и B:c_d|v, таких что u принадлежит EFFk(dv). Такая пара соответствует конфликту свертка-свертка, если d пусто, и конфликту сдвиг-свертка, если d не пусто. LR(k)-парсер устроен аналогично LR(0). Действие из множества {сдвиг, свертка, успех, ошибка}, выполняемое на очередном шаге LR-разбора, есть функция от состояния стека Vk(u) и аванцепочки x: сдвиг, если A:b_c|t содержится в Vk(u), c!=e, x из EFF(ct); свертка, если A:a_|x содержится в Vk(u); успех, если S:A|e содержится в Vk(u); ошибка в остальных случаях. Таблицы LR(1)-парсера для грамматики S:A; A:AaAb|e. --T-------T----------------------T---------------------¬ ¦ ¦Префикс¦ Действие ¦ Переход ¦ ¦ ¦ ¦ a b e ¦ a b А ¦ +-+-------+----------------------+---------------------+ ¦0¦ e ¦ Св.0,А Ошибка Св.0,А ¦ Ошибка Ошибка 1 ¦ ¦1¦ A ¦ Сдвиг Ошибка Успех ¦ 2 Ошибка Ошибка¦ ¦2¦ Aa ¦ Св.0,А Св.0,А Ошибка ¦ Ошибка Ошибка 3 ¦ ¦3¦ AaA ¦ Сдвиг Сдвиг Ошибка ¦ 4 5 Ошибка¦ ¦4¦ AaAa ¦ Св.0,А Св.0,А Ошибка ¦ Ошибка Ошибка 6 ¦ ¦5¦ AaAb ¦ Св.4,А Ошибка Св.4,А ¦ Ошибка Ошибка Ошибка¦ ¦6¦ AaAaA ¦ Сдвиг Сдвиг Ошибка ¦ 4 7 Ошибка¦ ¦7¦ AaAaAb¦ Св.4,А Св.4,А Ошибка ¦ Ошибка Ошибка Ошибка¦ L-+-------+----------------------+---------------------- Упражнение: запрограммируйте интерпретатор LR(k)-таблиц. На практике LR(k)-грамматики при k>1 не применяются. На это имеются две причины. Первая: очень большое число LR(k) состо¦ яний. Вторая: для любого языка, определяемого LR(k)-граммати¦ кой, существует LR(1)-грамматика; более того, для любого детер¦ минированного КС-языка существует LR(1)-грамматика. Число LR(1)-состояний для практически интересных грамматик также весьма велико. LR(0) свойством такие грамматики обладают редко. На практике чаще всего используются промежуточные между LR(0) и LR(1) методы, известные под названиями SLR(1) и LALR(1). SLR(1) и LALR(1) грамматики. В основе этих двух методов лежит одна и та же идея. Построим множество канонических LR(0)-состояний грамматики. Если это множество не содержит конфликтов, то можно применить LR(0)-пар¦ сер. Иначе попытаемся разрешить возникшие конфликты, рассматри¦ вая односимвольную аванцепочку. Другими словами, попробуем построить LR(1) парсер с множеством LR(0)-состояний. В SLR(1) грамматиках (Simple LR(1) - простых LR(1)-граммати¦ ках) для разрешения конфликтов используется множество FOLLOW(X) - множество терминалов, встречающихся после X. Если в состоянии имеется ситуация A:b_, свертка допускается, если только аванце¦ почка принадлежит FOLLOW(A). Грамматика является SLR(1)-грамматикой, если для двух любых LR(0) ситуаций из одного состояния A:a_b и B:c_d выполняется одно из следующих условий: - b!=e, d!=e (конфликта нет, требуется сдвиг); - b=d=e и FOLLOW(A) не пересекается с FOLLOW(B) (конфликт "свертка/свертка" может быть устранен с учетом аванце¦ почки); - b=e, d<>e и FOLLOW(A) не пересекается с EFF(tFOLLOW(B)) (конфликт "сдвиг/свертка" может быть устранен с учетом аванцепочки). Построим LR(0)-состояния для грамматики арифметических фор¦ мул: S:E; E:E+T|T; T:T*F|F; F:(E)|a. 0 V(e) ={ S:_E; E:_E+T, E:_T, T:_T*F, T:_F, F_a, F:_(E) } 1 V(E) ={ S:E_, E:E_+T } 2 V(T) ={ E:T_, T:T_*F, 3 V(F) ={ T:F_ } 4 V(a) ={ F:a_ } 5 V(() ={ F:(_E); E:_E+T, E:_T, T:_T*F, T:_F, F_a, F:_(E) } 6 V(E+) ={ E:E+_T; T:_T*F, T:_F, F_a, F:_(E) } 7 V(T*) ={ T:T*_F; F:_a, F:_(E) } 8 V((E) ={ F:(E_), E:E_+T } (T=T; (F=F; (a=a; ((=( 9 V(E+T)={ E:E+T_, T:T_*F } E+F=F; E+a=a; E+(=( 10 V(T*F)={ T:T*F_ } T*a=a; T*(=( 11 V((E))={ F:(E)_ } (Е+=Е+; Е+Т*=Т* LR(0)-конфликты возникают в состояниях 1,2,9, но 1: FOLLOW(S) = {е}, FIRST(+T) = {+} 2: FOLLOW(E) = {+,),e} FIRST(*F) = {*} 9: FOLLOW(E) = {+,),e} FIRST(*F) = {*}, следовательно, конфликты разрешаются с использованием SLR(1) техники и грамматика является SLR(1)-грамматикой. Таблицы SLR(1)-парсера для грамматики арифметических формул ---T-------------------------T--------------------------------¬ ¦ ¦ Действие ¦ Переход ¦ ¦ ¦ e + * а ( ) ¦ + * а ( ) E T F ¦ +--+-------------------------+--------------------------------+ ¦0 ¦ Ош Ош Ош Сдв Сдв Ош ¦ Ош Ош 4 5 Ош 1 2 3 ¦ ¦1 ¦ Усп Сдв Ош Ош Ош Ош ¦ 6 Ош Ош Ош Ош Ош Ош Ош ¦ ¦2 ¦ 1,E 1,E Сдв Ош Ош 1,E ¦ Ош 7 Ош Ош Ош Ош Ош Ош ¦ ¦3 ¦ 1,T 1,T 1,T Ош Ош 1,T ¦ Ош Ош Ош Ош Ош Ош Ош Ош ¦ ¦4 ¦ 1,F 1,F 1,F Ош Ош 1,F ¦ Ош Ош Ош Ош Ош Ош Ош Ош ¦ ¦5 ¦ Ош Ош Ош Сдв Сдв Ош ¦ Ош Ош 4 5 Ош 8 2 3 ¦ ¦6 ¦ Ош Ош Ош Сдв Сдв Ош ¦ Ош Ош 4 5 Ош Ош 9 3 ¦ ¦7 ¦ Ош Ош Ош Сдв Сдв Ош ¦ Ош Ош 4 5 Ош Ош Ош 10 ¦ ¦8 ¦ Ош Сдв Ош Ош Ош Сдв ¦ 6 Ош Ош Ош 11 Ош Ош Ош ¦ ¦9 ¦ 3,Е 3,Е Ош Ош Ош 3,Е ¦ Ош 7 Ош Ош Ош Ош Ош Ош ¦ ¦10¦ 3,Т 3,Т 3,Т Ош Ош 3,Т ¦ Ош Ош Ош Ош Ош Ош Ош Ош ¦ ¦11¦ 3,F 3,F 3,F Ош Ош 3,F ¦ Ош Ош Ош Ош Ош Ош Ош Ош ¦ L--+-------------------------+--------------------------------- LALR(1)-метод (Look Ahead - заглядывание вперед) заключается в следущем. Введем на множестве LR(1)-ситуаций отношение экви¦ валентности: будем считать две ситуации эквивалентными, если они различаются только аванцепочками. Например, ситуации A:Aa_Ab|e и A:Aa_Ab|a эквивалентны. Построим каноническое мно¦ жество LR(1)-состояний и объединим состояния, состоящие из мно¦ жества эквивалентных ситуаций. Например, LR(1) состояния 2 и 4 грамматики S:A; A:AaAb|e эк¦ вивалентны: 2 V1(Aa) = { A:Aa_Ab|e,a; A:_AaAb|a,b, A:_|a,b } 4 V1(AaAa) = { A:Aa_Ab|a,b; A:_AaAb|a,b, A:_|a,b } и могут быть объединены в одно состояние 2+4 V1(Aa) = { A:Aa_Ab|e,a,b; A:_AaAb|a,b, A:_|a,b } Также эквивалентны состояния 3,6 и 5,7 этой грамматики. Если полученное множество состояний не содержит LR(1) конфликтов, и, следовательно, позволяет построить LR(1)-парсер, то говорят, что грамматика обладает свойством LALR(1). Например, грамматика S:A; A:AaAb|e является LALR(1), Таблицы LALR(1)-парсера для грамматики S:A; A:AaAb|e. ----T-------T----------------------T---------------------¬ ¦ ¦Префикс¦ Действие ¦ Переход ¦ ¦ ¦ ¦ a b e ¦ a b А ¦ +---+-------+----------------------+---------------------+ ¦ 0¦ e ¦ Св.0,А Ошибка Св.0,А ¦ Ошибка Ошибка 1 ¦ ¦ 1¦ A ¦ Сдвиг Ошибка Успех ¦ 2 Ошибка Ошибка¦ ¦2+4¦ Aa ¦ Св.0,А Св.0,А Ошибка ¦ Ошибка Ошибка 3+6 ¦ ¦3+6¦ AaA ¦ Сдвиг Сдвиг Ошибка ¦ 4 5+7 Ошибка¦ ¦5+7¦ AaAb ¦ Св.4,А Св.4,А Св.4,А ¦ Ошибка Ошибка Ошибка¦ L---+-------+----------------------+---------------------- Заметим, что при слиянии канонических LR(1)-состояний, раз¦ личающихся только аванцепочками, получается множество канони¦ ческих LR(0)-состояний, для каждой ситуации которого вычислено множество допустимых аванцепочек (Докажите!). Следовательно, SLR(1) и LALR(1) методы при успешном применении дают одинаковые таблицы парсера. Метод LALR(1) применим к более широкому классу грамматик, чем SLR(1). Это объясняется тем, что отношение FOLLOW(A), применяемое при вычислении допустимых аванцепочек в SLR(1)-методе не использует всю доступную информацию - оно не зависит от левого контекста правила A:... Действительно, су¦ ществуют LALR(1)- грамматики, не принадлежащие классу SLR(1). Упражнение: покажите, что грамматика является LALR(1), но не SLR(1): S:L=R|R; L:*R|a; R:L Упражнение: к какому типу принадлежат следующие грамматики? 1) S:Aa|dAb|cb|dca; A:c; 2) S:Aa|dAb|Bb|dBa; A:c; B:c 3) S:Aa|dAb|Bb|dBa|c; A:c; B:c - конец материала к лекции 6 -