Если грамматика является грамматикой простого предшествования, то для поиска основы каждой ее сентенции надо просматривать элементы сентенции слева направо и найти самую левую пару символов xj и xj +1, такую что xj×>xj +1. Окончанием основы сентенции будет xj. Далее просматривать элементы сентенции справа налево, начиная с символа xj до тех пор, пока не будет найдена самая правая пара символов xi -1 и xi, такая что xi -1 <× xi. Заголовком основы будет символ xi. Таким образом, будет найдена основа сентенции, имеющая вид xi xi +1 …xj -1 xj. Схема поиска основы сентенции грамматики представлена на рисунке 3.4.
x 1 | x 2 | … | xi- 1 | xi | xi +1 | … | xj -1 | xj | xj+ 1 | … | xn |
<× … <× = × … = × ×> … ×>
Рисунок 3.4 – Схема поиска основы сентенции грамматики
На основе отношений предшествования строят матрицу предшествования грамматики. Строки и столбцы матрицы предшествования помечаются символами грамматики. Пустые клетки матрицы указывают на то, что данные символы не связаны отношением предшествования.
|
|
Определение Построение матрицы предшествования основано на двух вспомогательных множествах, определяемых следующим образом:
- L (A) = { X | $ A Þ* Xz }, A Î VN, X Î V, z Î V * - множество крайних левых символов относительно нетерминального символа А;
- R (A) = { X | $ A Þ* zX }, A Î VN, X Î V, z Î V* - множество крайних правых символов относительно нетерминального символа А.
Определение Отношения предшествования можно определить с помощью введенных множеств следующим образом:
- Bi =× Bj (" Bi, Bj Î V), если и только если существует правило A ® xBiBjy Î P, где A Î VN, x, y Î V *;
- Bi <× Bj (" Bi, Bj Î V), если и только если существует правило A ® xBiDy Î P и Bj Î L (D),где A, D Î VN, x, y Î V *;
- Bi ×> Bj (" Bi, Bj Î V), если и только если существует правило A ® xCBjy и Bi Î R (C) или существует правило A ® xCDy Î P и Bi Î R (C), Bj Î L (D), где A, C, D Î VN, x, y Î V*.
Матрицу предшествования дополняют символами ^н и ^к (начало и конец цепочки). Для них определены следующие отношения предшествования:
- ^н <× X," X Î V, если X Î L (S);
- ^к ×> X," X Î V, если X Î R (S).
3.5.1.1.3 Построение множеств L (A) и R (A)
Шаг 1. Для каждого нетерминального символа А ищем все правила, содержание А в левой части. Во множество L (A) включаем самый левый символ из правой части правил, а во множество R (A) – самый крайний правый символ из правой части, т.е.
" A Î VN: L 0(A) = { X | A ® Xy, X Î V, y Î V *},
R 0(A) = { X | A ® yX, X Î V, y Î V *}.
Шаг 2. Для каждого нетерминального символа А: если множество L (A) содержит нетерминальные символы грамматики А¢, A², …, то множество L (A) надо дополнить символами, входящими в соответствующие множества L (А¢), L (A²) и т.д., … и не входящими в L (A). Аналогичную операцию выполнить для множеств R (A), т.е.
|
|
" A Î VN: Li (A) = Li -1(A)È Li -1(B)," B Î (Li -1(A)Ç VN),
R i(A) = Ri -1(A)È Ri -1(B), " B Î (Ri -1(A)Ç VN).
Шаг 3.Если на предыдущем шаге хотя бы одно множество L (A) или R (A) для некоторого символа грамматики изменилось, то вернуться к шагу 2, иначе построение закончено. Т.е. если существует A Î VN: Ri (A)¹ Ri -1(A) или Li (A)¹ Li -1(A), то положить i:= i +1 и вернуться к шагу 2, иначе построение закончено и R (A) = Ri (A) и L (A) = Li (A).