Реферат: Построение функции предшествования по заданной КС-грамматике
<
)
>
>
>
>
P
>
>
>
>
^ н
<
Посмотрим, как заполняется матрица предшествования в табл. 4 на примере символа & . В правиле грамматики B ® B& T (правило 3) этот символ стоит слева от нетерминального символа T. В множество L t (T) входят символы: ^ ( p . Ставим знак < в клетках матрицы, соответствующих этим символам, в строке для символа & . В то же время в этом же правиле символ & стоит справа от нетерминального символа B. В множество R t (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 . Для определения в программе нетерминала используются символы ‘<’ и ‘>’ непосредственно между которыми находится нетерминал, знак или ‘|’, знак присвоить ‘:=’. Новая строка обязательно должна начинаться с нетерминала и последующим символом(и) ‘:=’.