80
Теперь попробуем построить различные языки, используя в качестве
способа описания языка задание регулярного выражения. Напомним
основные правила построения регулярных выражений.
Отдельная буква алфавита представляет регулярное выражение, задающее
язык, состоящий из единственного слова, содержащего эту
единственную букву.
Специальное обозначение ε представляет регулярное выражение,
задающее язык, содержащий только пустое слово.
Если α
и β – два регулярных выражения, то (αβ) – тоже регулярное
выражение, представляющее катенацию соответствующих языков
(множество слов, образованных катенацией слов языка α со словами
языка β).
Если α и β – два регулярных выражения, то (α | β) – тоже регулярное
выражение, представляющее альтернацию соответствующих языков
(множество слов, образованных объединением слов языка α со
словами
языка β).
Если α – регулярное выражения, то (α *) – тоже регулярное выражение,
представляющее итерацию соответствующего языка (множество слов,
образованных объединением пустого слова и слов, образованных
катенацией произвольного количества слов языка α).
(α +) – регулярное выражение, являющееся просто сокращением для
(α (α *)) Эту операцию мы будем называть операцией непустой
итерации. Она
не всегда рассматривается в качестве одной из основных
операций, поскольку может быть выражена через обычную операцию
итерации. Верно и обратное: операцию итерации можно выразить с
помощью операции непустой итерации. Язык, задаваемый выражением
(α *), совпадает с языком, задаваемым выражением (ε | (α +))
Операциям катенации, альтернации и итерации, использующимся
для построения регулярных выражений,
обычно приписывают приоритет в
соответствии со следующими правилами: операцией с наивысшим
приоритетом считается операция итерации, следующей по старшинству
приоритетов является операция катенации, самой низкоприоритетной
операцией считается операция альтернации. Правила приоритетов
позволяют убирать скобки из регулярных выражений в тех случаях, когда
порядок выполнения операций определяется их приоритетами. Например,
регулярное выражение (ab+)* является
сокращенной записью выражения
((a(b+))*) и задает язык, содержащий слова, состоящие из букв a и b,
начинающиеся с буквы a, в которых после любой буквы a обязательно
стоит хотя бы одна буква b.
Мы опишем функции, которые позволят строить произвольные
регулярные выражения. Фактически мы будем выполнять операции не над
выражениями, а
над соответствующими языками, так что получившееся
выражение можно будет сразу использовать для проверки того,