Page 47 - 4761

Матрицю операторно передування будують аналогічно матриці простого
передування. Основна відмінність – відсутність нетермінальних символів в структурі
матриці.
Оскільки, алгоритм розбору вхідного ланцюга ігнорує на термінальні символи,
перетворимо правила заданої граматики таким чином, щоб залишити в ній тільки один
нетермінальний символ.
Приведена граматика буде мати вигляд:
G({+,-,*,/,a,b}, {S,T,E}, P, S)
P:
S  S+S | S-S | S (правила 1, 2, 3)
T  S*S | S/S |S (правила 4, 5, 6)
E  (S) | a | b (правила 7, 8, 9)
Таке перетворення не призводить до створення еквівалентної граматики і
виконується тільки для спрощення алгоритму. Отримана в результаті перетворення
граматика не є однозначною, але в алгоритм розпізнавання уже були закладені всі
необхідні дані про порядок застосування правил при побудові матриці передування.
Використовуючи матрицю ОП, запишемо послідовність розбору для ланцюга
a+a*b.

15. {a+a*b  к ;  п }  п
16. {+ a*b  к ;  п a}  з
17. {+a*b  к ;  п S; 8}  п
18. {a*b  к ;  п S+; 8}  п
19. {*b  к ;  п S+a; 8}  з
20. {*b  к ;  п S+S; 8; 8}  п
21. {b  к ;  п S+S*; 8; 8}  п
22. {  к ;  п S+S*b; 8; 8}  з
23. {  к ;  п S+S*S; 8; 8; 9}  з
24. {  к ;  п S+S; 8; 8; 9; 4}  з
25. {  к ;  п S; 8; 8; 9; 4; 1}.

Ланцюг має вигляд:
S  S+S  S+S+S  S+S+b  S+a*b  a+a*b.

Результатом роботи розпізнавача КВ-граматики вхідної мови є послідовність
правил граматики, яка приміняється для побудови вхідного ланцюга. По знайденій
послідовності, можна побудувати ланцюг виводу чи дерево виводу. В цьому випадку
дерево виводу виступає як дерево синтаксичного розбору і являє собою результат роботи
синтаксичного аналізатора.
Для повного уявлення про тип і структуру знайденої синтаксичної конструкції
вхідної мови в принципі достатньо знати послідовність номерів правил граматики,
застосованих для її побудови. А форма представлення цієї інформації може бути різною
(форма називається внутрішнє представлення програми).

3.9 Семантичний аналіз. Призначення семантичного аналізу

Всі мови програмування не є КВ-мовами. Тому повний розбір вхідної програми
компілятор не може виконати в межах КВ-мов за допомогою КВ-граматик та МП-
автоматів.
Повний розпізнавач для більшості мов програмування може бути побудований в
рамках КЗ-мов. Оскільки, розпізнавач КЗ-мов має експоненціальну залежність потрібних

45