Грамматика предшествования

Для грамматик предшествования можно построить восходящий распознаватель на основе алгоритма перенос / свертка. Данный метод будет сводиться к основе, которая соответствует правой части грамматики.

При этом между символами устанавливается некоторое отношение называемое отношение предшествования. Работает этот восходящий распознаватель как LL грамматика.

Будут рассмотрены два вида грамматик: простое предшествование и операторного предшествования.

Грамматика простого предшествования называется грамматика без онулирующих правил для которой выполняются следующие условия:

1. Для каждой упорядоченной пары терминальных и нетерминальных может быть установлено одно из трех отношений предшествования.
   <. – предшествует;
   .> - следует;
   =. - составляет основу;
2. Различные правила грамматики не могут содержать одинаковую часть.

Для построения отношения предшествования используется специальный алгоритм, который требует нахождение для каждого правила грамматики множество крайних левых и крайних правых символов:

L(I) – для крайних левых
R(I) – для крайних правых

Для каждого нетерминального символа A ищем все правила, содержащие A с левой части. Множество L(A).

Если множество L(A) содержит нетерминальные символы: A1, A2, … , An. То множество L(A) необходимо дополнить символами, входящими в множество: L(A1), L(A1), … , L(An).

Шаг 2 повторяется пока множество не перестает выполняться.

A<.B - перенос
A.>B - свертка
A=.B – перенос.

Для любых подряд идущих символов правой части грамматики справедливо следующее:

• На пересечения строки А и столбца В ставим знак составление основы (=.).
• На пересечении строки А и столбца В(B) ставим знак предшествует(<.).
• На пересечении строк R(А) и столбцов В,L(B) ставим знак следует (.>).
• На пересечении строк начала и столбцов L(I) ставим знак предшествует(<.).
• На пересечении строк R(I)  и столбцов соответствующих конец строки ставим знак следует(.>).

Пример:

I -> TR | T
R -> +T | -T | +TR | -TR
T -> a|b

1. Построим крайние левые и правые:
   L(I) = { T}
   L(R) = { +,-}
   L(T) = { a,b}
   R(I) = { R,T}
   R(R) = {T,R}
   R(T) = {a,b}
2. Дополняем к T входящие a,b:
   L(I) = { T,a,b}
   L(R) = { +,-}
   L(T) = { a,b}
   R(I) = { R,T,a,b}
   R(R) = {T,R, a,b}
   R(T) = {a,b}

Процесс распознавания работает как LR анализатор:

Пример:

I -> TS;
T -> int | char
S -> *BR | BR | B
R -> , S
B -> i | j

Построим крайние левые и правые:

L(I) = { T, int ,char}
L(T) = {int, char}
L(S) = {*, B, i,j}
L(R) = {,}
L(B) = {i,j}
R(I) = {;}
R(T) = {int, char}
R(S) = {R,B, i, j,S}
R(R) = {S, R, B, i,j}
R(B) = {I,j}

Строим таблицы:

В таблице имеет два предшествования. Это на пересечении ; и S.

Следовательно правило нужно переписать:

I -> TS;
T -> int | char
S -> ,*BR | ,BR | ,B
B -> i | j

Тогда буква S должна исчезнуть.

R(R) = {R, B, i,j}