Page 14 - 4761

Дана граматика є неоднозначною, тому що з точки зору семантики в ній немає
пріоритету операцій, адже «*», виконується раніше за «+», тому при побудові
компіляторів, таку граматику використовувати не можна, необхідно вказувати пріоритет
виконання операцій. Отже, граматика для мови програмування повинна завжди бути
однозначною, а якщо ні, то треба привести її до цього виду.
Граматика називається однозначною, якщо для кожного ланцюга символів мови,
заданого цією граматикою, можна побудувати один ліво- або правосторонній виводи.
Інакше – неоднозначна.
Приклад 1.5.
G({+, -, *, /, (, ), a, b}, { S, T, F}, P, S):
P’:
SS+T S  T T
T T*E T / E E

E (S) a b
Тут можливий тільки один лівосторонній вивід:
S S+TT+T T*E+TE*E+T a*E+Ta*b+Ta*b+Ea*b+а
Цьому виводу відповідає тільки одне можливе дерево виводу (рис.1.2). Видно, що
ланцюг дещо подовжився, але пріоритет операцій в даному випадку є єдино можливий і
відповідає їхньому порядку в арифметиці.

Рисунок 1.2 – Дерево виводу для однозначної граматики

В загальному вигляді неможна перевірити, чи є задана граматика однозначною.
Проте для КВ-граматик існують правила, за наявністю яких в множині правил граматики
G(VT, VN, P, S) можна стверджувати, що вона є неоднозначною.
Правила, які задають неоднозначність в граматиці:
1. А  АА  ,

2. А  АαА  ,
3. А  αА А γ,

4. А  αА А А γ,
*
де A  VN, α, β, γ  (VN VT) .

12