Описание алгоритма

1. Функция переноса f зависит только от верхнего символа магазина и самого левого необработанного символа входной це­почки. Поэтому f определяется на множестве (V  {  })  (T  {  }) ( за исключением правила с), которое имеет приоритет над правила­ми а) и b), когда Х = S и a =  ):

1. f(X, а) = ПЕРЕНОС, если Х <• а или Х  а ;

2. f(X, а) = СВЕРТКА, если Х •> а ;

3. f(S, ) = ДОПУСК;

4. f(X, а) = ОШИБКА в остальных случаях.

2) Функция свертки g зависит от верхней части магазинной цепочки, включающей основу и еще один символ ниже нее. Необ­работанная часть входной цепочки на g не влияет, поэтому g задается только на (V  {  })^*:

1. g(X_k+1X_kX_k-1 … X₁, ) = i, если X_k+1 <• X_k, X_j+1  X_j для k>j1 и

A  Х_kХ_k-₁ ... Х₁ – правило вывода с номером i. Заметим, что функция g определяется только тогда, когда Х₁ •> a – текущий входной символ;

b) g(, ) = ОШИБКА в остальных случаях.

Пример 4.9. Построить алгоритм разбора типа “перенос-свертка” для грамматики простого предшествования с правила­ми вывода:

(1) S  aSSb

(2) S  c

Матрица простого предшествования для этой грамматики приведе­на на рис. 4.31.

Функцию переносов f строим непосредственно по матрице простого предшествования: f(X, a) = ПЕРЕНОС, если Х <•а или Х  а, f(X, a) = СВЕРТКА, если Х •>а. После добавления строки, соответствующей правилу 1,с), получим функцию переносов f, приведенную на рис. 4.32.

Для построения функции свертки рас­смотрим все возможные комбинации основ и символа, который может располагаться в магазине под основой. Грамматика содержит два основывающих правила и, сле­довательно, две основы: aSSb и с. По матрице предшество­вания определяем множества символов, которые могут находить­ся под каждой основой (это символы Х <•а для правила (1) и Y <•с для правила (2)). Таким образом, функция g()=1 (см. рис. 4.33) для множества цепочек { SaSSb, aaSSb, aSSb } и g()=2 для множества цепочек { Sc, ac,  }. В остальных случаях g() = ОШИБКА.

В заключение отметим, что каждая грамматика простого пред­шествования является LR(1)-грамматикой, в то время, как обратное утверждение неверно. Доказано, что существуют LR(1)-языки, которые не могут быть определены никакой грам­матикой простого предшествования.

4.3.3.Грамматики слабого предшествования

Многие грамматики, описывающие языки программирования, не являются грамматиками простого предшествования. Попытки найти для данного языка грамматику простого предшествования могут привести к довольно громоздким грамматикам. Можно расширить класс грамматик, анализируемых методом предшествования, исключив ограничение, что отношения <•ине могут пересе­каться.

Отношение •> по-прежнему используется для определения правого конца основы, а для локализации левого конца основы нужно найти правило грамматики, правая часть которого совпа­дает с символами, находящимися непосредственно слева от пра­вого конца основы.

При использовании такого подхода могут возникнуть труд­ности, связанные с тем, что среди правил вывода грамматики могут быть правила, правые части которых являются суффикса­ми одна другой. Например, если w – правовыводимая це­почка, в которой правый конец основы находится между симво­лами  и w, а A   и В   – два разных правила, то не ясно, какое из них следует выбрать для свертки.

Мы ограничимся применением самого длинного из применимых правил. Класс грамматик, для которых такое решение является правильным, образуют грамматики слабого предшествования.

Определение.

Пусть G = < T, N, S, R > – приве­денная грамматика без -правил. Назовем G грамматикой сла­бого предшествования, если

1. отношение •> не пересекается с объединением отношений <• и  ;

2. для AX и В   из R, где XV, не выполняется ни Х <• В, ни Х  В.

Пример 4.10. Рассмотрим грамматику G₀ (см. рис. 4.14). Матрица отношений простого предшествования для этой граммати­ки приведена на рис. 4.30. Как следует из рисунка, конфликты возникают только между отношениями <• и , и, следовательно. условие (1) определения грамматики слабого предшествования удовлетворяется. Рассмотрим правила (1) Е  Е + Т и (2) Е  Т, в которых одна правая часть служит суффиксом дру­гой. Между символами + и Е нет никакого отношения предшество­вания, значит, для этих правил условие (2) не нарушается. Аналогичное заключение можно сделать и для правил (3) и (4). Таким образом, G₀ – грамматика слабого предшествования.

Для любой обратимой грамматики слабого предшествования можно построить алгоритм разбора типа “перенос – свертка”.

Приведем этот алгоритм.

Вход

Обратимая грамматика слабого предшествования G = < T, N, S, R >, правила которой занумерованы натуральными числами от 1 до р.

Выход

Алгоритм A = (f, g) типа “перенос – свертка” для грамматики G.