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

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