4.4. Регулярні вирази й контекстно-вільні граматики
Кожна конструкція, що може бути описана регулярним виразом, може бути описана й граматикою. Наприклад, регулярний вираз (a|b)*abb і граматика
-
A0 ::= aA0|bA0|aA1
A1 ::= bA2
A2 ::= bA3
A3 ::= ε
описують одну й ту ж саму мову – множину рядків з а й b, що закінчуються на abb. Нижче вона представлена і в графічній формі (рис.4.11).
Рис. 4.11. Граф граматики для регулярного виразу (a|b)*abb
Ми можемо механічно перетворити недетермінований кінцевий автомат (НКА) у граматику, що породжує ту ж мову, що й розпізнаваний НКА. Наведена вище граматика побудована на основі вже показаного раніше НКА (рис. 4.12), у такий спосіб.
Для кожного стану і у НКА створюється нетермінальний символ Аі. Якщо стан і має перехід у стан j по символу а, уводимо в граматику відповідну продукцію Аі ::= aAj (якщо стан і переходить у стан j для входу ε, ми додаємо продукцію Аі ::= Aj). Для заключного стану і уводимо продукцію Ai ::= ε; якщо ж i — початковий стан, то Ai стає стартовим символом граматики.
Оскільки кожна регулярна множина є контекстно-вільною мовою, можна цілком резонно запитати: "Навіщо ж використати регулярні вирази для визначення лексичної структури мови?". Тому є кілька причин.
Лексичні правила мови найчастіше досить прості, і для їхнього опису не потрібен такий потужний інструмент, як граматика.
Регулярні вирази звичайно являють собою більш простий й виразніший запис токенів, чим на основі граматики.
На основі регулярних виразів можна автоматично побудувати більш ефективні лексичні аналізатори, чим на основі граматики.
Поділ синтаксичної структури мови на лексичну й нелексичну частини забезпечує поділ початкової стадії компілятора на модулі, що підвищує керованість проектом.
Не існує чітких правил щодо того, що варто розміщати в лексичній частині, а що - у синтаксичній. Регулярні вирази найбільш придатні для опису структури лексичних конструкцій, таких як ідентифікатори, константи, ключові слова й т.п. Граматики ж більше застосовні для опису вкладених структур типу збалансованих дужок, begin-end, умовних операторів if-then-else і т.п. Як уже згадувалося, ці структури не можуть бути описані регулярними виразами.
4.5. Перетворення граматик для спрощення синтаксичного аналізу
4.5.1 Усунення неоднозначності
Найчастіше для усунення неоднозначності граматика може бути переписана. Як приклад усунемо неоднозначність із наступної граматики:
stmt ::= if expr then stmt
| if expr then stmt else stmt (4.7)
| other
Тут "other" означає всі інші інструкції. Відповідно до цієї граматики наведемо таку умовну інструкцію:
if E1 then S1 else if E2 then S2 else S3
Вона має дерево розбору, показане на рис. 4.13.
Рис. 4.13.Дерево розбору для «правільної» інструкції if … then … else …
Але граматика (4.7) неоднозначна, оскільки рядок
if E1 then if E2 then S1 else S2 (4.8)
має два дерева розбору, показаних на рис. 4.14.
Рис. 4.14. Два дерева розбору для неоднозначного речення
У всіх мовах програмування з умовними інструкціями такого виду переважно дотримуються першого дерева розбору. Загальне правило говорить "зіставити кожне else найближчому незайнятому then". Це правило усунення неоднозначності може бути убудоване безпосередньо в граматику. Наприклад, ми можемо переписати граматику (4.7) як однозначну. Основна ідея полягає в тому, що інструкція, що з'являється між then й else, повинна бути "збалансована" (matched), тобто не повинна кінчатися на then, яка не відповідна деякій інструкції else. Така "збалансована" інструкція може являти собою або повну інструкцію if-then-else, що містить тільки "відповідні" інструкції, або будь-які інструкції, що відрізняються від умовної, тобто ми одержуємо граматику
stmt ::= matched_stmt
| unmatched_stmt
matched_stmt ::= іf expr then matched_stmt else matched_stmt
| other (4.9)
unmatched_stmt ::= if expr then stmt
| if expr then matched_stmt else unmatched_stmt
Ця граматика генерує ту ж множину рядків, що й граматика (4.7), але для рядка (4.8) дає тільки одне дерево розбору, а саме те, що зв'язує кожне else з найближчим незайнятим then.