Page 45 - 4761

3) послідовності застосованих правил граматики.
Послідовність номерів правил має додаткову корисну інформацію, на основі якої
можна побудувати дерево чи ланцюг виводу. Правила нумеруються зліва направо, і зверху
вниз.
Позначення :
 такт автомата;  п – виконувався перенос;  з –виконувалася згортка.

Приклад 3.4. Записати послідовність розбору для ланцюга a+a*b.
1. {a+a*b  к ;  п }  п
2. {+ a*b  к ;  п a}  з
3. {+a*b  к ;  п E; 14}  з
4. {+a*b  к ;  п T; 14;8}  п
5. {a*b  к ;  п T+; 14;8}  п
6. {*b  к ;  п T+a; 14;8}  з
7. {*b  к ;  п T+E; 14;8;14}  п
*
8. {b  к ;  п T+E ; 14;8;14}  п
*
9. {b  к ;  п T+E b; 14;8;14}  з
*
10. {  к ;  п T+E E; 14;8;14;15}  з
11. {  к ;  п T+EF; 14;8;14;15;9}  з
12. {  к ;  п T+T; 14;8;14;15;9;7}  з
13. {  к ;  п TR; 14;8;14;15;9;7;3}  з
14. {  к ;  п S; 14;8;14;15;9;7;3;1} – алгоритм завершений, ланцюг прийнято.

Ланцюг має вигляд:
S  TR  T+T  T+EF  T+E*E  T+E*b  T+a*b  E+a*b  a+a*b.
Дерево виводу:

Рисунок 3.6 – Приклад дерева виводу для ГПП

У ГПП є один недолік – при великій кількості термінальних і нетермінальних
символів в граматиці матриця передування буде мати значний об’єм (при цьому частина
комірок може бути пустою).

3.8 Граматика операторного передавання (ГОП)

ГОП – називається КВ-граматика без λ-правил, в якій праві частини всіх правил не
міняють суміжних не термінальних символів.
Для неї використовують умови:
43