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

3.2 Грамматики операторного предшествования Грамматикой операторного предшествования называется приведенная КС-грамматика без ? -правил (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) = {t | ? U? *tz или ? U? *Ctz}, где t? VT, U,C? VN, z? V*; * Rt(U) = {t | ? U? *zt или ? U? *ztC }, где 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.

Таблица 3. Множества крайних правых и левых терминальных символов грамматики (по шагам построения) Символ Шаг 1 (начало построения) Последний шаг (результат) (U) Lt(U) Rt(U) Lt(U) Rt(U) J ( p ) p ( p ) p T ^ ^ ^ ( p ^ ) p B & & & ^ ( p & ^ ) p S - - - - & ^ ) p На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики (табл. 4).

Восходящие

      Ко второму классу относятся распознаватели, которые, читая входную цепочку строят ее дерево вывода начиная с вершин, соответствующих наиболее мелким конструкциям, и кончая корнем. В этом случае детерминированный разбор реализуется в терминах "сдвиг" и "свертка". Сдвиг - это перенос символа из входной цепочки в магазин(стек), а свертка - применение к вершине магазина какого-либо правила грамматики. Проблема в этом случае состоит в выборе между сдвигом и сверткой и в выборе правила для свертки.       LR-грамматика и грамматики предшествования, наиболее часто используемые из грамматик восходящего разбора. LR(k) - грамматикой называется грамматика, при использовании которой в качестве основы для анализатора все конфликты типа сдвиг - свертка и свертка - свертка можно разрешать на основании уже прочитанного текста и фиксированного числа предварительно просматриваемых символов.       Буква L показывает, что строки читаются слева направо, а R - что получается правосторонний разбор. На практике k принимает значение 0 или 1. Читая входную цепочку слева направо, анализатор пытается свернуть ее в начальный символ.       Шаг алгоритма состоит в считывании цепочки, расположенной в верхней части магазина, чтобы выяснить, образуют ли верхние символы правую часть какого-нибудь правила. Если это так, то производится свертка, заменяющая эти символы левой частью того самого правила. Если свертка невозможна, то в магазин переносится следующий входной символ и процесс продолжается.       Грамматики предшествования являются подклассами LR(k) - грамматик. При разборе данного типа грамматик используется понятие "основа цепочки". Основа правовыводимой цепочки - это ее любая подцепочка, которая является правой частью некоторого правила, причем после замены ее левой частью этого правила, тоже получается правовыводимая цепочка. Таким образом, если цепочку abw можно свернуть в цепочку aAw с помощью правила A->b, то b - основа цепочки abw .       Для грамматики предшествования границы основы правовыводимой цепочки можно определить с помощью некоторых отношений между символами, входящими в эту цепочку. Используются три отношения предшествования

• ·> - конец основы, выполняется между последним символом цепочки b и первым символом цепочки w;

• <· - начало основы, выполняется между последним символом цепочки a и первым символом цепочки b;

• =· - выполняется между смежными символами основы.

      Итак, основу правовыводимой цепочки грамматики простого предшествования можно выделить, просматривая эту цепочку слева направо до тех пор, пока впервые не встретится отношение конца цепочки. Для нахождения левого конца основы надо возвращаться назад, пока не встретится отношение начала основы. Полученная цепочка и будет искомой основой. Этот процесс продолжается до тех пор, пока входная цепочка не свернется к начальному символу.       Грамматика является грамматикой простого предшествования, если она приведенная, не содержит е-правил, и для любой пары символов выполняется не более одного отношения предшествования.       Рассмотрим грамматику, состоящую из правил:     S->aSSbЅ|c В качестве начала и конца цепочки используются маркеры # или $. Найдем отношения предшествования. 1) =· Просматриваем правые части правил, получаем a =· S, S =· S, S =· b. 2) <· Ищем в правых частях правил пары смежных символов ХС, таких что Х находится в отношении <· с самым левым символом цепочки, выводимой из С. Рассмотрим пару aS, получим a <· a, a <· c. Рассмотрим пару SS, получим S <· a, S <· c. Рассмотрим начальный маркер, получим $ <· a, $ <· c. 3) ·> Ищем в правых частях правил пары смежных символов СХ. Затем ищем символы Y, которые могут оказаться на правом конце цепочки, выводимой из С за один или более шагов, и терминалы d, которые могут находиться в начале цепочки, выводимой из Х за нуль и более шагов. В нашем случае это пары: SS: b ·> a, b ·> c, c ·> a, c ·> c; Sb: b ·> b, c ·> b; конечный маркер: b ·> $, c ·> $.       Построим таблицу для этих отношений. Это квадратная матрица, строки и столбцы которой помечены терминалами , нетерминалами и маркером (начала или конца цепочки). Пустая ячейка таблицы соответствует состоянию ошибки.

	S	a	b	C	$
S	=·	<·	=·	<·
a	=·	<·		<·
b		·>	·>	·>	·>
c		·>	·>	·>	·>
$		<·		<·

      Так как в одной ячейки управляющей таблицы записано не более одного отношения предшествования, то это грамматика предшествования, кроме того правые части всех правил различны, следовательно это грамматика простого предшествования.       Построение алгоритма разбора. Символ $ будем использовать в качестве маркера для стека и правого концевого маркера входной цепочки. Действие f(x,a) зависит от верхнего символа стека и самого левого символа необработанной части входной цепочки. f(x,a) - перенос (сдвиг), если х <· a или х =· а. f(x,a) - свертка, если х ·> a. f(x,a) - ошибка в противоположных случаях. f($S$) - допуск цепочки.       Функция свертки зависит от верхней части стека, включающей основу и еще одного символа ниже нее. Оставшаяся необработанная часть входной цепочки на свертку не влияет.       Грамматика операторного предшествования - это приведенная контекстно-свободная грамматика без е-правил, в которой правые части правил не содержат смежных нетерминалов. Операторная грамматика является грамматикой операторного предшествования, если между любыми двумя терминальными символами выполняется не более одного отношения предшествования. Для грамматик операторного предшествования отношения задаются на множестве терминалов плюс маркер начала (конца), игнорируя нетерминалы. Рассмотрим отношения: a =· b , если есть правило A->…ab… или A->…aBb… a <· b , если есть правило A->…aB и B->b… или B->Cb… a ·> b , если есть правило A->…Bb… и B->…a или B->…aC $ <· a , если есть правило S->Ca… или S->a… a ·> $ , если есть правило S->…aC или S->…a       Алгоритм разбора цепочки по управляющей таблице аналогичен предыдущему.       Отыскивая самую левую основу, распознаватель для грамматики операторного предшествования не обращает внимания на нетерминалы приводимой основы. Нетерминалы могут учитываться только семантическими подпрограммами. Поэтому правила, содержащие только нетерминалы в правых частях, можно не включать в таблицу правил.

Грамматикой операторного предшествования называется приведенная КС-грамматика без 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 - L_t(U) или R_t(U):

•       L_t(U) = {t | $ UÞ*tz или $ UÞ*Ctz }, где tÎVT, U,CÎVN, zÎV^*;

•       R_t(U) = {t | $ UÞ*zt или $ UÞ*ztC }, где 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ÎL_t(C), где a,bÎVT, U,CÎVN, x,yÎV^*;

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

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

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

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

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

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

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

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

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