2.2.2 Рядки й мови

.

Термін мова (language) позначає будь-яку множину рядків над деяким фіксованим алфавитом. Таке визначення досить широке. Абстрактні мови типу Ø (порожня множина) або {ε} (множина, що містить тільки порожній рядок) також підходять під це визначення. Точно так само мовами є й множини всіх синтаксично коректних програм мовою Pascal, і всі граматично коректні речення природної мови (українською, англійської, тощо) — хоча дві останніх множини істотно складніше визначити.

Порожній рядок являє собою одиничний елемент стосовно операції конкатенації, тобто для будь-якого рядка s справедливе співвідношення sε = εs = s.

Якщо розглядати конкатенацію як операцію "множення", то можна визначити операцію "піднесення в степінь" у такий спосіб. Визначимо, що s°=ε, а для i>0 визначимо s^і як s^і-1s. Оскільки εs — просто s, то s¹=s. Відповідно, s²=ss, s³=sss і т.д.

2.2.3 Операції над мовами

Є ряд важливих операцій, виконуваних над мовами. З погляду лексичного аналізу нас у першу чергу цікавлять об'єднання, конкатенація й замикання (рис. 2.4). Можна також узагальнити оператор піднесення в степень для мови, визначивши L⁰ як {ε}, a L^і — як L^і-1L. Таким чином, L^і являє собою L, конкатенований із самим собою і-1 раз.

Операція	Визначення
Об'єднання (union) L і М – LUM	LUM ={s|s ϵ L або s ϵ M}
Конкатенація (concatenation) L і М – LM	LM = {st|s ϵ L й t ϵ M}
Замикання Кліні (Kleene closure); або ітерація L – L*.	L*=ULі , i=0, ∞ L* позначає “нуль або більше конкатенацій L”
Позитивне замикання (positive closure).	L+=ULі , i=1, ∞ L+ позначає "одна або більше конкатенацій L"

Рис. 2.4. Визначення операцій над мовами

Приклад 2.2

Нехай L – множина {А, В,.. . , Z, а, b, ..., z}, а D — множина {0, 1, 2, ..., 9}. Ми можемо розглядати множини L і D подвійно. З одного боку, L являє собою алфавит, що складається з набору прописних і малих літер, a D — алфавит, що складається із цифр. З іншого боку, оскільки символ можна розглядати як рядок одиничної довжини, множини L й D являють собою кінцеві мови. От кілька прикладів нових мов, створених з L і D із застосуванням операторів, наведених на рис. 2.4.

1. LUD являє собою множину букв і цифр.

2. LD — множина рядків, що складаються з букви, за якої слідує цифра.

3. L⁴ — множина всіх чотирибуквених рядків.

4. L^* — множина всіх рядків з букв, включаючи порожній рядок ε.

5. L(LUD)^* — множина всіх рядків з букв і цифр, що починаються з букви.

6. D⁺ — множина всіх рядків з однієї або декількох цифр.

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

У визначенні токенів важливу роль грають регулярні вирази. Кожен шаблон відповідає множини рядків, так що регулярні вирази можна розглядати як імена таких множин.

В Pascal ідентифікатор являє собою букву, за якої слідує нуль або кілька букв або цифр; отже, ідентифікатор є елементом множини, визначеного в п. 5 приклада 2.2. У цьому розділі представлений спосіб запису, іменований регулярними виразами, що дозволяє точно визначати подібні множини. За допомогою цього способу запису можна визначити ідентифікатори Pascal як

letter(letter|digit)*

Вертикальна риса означає "або", дужки використовуються для групування підвиразів, а безпосереднє сусідство letter із частиною виразу, що залишилася, означає конкатенацію.

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

Розглянемо правила, які визначають регулярні вирази над алфавитом V.

1. ε являє собою регулярний вираз, що позначає {ε}, тобто множина, що містить порожній рядок.

2. Якщо а є символом з V, то а — регулярний вираз, що позначається {а}, тобто множина, що містить рядок а. Хоча ми використаємо ту саму запис, технічно регулярний вираз а відрізняється від рядка а й символу а. Говоримо ми про регулярний вираз, рядок або символ - стає зрозуміло з контексту.

3. Припустимо, що r и s — регулярні вирази, що позначають мови L(r) і L(s). Тоді

• (r)|(s) являє собою регулярний вираз, що позначає L(r)UL(s).

• (r)(s) — регулярний вираз, що позначає L(r)L(s).

• (r)^* - регулярний вираз, що позначає (L(r))^*.

• (r) — регулярний вираз, що позначає L(r).

Мова, що задається регулярним виразом, називається регулярною множиною.

Визначення регулярного виразу являє приклад рекурсивного визначення. Правила (1) і (2) формують базис визначення; використаємо термін базовий символ для ε або символу з алфавиту V, що з'являються в регулярному виразі. Правило (3) забезпечує крок індукції.

Зайві дужки в регулярному виразі можуть бути усунуті, якщо прийняти наступні угоди.

1. Унарний оператор ^* має вищий пріоритет і лівоасоціативен.

2. Конкатенація має другий по значимості пріоритет і лівоасоціативна.

3. | (об'єднання) має нижчий пріоритет і лівоасоціативно.

При цих угодах запис (а)|((b)^*(с)) еквівалентний а|b^*с. Обидва вирази позначають множину рядків, які являють собою або єдиний символ а, або нуль або кілька b, за якими слідує єдиний символ с.

Приклад 2.3

Нехай V = {a,b}.

1. Регулярний вираз а|b позначає множину {а,b}.

2. Регулярний вираз (а|b)(а|b) — {аа, ab, ba, bb}, множина всіх рядків з а й b довжини 2. Інший регулярний вираз для тієї ж множини — aa|ab|ba|bb.

3. Регулярний вираз а^* — множина всіх рядків з нуля або більше а, тобто {ε, а, аа, ааа,...}.

4. Регулярний вираз (а|b)^* позначає множину всіх рядків, що містять нуль або кілька екземплярів а й b, тобто множина всіх рядків з а й b. Інший регулярний вираз для цієї множини — (а^*|b^*)^*.

5. Регулярний вираз а|а^*b — множина, що містить рядок а й всі рядки, що­ складаються з нуля або декількох а, за якими слідує b.

Якщо два регулярних вирази r и s задають ту ж саму мову, то r й s називаються еквівалентними, тобто r = s. Наприклад, (а|b)=(b|а).

Є ряд алгебраїчних законів, використовуваних для перетворення регулярних виразів в еквівалентні. На рис. 2.5 наведено деякі із цих законів для регулярних виразів r, s й t.

Аксіома	Опис
r|s = s|r	Оператор | комутативен
r | (s|t)=(r|s)|t (rǀs)ǀt	Оператор | асоціативен
(rs)t = r(st)	Конкатенація асоціативна
r(s|t) = rs|rt (s|t) r = sr|tr	Конкатенація дистрибутивна над |
εr = r rε = r	ε є одиничним елементом стосовно конкатенації
r* = (r|ε) *	Зв'язок між * й ε
r** = r*	Оператор * ідемпотентний

Рис. 2.5. Алгебраїчні властивості регулярних виразів