После построения множеств L(U) и R(U) по правилам грамматики создается матрица предшествования. Матрицу предшествования дополняют символами ^ н и ^ к (начало и конец цепочки). Для них определены следующие отношения предшествования:

^ н < a, " aÎ V, если $ SÞ *ax, где SÎ VN, xÎ V* или (с другой стороны) если aÎ L(S);

^ к > a, " aÎ V, если $ SÞ *xa, где SÎ VN, xÎ V* или (с другой стороны) если aÎ R(S).

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

Грамматикой операторного предшествования называется приведенная КС-грамматика без l -правил (e-правил), в которой правые части продукций не содержат смежных нетерминальных символов. Для грамматики операторного предшествования отношения предшествования можно задать на множестве терминальных символов (включая символы ^ н и ^ к).

Отношения предшествования для грамматики операторного предшествования G(VN,VT,P,S) задаются следующим образом:

·        a = b, если и только если существует правило U® xaby Î P или правило U® xaCby, где a,bÎ VT, U,CÎ VN, x,yÎ V*;

·        a < b, если и только если существует правило U® xaCy Î P и вывод CÞ *bz или вывод CÞ *Dbz, где a,bÎ VT, U,C,DÎ VN, x,y,zÎ V*;

·        a > b, если и только если существует правило U® xCby Î P и вывод CÞ *za или вывод CÞ *zaD, где a,bÎ VT, U,C,DÎ VN, x,y,zÎ V*.

В грамматике операторного предшествования различные порождающие правила имеют разные правые части. Для грамматики операторного предшествования тоже строится матрица предшествования, но она содержит только терминальные символы грамматики.

Для построения этой матрицы удобно ввести множества крайних левых и крайних правых терминальных символов относительно нетерминального символа U - Lt(U) или Rt(U):

·        Lt(U) = $ UÞ *tz или $ UÞ *Ctz, где tÎ VT, U,CÎ VN, zÎ V*;

·        Rt(U) = t , где tÎ VT, U,CÎ VN, zÎ V*.

Тогда определения отношений операторного предшествования будут выглядеть так:

·        a = b, если $ правило U® xaby Î P или правило U® xaCby, где a,bÎ VT, U,CÎ VN, x,yÎ V*;

·        a < b, если $ правило U® xaCy Î P и bÎ Lt(C), где a,bÎ VT, U,CÎ VN, x,yÎ V*;

·        a > b, если $ правило U® xCby Î P и aÎ Rt(C), где a,bÎ VT, U,CÎ VN, x,yÎ V*.

В данных определениях цепочки символов x,y,z могут быть и пустыми цепочками.

Для нахождения множеств Lt(U) и Rt(U) используется следующий алгоритм:

Шаг 1. Для каждого нетерминального символа грамматики U строятся множества L(U) и R(U).

Шаг 2. Для каждого нетерминального символа грамматики U ищутся правила вида U® tz и U® Ctz, где tÎ VT, CÎ VN, zÎ V*; терминальные символы t включаются во множество Lt(U). Аналогично для множества Rt(U) ищутся правила вида U® zt и U® ztC.

Шаг 3. Просматривается множество L(U), в которое входят символы U’,U”,... Множество Lt(U) дополняется символами, входящими в Lt(U’), Lt(U”), ... и не входящими в Lt(U). Аналогичная операция выполняется и для множества Rt(U) на основе множества R(U).

Для практического использования матрицу предшествования дополняют символами ^ н и ^ к (начало и конец цепочки). Для них определены следующие отношения предшествования:

^ н < a, " aÎ VT, если $ SÞ *ax или $ SÞ *Cax, где S,CÎ VN, xÎ V* или если aÎ Lt(S);

^ к > a, " aÎ VT, если $ SÞ *xa или $ SÞ *xaC, где S,CÎ VN, xÎ V* или если aÎ Rt(S).

3.3 Пример построения матрицы предшествования

Построим матрицу предшествования для грамматики операторного предшествования.

Рассмотрим в качестве примера грамматику G({S,B,T,J},{-,&,^,(,),p},P,S): (Терминалы выделены жирным шрифтом)

P: S ® -B (правило 1)
B ® T | B&T (правила 2 и 3)
T ® J | T^J (правила 4 и 5)
J ® (B) | p (правила 6 и 7)

Видно, что эта грамматика является грамматикой операторного предшествования.

Построим множества крайних левых и крайних правых символов L(U), R(U) относительно всех нетерминальных символов грамматики. Результат построения приведен в табл. 2.

На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики. Результат (второй и третий шаги построения) приведен в табл. 3.

Таблица 2.

Множества крайних правых и крайних левых символов грамматики (по шагам построения)