Реферат: Построение функции предшествования по заданной КС-грамматике
· 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).
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.
На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов L t (U), R t (U) относительно всех нетерминальных символов грамматики. Результат (второй и третий шаги построения) приведен в табл. 3.
Таблица 2.
Множества крайних правых и крайних левых символов грамматики (по шагам построения)
|
Символ |
Шаг 1 (начало построения) |
Последний шаг (результат) | ||
|
К-во Просмотров: 729
Бесплатно скачать Реферат: Построение функции предшествования по заданной КС-грамматике
| ||||