Page 44 - 4761

L2(F) = { , /} R2(F) = {E, F, ), a, b}
L2(E) = {(, a, b} R2(E) = {), a, b}

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

Крок 3. Ні одна з множин не змінилася, побудова закінчена. Результат:
L(S) = {T, E, (, a, b} R(S) = {R, T, E, F,), a, b}
L(R) = {+,-} R(R) = {R, T, E, F, ), a, b}
L(T) = {E, (, a, b} R(T) = {E, F, ), a, b}.

+ - * / ( ) a b S R T F E ┴ к
+ <· <· <· =· <·
- <· <· <· =· <·
* <· <· <· =·
/ <· <· <· =·
( <· <· <· =· <· <·
) ·> ·> ·> ·> ·> ·> ·> ·>
a ·> ·> ·> ·> ·> ·> ·> ·>
b ·> ·> ·> ·> ·> ·> ·> ·>
S =·
R ·> ·>
T <· <· ·> =· ·>
F ·> ·> ·> ·> ·>
E ·> ·> <· <· ·> ·> =· ·>
┴ п <· <· <· <· <·

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

Пояснимо побудову матриці на прикладі символа ‘+’ . В правилах граматики
R+T|+TR ‘+’ стоїть зліва від символа Т. Отже, в рядку символ + в стовпчику, який
відповідає Т, ставимо знак = .
Крім того, в множину L(T) входять символи E,(,a,b, тоді в рядку символа + в усіх
стовпцях, які відповідають цим чотирьом символам ставимо < . Символ +, входять в
множину L(R), а в граматиці є правила виду S  TR; R  +TR|-TR. Отже, треба розглянути
множину R(T). Тоді вхідні символи E, F, a, b, ). Отже, в стовпчику символа + в усіх
рядках, що відповідають цим 5 символам, ставимо  >. Більше + ні в які множини не
входив і ні в яких правилах не зустрічається.
Окремо розглянемо заповнення рядка для символа  n і стовпця  к . Множину
L(S), де S-початковий символ містить символи T,E,(,a,b,  Поміщаємо < в рядок, який
відповідає  n для всіх 5 стовпців, які відповідають цим символам. Аналогічно R(S)
містить R,T,E,F,),a,b. Поміщаєм  > в стовпчик, який відповідає  к для всіх 7 рядків, що
відповідають цим символам.
Записати послідовність розбору у вигляді послідовності конфігурацій МП-автомата з
ох
3- складових:
1) не переглянутій автоматом частини вхідного ланцюга;
2) вмісту стека;
42