Page 43 - 4761

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

Крок 1.
L0(S) = {T} R0(S) = {R, T}
L0(R) = {+,-} R0(R) = {R, T}
L0(T) = {E} R0(T) = {E, F}
L0(F) = { , /} R0(F) = {E, F}
L0(E) = {(, a, b} R0(E) = {), a,b}

Крок 2.

L1(S) = {T, E} R1(S) = {R, T, E, F}
L1(R) = {+,-} R1(R) = {R, T, E, F}
L1(T) = {E, (, a, b} R1(T) = {E, F, ), a, b}
L1(F) = { , /} R1(F) = {E, F, ), a, b}
L1(E) = {(, a, b} R1(E) = {), a, b}

Крок 3. Маємо L0(S)  L1(S), отже повертаємось до Кроку 2.
Крок 2.
L2(S) = {T, E, (, a, b} R2(S) = {R, T, E, F,), a, b}
L2(R) = {+,-} R2(R) = {R, T, E, F, ), a, b}
L2(T) = {E, (, a, b} R2(T) = {E, F, ), a, b}

41