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).  Терминалами  новой
грамматики будут терминалы и нетерминалы  исходной  грамматики,
нетерминалы новой грамматики обозначим <L(A)>,... - их значени-
ями будут левые контексты нетерминалов исходной грамматики. Ес-
ли S - начальный символ исходной грамматики, то грамматика  ле-
вых контекстов будет содержать правило
    <L(S)> : e      - левый контекст S содержит пустую цепочку
Для каждого правила исходной грамматики, например,
    A : B C d E
добавим в новую грамматику правила:
    <L(B)> : <L(A)>           - L(B) включает L(A)
    <L(C)> : <L(A)> B         - L(C) включает L(A) B
    <L(E)> : <L(A)> 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