Лабораторная работа №3
Синтаксический анализ предложений для грамматик с предшествованием

   При восходящем грамматическом разборе правила подстановки применяются для свертки (приведения) всего исходного предложения к начальному символу грамматики. С этой целью в приводимой строке последовательно отыскивается основа - самая левая часть строки, которая по одному из правил подстановки может быть заменена на нетерминал, и выполняется эта замена.

   Между любыми двумя соседними символами приводимой строки p и q могут существовать три отношения:
p<q,если q - самый левый символ некоторой основы:
pq...
└основа─>
p>q,если p - самый правый символ некоторой основы:
...pq
<─основа┘
p=q,если символы принадлежат одной основе:
...pq...
└─основа─┘

   Отношения <,>, = называются отношениями предшествования.

   Пусть p, q - любые символы (терминальные или нетерминальные), U, C, D - нетерминальные символы, x,y,z,w - любые строки, возможно пустые. Грамматика называется грамматикой с простым предшествованием, если для каждой упорядоченной пары символов выполняется не более чем одно из трех отношений предшествования:
p=q,если существует правило U -> xpqy;
p<q,если существует правило U -> xpDy и вывод D =>+ qz;
p>q,если существует правило U -> xCqy и вывод C =>+ zp или правило U -> xCDy и выводы C =>+ zp, D =>+ qw.

   Для определения отношений предшествования предварительно для каждого нетерминального символа U находятся два множества:
L(U) - множество самых левых символов в разложениях U, т.е. множество таких символов q, что существует вывод U =>+ qz;
R(U) - множество самых правых символов в разложениях U, т.е. множество таких символов p, что существует вывод U =>+ zp.

   Построение множеств L(U), R(U) состоит из следующих шагов:

  1. для каждого правила вида U -> z, в L(U) заносится самый левый символ правой части, в R(U) - самый правый символ;
  2. если L(U) содержит нетерминальные символы U1, U2..., то L(U) дополняется символами, входящими в L(U1), L(U2)... и не входящими в L(U). Аналогично дополняется R(U);
  3. шаг 2 повторяется, пока L(U), R(U) не перестанут изменяться.
Пример:
Z -> bMb
M -> (N | a
N -> Ma)		 Грамматика определяет цепочки символов bab, b(aa)b, b((aa)a)b, b(((aa)a)a)b и т.д.
L(U), R(U) после первого шагаокончательно
UL(U)R(U)
Z
M
N		b
(, a
M		b
N, a
)
UL(U)R(U)
Z
M
N		b
(, a
M, (, a		b
N, a, )
)

   Вывод отношений между символами:

  1. для проверки p=q в правилах отыскиваются сочетания pq;
  2. для проверки p<q в правилах отыскиваются сочетания pU и проверяется, что q принадлежит L(U);
  3. для проверки p>q в правилах отыскиваются сочетания Uq и проверяется, что p принадлежит R(U). Кроме этого, для всех нетерминалов C, таких, что p принадлежит R(C) отыскиваются сочетания CD и проверяется, что q принадлежит L(D).
  Отношения между символами для грамматики из примера:
ZbMNa()
Z
b
M
N
a
(
)		    
 
=
>
>
 
>		  
=
 
 
 
<
 		  
 
 
 
 
=
 		  
<
=
>
>
<
>		  
<
 
 
 
<
 		  
 
 
 
=
 
 
Например:
  1. b=M, т.к. существует правило Z -> bMb;
  2. (<a, т.к. существует правило M -> (N и a принадлежит L(N);
  3. N>b, т.к. cуществует правило Z -> bMb и N принадлежит R(M).

   Разбор предложений в грамматиках с простым предшествованием ведется с использованием стека терминальных и нетерминальных символов.
   Пусть необходимо выполнить грамматический разбор для некоторой входной строки терминальных символов t(1)...t(n). Строка ограничивается с двух сторон терминальным символом ┴, при этом считается, что для любого терминала t(j) ┴<t(j) и t(j)>┴. Формируется стек S, элементы которого s(i) - терминальные и нетерминальные символы. В стек заносится символ ┴ (s(1)=┴). Далее, на каждом промежуточном этапе действия определяются состоянием стека - s(1)...s(k) и остатком входного предложения - t(j)...t(n)┴. Проверяется отношение между верхним элементом стека s(k) и очередным символом строки t(j). Если отношения нет, то входная строка некорректна. Если s(k)<t(j) или s(k)=t(j), то t(j) заносится в стек. Если s(k)>t(j), то отыскивается множество символов в вершине стека, удовлетворяющих отношению: s(i-1)<s(i)=s(i+1)=...=s(k)>t(j). Элементы s(i)...s(k) принадлежат одной основе и могут быть свернуты по некоторому правилу грамматики: U -> s(i)...s(k). Выполняется свертка: отыскивается это правило, символы s(i)...s(k) удаляются из стека, а U - заносится. Процесс повторяется: символ U, как верхний элемент стека, сравнивается с t(j) и т.д. По концу разбора правильного предложения в стеке должны остаться символы ┴Z, где Z - начальный символ грамматики.

   Пример разбора предложения ┴b((aa)a)b┴
СтекОстатокОтношениеОсноваПравило
┴
┴b
┴b(
┴b((
┴b((a
┴b((M
┴b((Ma
┴b((Ma)
┴b((N
┴b(M
┴b(Ma
┴b(Ma)
┴b(N
┴bM
┴bMb
┴Z 		b((aa)a))b┴
((aa)a)b┴
(aa)a)b┴
aa)a)b┴
a)a)b┴
a)a)b┴
)a)b┴
a)b┴
a)b┴
a)b┴
)b┴
b┴
b┴
b┴
┴
┴ 		┴ < b
b < (
( < (
( < a
a > a
M = a
a = )
) > a
N > a
M = a
a = )
) > b
N > b
M = b
b >┴
конец 		 
 
 
 
( < a > a
 
 
( < M=a=) > a
( < (=N > a
 
 
( < M=a=) > b
b < (=N > b
 
┴ < b=M=b > ┴
  		 
 
 
 
M -> a
 
 
N -> Ma)
M -> (N
 
 
N -> Ma)
M -> (N
 
Z -> bMb
 

   Операторной грамматикой называется грамматика, не содержащая правил вида A -> xBCy, где x, y - произвольные строки, B, C - нетерминалы.
   Пусть U, C, D - нетерминалы. Грамматикой с операторным предшествованием называется операторная грамматика, в которой между двумя любыми терминальными символами p, q выполняется не более, чем одно из следующих отношений предшествования:
p=q,если существует правило U -> xpqy или U -> xpСqy;
p<q,если существует правило U -> xpCy и вывод C=>+qz или C=>+Dqz;
p>q,если существует правило U -> xCqy и вывод C=>+zp или C=>+zpD.
   Для определения отношений строятся множества:
LT(U) - множество левых терминалов в разложениях U, т.е. множество таких терминалов q, что существует вывод U=>+qz или U=>+Dqz;
RT(U) - множество правых терминалов в разложениях U, т.е. множество таких терминалов p, что существует вывод U=>+zp или U=>+zpD.
   С этой целью:

  1. строятся множества левых и правых символов - L(U), R(U) (см.тут);
  2. для правил вида U->qz, U->Cqz терминал q заносится в LT(U); для правил вида U->zp, U->zpC терминал p заносится в RT(U);
  3. для каждого U', принадлежащего L(U), LT(U) дополняется терминалами из LT(U'). Аналогично дополняется RT(U).

   Пример:
S -> T | S+T
T -> ид | T*ид		 Грамматика для выражений, состоящих из идентификаторов и знаков +, *.
L(U), R(U) после первого шага окончательно
UL(U)R(U)
S
T		T, S
ид, T		T
ид
UL(U)R(U)
S
T		T, S, ид
ид, T		T, ид
ид
LT(U), RT(U) после второго шага окончательно
ULT(U)RT(U)
S
T		+
ид, *		+
ид
ULT(U)RT(U)
S
T		+, ид, *
ид, *		+, ид
ид

   Вывод отношений между терминалами:
p=qв правилах отыскиваются сочетания pq и pCq;
p<qдля сочетаний pC проверяется, что q принадлежит LT(C);
p>qдля сочетаний Cq проверяется, что p принадлежит RT(C).
   Для примера
+*ид
+
*
ид		>
 
>		<
 
>		<
=
 
 Например:
  1. *=ид, т.к. существует правило T->T*ид;
  2. +<*, т.к. существует правило S->S+T и принадлежит LT(T);
  3. +>+, т.к. существует правило S->S+T и + принадлежит RT(S).

   Разбор в грамматиках с операторным предшествованием выполняется так же, как в грамматиках с простым предшествованием, но отношения проверяются только между терминалами. Пусть стек содержит символы s(1)...s(k), t(j)...t(n)┴ - остаток входной строки, p=s(m) - верхний терминал стека (m<=k). Если p=t(j) или p<t(j), то t(j) заносится в стек. Если p>t(j), то отыскивается множество терминалов в вершине стека, удовлетворяющих отношениям s(a)<s(b)=s(c)=...=s(m)>t(j). Тогда все элементы стека от s(a+1) до s(k) составляют основу и могут быть свернуты в некоторый нетерминал U.

   Пример разбора предложения ┴a+b*c┴
СтекОстатокОтношениеВыбор основыОсноваПравило
┴
┴a
┴T
┴T+
┴T+b
┴T+T
┴T+T*
┴T+T*C
┴T+T
┴S 		a+b*c┴
+b*c┴
+b*c┴
b*c┴
*c┴
*c┴
c┴
┴
┴
┴
 ┴ < a
a > +
┴ < +
+ < b
b > *
+ < *
* = c
c > ┴
+ > ┴
конец 		 
┴ < a > +
 
 
+ < b > *
 
 
+ < *=c > ┴
┴ < + > ┴
  		 
a
 
 
b
 
 
T*c
T+T
  		 
T->ид
 
 
T->ид
 
 
T->T*ид
S->T, S->S+T