Построение функции предшествования по заданной КС-грамматике (стр. 2 из 4)
· 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.
Таблица 2.
Множества крайних правых и крайних левых символов грамматики (по шагам построения)
| Символ | Шаг 1 (начало построения) | Последний шаг (результат) | ||
| (U) | L(U) | R(U) | L(U) | R(U) |
| J | ( p | ) p | ( p | ) p |
| T | J T | J | J T ( p | J ) p |
| B | T B | T | T B J ( p | T J ) p |
| S | - | B | - | B T J ) p |
Таблица 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).
Таблица 4.
Матрица предшествования грамматики
| Символы | - | & | ^ | ( | ) | p | ^ к |
| - | < | < | < | < | > | ||
| & | > | < | < | > | < | > | |
| ^ | > | > | < | > | < | > | |
| ( | < | < | < | = | < | ||
| ) | > | > | > | > | |||
| P | > | > | > | > | |||
| ^ н | < |
Посмотрим, как заполняется матрица предшествования в табл. 4 на примере символа &. В правиле грамматики B ® B&T (правило 3) этот символ стоит слева от нетерминального символа T. В множество Lt(T) входят символы: ^ ( p. Ставим знак < в клетках матрицы, соответствующих этим символам, в строке для символа &. В то же время в этом же правиле символ & стоит справа от нетерминального символа B. В множество Rt(B) входят символы: & ^ ) p. Ставим знак > в клетках матрицы, соответствующим этим символам, в столбце для символа &. Больше символ & ни в каком правиле не встречается, значит заполнение матрицы для него закончено, берем следующий символ и продолжаем заполнять матрицу таким же методом.
Алгоритм разбора цепочек грамматики операторного предшествования игнорирует нетерминальные символы. Поэтому имеет смысл преобразовать исходную грамматику таким образом, чтобы оставить в ней только один нетерминальный символ. Тогда получим следующий вид правил:
P: E ® -E (правило 1)
E ® E | E&E (правила 2 и 3)
E ® E | E^E (правила 4 и 5)
E ® (E) | p (правила 6 и 7)
Это преобразование не ведет к созданию эквивалентной грамматики и выполняется только после построения всех множеств и матрицы предшествования. Само преобразование выполняется только с целью более эффективного выполнения алгоритма разбора, в который уже заложены необходимые данные о порядке применения правил при создании матрицы предшествования.
3.4 Линеаризация матрицы предшествования
Для компактного хранения матрицы предшествования часто можно использовать следующий прием. По матрице M[n][n], элементы которой принимают только три значения (< = >), попытаемся построить два целочисленных вектора f и g:
M[i][j] равно >, если f[i]>g[j]
M[i][j] равно <, если f[i]<g[j]
M[i][j] равно =, если f[i]=g[j]
Для получения этих векторов используется следующий метод: построить ориентированный граф, содержащий n вершин типа F и n вершин типа G;
- построить ребро графа F[i]->G[j], если i > j
- построить ребро графа F[i]<-G[j], если i < j
- склеить вершины F[i] и G[j], если i = j
Если полученный граф циклический, то линеаризация невозможна. Иначе положить f[i] равным длине самого длинного пути из F[i], g[i] равным длине самого длинного пути из G[i].
4. Руководство пользователя
После запуска программы пользователю предлагается ввести КС-грамматику (ограничение при вводе: длина нетерминала не больше восьми символов). Ввод строки заканчивается нажатием клавиши Enter. Для определения в программе нетерминала используются символы ‘<’ и ‘>’ непосредственно между которыми находится нетерминал, знак или ‘|’, знак присвоить ‘:=’. Новая строка обязательно должна начинаться с нетерминала и последующим символом(и) ‘:=’.
Для начала анализа введённой КС-грамматике нужно нажать клавишу F5 или выбрать в меню пункт «Запуск» (меню вызывается нажатием F9). Перед тем как начать построение матрицы предшествования производится синтаксический анализ введенного текста.
Возможные ошибки при вводе грамматики:После символа ‘|’ должен обязательно следовать терминал или нетерминал.
В грамматике описан нетерминал <F>, но он нигде не используется (отсутствует в правой части).
В грамматике отсутствует описание нетерминала <ZZZ> (отсутствует в правой части)
Если грамматика введена верно, то начинается построение матрицы (алгоритм описан выше). При возникновении ошибки (один или несколько (не)терминалов имеют более чем одно отношение предшествования) выводится сообщение и в соответствующую ячейку записывается символ Х.
После этого выполняется линеаризация матрицы с помощью графа: для упрощения алгоритма в матрице сначала ведется поиск отношений = при нахождении таковых выполняется склеивание соответствующих вершин. Эта операция избавляет нас от рутинных действий связанных с «перестановкой» связей. Также упрощается описание графа в программе: надобность в хранении связей отсутствует - необходимо лишь хранить количество входящих и выходящих ребер. При построении векторов граф, проверяется на цикличность (при существовании цикла выводится сообщении о невозможности построения функции предшествования).