Вопрос 12.1.

Грамматикой простого предшествования называют такую приведенную (без циклов, бесплодных и недостижимых символов и -правил)КС-грамматику G(VN,VT,P,S), V = VTVN, в которой:

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

• В_i =• В_j ( B_i, B_j  V), если и только если  правило AxB_iB_jy  P, где AVN, x,yV*;

• В_i <• В_j ( B_i, B_j  V), если и только если  правило AxB_iDy  P и вывод D*S_jz, где A,DVN, x,y,zV*;

• В_i •> B_j ( B_i, B_j  V), если и только если  правило АхСВ_jу  P и вывод C*zB_i или  правило AxCDy  P и выводы C*zB_i и D*B_jw, где A,C,DVN, x,y,z,wV*.

2. Различные правила в грамматике имеют разные правые части (то есть в грам­матике не должно быть двух различных правил с одной и той же правой ча­стью).

Отношения =•, <• и •> называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между какими-либо двумя символами может и не быть от­ношения предшествования — это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций — они не обладают ни свой­ством коммутативности, ни свойством ассоциативности. Например, если извест­но, что В_i •> B_j, то не обязательно выполняется B_j <• В_i (поэтому знаки предшест­вования иногда помечают специальной точкой: =•, <•, •>).

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

• всякая грамматика простого предшествования является однозначной;

• легко проверить, является или нет произвольная КС-грамматика граммати­кой простого предшествования (для этого достаточно проверить рассмотрен­ные выше свойства грамматик простого предшествования или воспользовать­ся алгоритмом построения матрицы предшествования, который рассмотрен далее).

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

Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:

• B_i <• B_i+1, если символ B_i+1 — крайний левый символ некоторой основы (это отношение между символами можно назвать «предшествует основе» или про­сто «предшествует»);

• В_i •> B_i+1, если символ В_i — крайний правый символ некоторой основы (это отношение между символами можно назвать «следует за основой» или просто «следует»);

• В_i =• B_i+1, если символы В_i и B_i+1 принадлежат одной основе (это отношение между символами можно назвать «составляют основу»),

Исходя из этих соотношений, выполняется разбор строки для грамматики пред­шествования.

Суть принципа такого разбора можно пояснить на рис. 12.5. На нем изображена входная цепочка символов  в тот момент, когда выполняется свертка цепоч­ки . Символ a является последним символом подцепочки , а символ b — первым символом подцепочки . Тогда, если в грамматике удастся установить непроти­воречивые отношения предшествования, то в процессе выполнения разбора по алгоритму «сдвиг-свертка» можно всегда выполнять сдвиг до тех пор, пока меж­ду символом на верхушке стека и текущим символом входной цепочки сущест­вует отношение <• или =•. А как только между этими символами будет обнаружено отношение •>, так сразу надо выполнять свертку. Причем для выполнения свертки из стека надо выбирать все символы, связанные отношением =•. То, что все различные правила в грамматике предшествования имеют различные правые части, гарантирует непротиворечивость выбора правила при выполнении свертки.

Таким образом, установление непротиворечивых отношений предшествования между символами грамматики в комплексе с несовпадающими правыми частями различных правил дает ответы на все вопросы, которые надо решить для органи­зации работы алгоритма «сдвиг-свертка» без возвратов.

Рис. 12.5. Отношения между символами входной цепочки в грамматике предшествования

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