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

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

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

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