Page 46 - 4761

- a=b, якщо існує правило А→xaby є Р або А→хаСby, де а, b є VT, A,C є VN, xy є V*;
- a<b, якщо існує правило А→xaCy є Р; вивід С => *bz або С=> *Dbz, де a,b є VT,
A,C,D є VN, x,y,z є V*;
- a>b, якщо існує правило А→xCby є Р, вивід С => *zа або С=> *zаD, де a,b є VT,
A,C,D є VN, x,y,z є V*

Алгоритм “зсув-згортка” для ГОП
Основна відмінність, що при визначенні відношення передування цей алгоритм не
бере до уваги нетермінальних символів, що знаходяться в стеці і при порівнянні шукає
найближчий до верхівки стеку термінальний символ. Проте після виконання порівняння і
визначення границь основи при пошуку правила в граматиці, треба приймати до уваги всі
не термінальні символи.
Алгоритм.
К1. Помістити у верхівку стеку  n, зчитуючи головку – в початок вхідного
ланцюга символів.
К2. Порівняти найближчий до верхівки стеку термінальний символ (лівий символ
відношення), з поточним символом вхідного ланцюга (правий символ).
К3. Якщо < або = , то зробити зсув ( переніс поточного символа з вхідного
ланцюга в стек і зсув головки на один символ і К2, інакше К4.
К4. Якщо  >, то згортка. Для цього треба знайти на вершині стеку всі термінальні
символи, пов’язані відношенням = , а також всі сусідні з ним не термінальні символи.
Всі символи, що складають основу, треба видалити зі стеку, а потім вибрати з граматики
правило, яке має праву частину, що співпадає з основою і помістити в стек ліву частину
правила. Якщо правила знайти не вдалося, то помилка, інакше, якщо розбір не закінчено
то К2.
К5. Якщо не встановлено ні одного відношення передування, то помилка.
Для заданої граматики G побудуємо матрицю операторного передування.
G({+,-,*,/,a,b}, {S,T,E}, P, S)
P:
S  S+T | S-T | T
T  T*E | T/E |T
E  (S) | a | b
Множина крайніх лівих і правих термінальних символів відносно всіх не
термінальних має вигляд.

Lt (S)= {+, -,*,/,(, a, b} Rt(S)= {+,-,*,/,),a,b}
Lt (T)= {*,/,(, a, b} Rt(T)= {*,/,),a,b}
Lt (E)= {(, a, b} Rt(E)= {),a,b}

Будуємо матрицю операторного передування .

+ - * / ( ) a b ┴ к
+ ·> ·> <· <· <· ·> <· <· ·>
- ·> ·> <· <· <· ·> <· <· ·>
* ·> ·> ·> ·> <· ·> <· <· ·>
/ ·> ·> ·> ·> <· ·> <· <· ·>
( <· <· <· <· <· =· <· <·
) ·> ·> ·> ·> ·> ·>
a ·> ·> ·> ·> ·> ·>
b ·> ·> ·> ·> ·> ·>
┴ п <· <· <· <· <· <· <·

Рисунок 3.7 – Матриця операторного передування

44