Реферат: Построение функции предшествования по заданной КС-грамматике
· Si = Sj (" Si ,SjÎ V ), если и только если $ правило U® xSi Sj y Î P , где UÎ VN , x,yÎ V * ;
· Si < Sj (" Si ,SjÎ V ), если и только если $ правило U® xSi Dy Î P и вывод DÞ *Sj z, где U,DÎ VN , x,y,zÎ V * ;
· Si > Sj (" Si ,SjÎ V ) , если и только если $ правило U® xCSj y Î P и вывод CÞ *zSi или $ правило U® xCDy Î P и выводы CÞ *zSi и DÞ *Sj w, где U,C,DÎ VN , x,y,z,wÎ V * .
2. Различные порождающие правила имеют разные правые части.
Отношения =, < и > называют отношениями предшествования для символов. Отношение предшествования единственно для каждой упорядоченной пары символов. При этом между какими-либо двумя символами может и не быть отношения предшествования - это значит, что они не могут находиться рядом ни в одном элементе разбора синтаксически правильной цепочки. Отношения предшествования зависят от порядка, в котором стоят символы, и в этом смысле их нельзя путать со знаками математических операций - например, если Si > Sj , то не обязательно, что Sj < Si (поэтому знаки предшествования иногда помечают специальной точкой: =× , <× , × >)
Метод предшествования основан на том факте, что отношения предшествования между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:
· Si < Si+1 , если символ Si+1 - крайний левый символ некоторой основы;
· Si > Si+1 , если символ Si - крайний правый символ некоторой основы;
· Si = Si+1 , если символы Si и Si+1 принадлежат одной основе.
Исходя из этих соотношений выполняется разбор строки для грамматики предшествования.
На основании отношений предшествования строят матрицу предшествования грамматики. Строки матрицы предшествования помечаются первыми символами, столбцы - вторыми символами отношений предшествования, а в клетки матрицы на пересечении соответствующих столбца и строки помещаются знаки отношений. При этом пустые клетки матрицы говорят о том, что между данными символами нет ни одного отношения предшествования.
Матрицу предшествования грамматики можно построить, опираясь непосредственно на определения отношений предшествования, но удобнее воспользоваться двумя дополнительными множествами - множеством крайних левых и множеством крайних правых символов относительно нетерминалов грамматики. Эти множества определяются следующим образом:
· L (U) = {T | $ UÞ *Tz}, U,TÎ V , zÎ V * - множество крайних левых символов относительно нетерминального символа U (цепочка z может быть и пустой цепочкой);
· R (U) = {T | $ UÞ *zT}, U,TÎ V , zÎ V * - множество крайних правых символов относительно нетерминального символа U.
Тогда отношения предшествования можно определить так:
· Si = Sj (" Si ,SjÎ V ), если $ правило U® xSi Sj y Î P , где UÎ VN , x,yÎ V * ;
· Si < Sj (" Si ,SjÎ V ), если $ правило U® xSi Dy Î P и SjÎ L (D), где U,DÎ VN , x,yÎ V * ;
· Si > Sj (" Si ,SjÎ V ) , если $ правило U® xCSj y Î P и SiÎ R (C) или $ правило U® xCDy Î P и SiÎ R (C), SjÎ L (D), где U,C,DÎ VN , x,yÎ V * .
Такое определение отношений удобнее на практике, так как не требует построения выводов, а множества L (U) и R (U) могут быть построены для каждого нетерминального символа UÎ VN по очень простому алгоритму:
Шаг 1. Для каждого нетерминального символа U ищем все правила, содержащие U в левой части. Во множество L (U) включаем самый левый символ из правой части правил, а во множество R (U) - самый крайний символ правой части. Переходи к шагу 2.
Шаг 2. Для каждого нетерминального символа U: если множество L (U) содержит нетерминальные символы грамматики U’,U”,..., то его надо дополнить символами, входящими в соответствующие множества L (U’), L (U”), ... и не входящими в L (U). Ту же операцию надо выполнить для R (U).
Шаг 3. Если на предыдущем шаге хотя бы одно множество L (U) или R (U) для некоторого символа грамматики изменилось, то надо вернуться к шагу 2, иначе построение закончено.
После построения множеств 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 * ;