2.2.4 Регулярні визначення

Для зручності запису регулярним виразам можна давати імена й визначати регулярні вирази з використанням цих імен так, ніби це були символи. Якщо V є алфавитом базових символів, то регулярне визначення являє собою послідовність виду

d1 → r1, d2 → r2, d3 → r3, …, dn → rn, …

де кожне di — індивідуальне ім'я, а кожне r_i — регулярний вираз над символами з VU{d₁,d₂,...,d_i-1}, тобто базовими символами й уже визначеними іменами. Обмежуючи кожне r_i символами з V і раніше визначеними іменами, можна побудувати регулярний вираз над V для будь-якого r_i, заміняючи (можливо, неодноразово) імена регулярних виразів позначеними ними виразами. Якщо r_i використає d_і для якогось j ≥ i, то ri може виявитися визначене рекурсивно, і підстановка ніколи не завершиться.

Для того щоб відрізнити імена від символів, імена в регулярних виразах виділяються іншим шрифтом.

Приклад 2.4

Як говорилося раніше, множина ідентифікаторів мови Pascal являє собою множину рядків з букв і цифр, що починаються з букви. От регулярне визначення цієї множини:

letter → A | B | ... | Z | a | b | … |z

digit → 0 | 1 | … |9

id → letter(letter | digit)^*

Приклад 2.5

Беззнакові числа в Pascal являють собою рядки типу 5280, 39.37, 6.336Е4 або 1.894Е-4. Наступне регулярне визначення забезпечує точну специфікацію цього класу рядків:

digit → 0 | 1 | … |9

digits → digit digit*

optional_fraction → .digits|ε

optional_exponent → (E(+| - | ε)digits) |ε

num → digits optional_fraction optional_exponent

Дане визначення говорить, що optional_fraction або являє собою десяткову крапку, за якою слідує одна або кілька цифр, або цей фрагмент відсутній (є порожнім рядком). У випадку наявності optional_exponent являє собою Е, за яким слідує необов'язковий знак + або - і одна або кілька цифр. Помітимо, що за крапкою повинна випливати цифра, тобто запис 1. некоректний, на відміну від запису 1.0.

2.2.5 Скорочення

Деякі конструкції зустрічаються в регулярних виразах настільки часто, що для них уведені спеціальні скорочення.

1. Один або кілька екземплярів. Унарний постфіксний оператор ⁺ означає "один або більше екземплярів". Якщо r - регулярний вираз, що означає мову L(r), то (r)⁺ являє собою регулярний вираз, що описує мову (L(r))⁺. Таким чином, регулярний вираз а⁺ описує множину всіх рядків з одного або більше а. Оператор ⁺ має той же пріоритет й асоциативність, що й оператор ^*.

Дві алгебраїчних тотожності r^*=r⁺|ε й r⁺=rr^* зв'язують замикання Кліні й позитивне замикання.

2. Нуль або один примірник. Унарний постфіксний оператор ? означає "нуль або один примірник". Запис r? являє собою скорочений запис r|ε. Якщо r — регулярний вираз, то (r)? - регулярний вираз, що позначає мову L(r)U{ε}. Наприклад, використовуючи оператори ⁺ й ?, ми можемо переписати регулярний визначення для num із приклада 2.5 як

digit → 0 | 1 | … |9

digits → digit ⁺

optional_ffaction → (.digits)?

optional_exponent → (E(+| -)?digits)?

num → digits optional_fraction optional_exponent

3. Класи символів. Запис [abc], де a, b і с — символи алфавиту, означає регулярний вираз a | b | с. Скорочений клас символів типу [a-z] означає регулярний ви­раз а | b | . . . | z. З використанням класів символів можна описати ідентифікатори як рядки, задані регулярним виразом [A-Za-z] [A-Za-z0-9]^*.