ub> н
<
Подивимося, як заповнюється матриця передування в табл. 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]
M [i] [j] дорівнює =, якщо f [i] = g [j]
Для отримання цих векторів використовується наступний метод: побудувати орієнтований граф, що містить n вершин типу F і n вершин типу G;
- побудувати ребро графа F [i] -> G [j], якщо i> j
- побудувати ребро графа F [i] <-G [j], якщо i
- склеїти вершини F [i] і G [j], якщо i = j
Якщо отриманий граф циклічний, то лінеаризація неможлива. Інакше покласти f [i] рівним довжині найдовшого шляху з F [i], g [i] рівним довжині найдовшого шляху з G [i]. h1> 4. Керівництво користувача
Після запуску програми користувачеві пропонується ввести КС-граматику (обмеження при введенні: довжина нетермінала не більше як вісім символі...
