Головна

Регулярні вирази й контекстно-вільні граматики

  1. Teaching Grammar Навчання граматики
  2. Алгоритм 4.2. Ліва факторизація граматики
  3. Введення та редагування текстової інформації. Перевірка орфографії та граматики
  4. Граматики та роль синтаксичного аналізатора
  5. Контекстно-вільні граматики
  6. Молодограматики
  7. Означення гіперболи та її канонічне рівняння. Вирази для фокальних радіусів.

Кожна конструкція, що може бути описана регулярним виразом, може бути описана й граматикою. Наприклад, регулярний вираз (a|b)*abb і граматика

A0 ::= aA0|bA0|aA1
A1 ::= bA2
A2 ::= bA3
A3 ::= ε

описують одну й ту ж саму мову - множину рядків з а й b, що закінчуються на abb. Нижче вона представлена і в графічній формі (рис.4.11).

Рис. 4.11. Граф граматики для регулярного виразу (a|b)*abb

Ми можемо механічно перетворити недетермінований кінцевий автомат (НКА) у граматику, що породжує ту ж мову, що й розпізнаваний НКА. Наведена вище граматика побудована на основі вже показаного раніше НКА (рис. 4.12), у такий спосіб.


Рис. 4.12. Недетермінований кінцевий автомат, що допускає рядок (a|b)*abb

Для кожного стану і у НКА створюється нетермінальний символ Аі. Якщо стан і має перехід у стан j по символу а, уводимо в граматику відповідну продукцію Аі ::= aAj (якщо стан і переходить у стан j для входу ε, ми додаємо продукцію Аі ::= Aj). Для заключного стану і уводимо продукцію Ai ::= ε; якщо ж i - початковий стан, то Ai стає стартовим символом граматики.

Оскільки кожна регулярна множина є контекстно-вільною мовою, можна цілком резонно запитати: "Навіщо ж використати регулярні вирази для визначення лексичної структури мови?". Тому є кілька причин.

1. Лексичні правила мови найчастіше досить прості, і для їхнього опису не потрібен такий потужний інструмент, як граматика.

2. Регулярні вирази звичайно являють собою більш простий й виразніший запис токенів, чим на основі граматики.

3. На основі регулярних виразів можна автоматично побудувати більш ефективні лексичні аналізатори, чим на основі граматики.

4. Поділ синтаксичної структури мови на лексичну й нелексичну частини забезпечує поділ початкової стадії компілятора на модулі, що підвищує керованість проектом.

Не існує чітких правил щодо того, що варто розміщати в лексичній частині, а що - у синтаксичній. Регулярні вирази найбільш придатні для опису структури лексичних конструкцій, таких як ідентифікатори, константи, ключові слова й т.п. Граматики ж більше застосовні для опису вкладених структур типу збалансованих дужок, begin-end, умовних операторів if-then-else і т.п. Як уже згадувалося, ці структури не можуть бути описані регулярними виразами.



Дерева розбору й приведення | Усунення неоднозначності

Граматики та роль синтаксичного аналізатора | Num → digits optional_fraction | Контекстно-вільні граматики | Угоди по позначеннях | Породження | Усунення лівої рекурсії | Алгоритм 4.2. Ліва факторизація граматики |

© um.co.ua - учбові матеріали та реферати