Построение регулярных выражений

Все алгебры начинаются с некоторых элементарных выражений. Обычно это константы и/или переменные. Применяя определенный набор операторов к этим элементарным выражений и уже построенным выражениям, можно конструировать более сложные выражения. Обычно необходимо так же иметь некоторые методы группирования операторов и операндов, например, с помощью скобок.

Алгебра регулярных выражений строится по такой же схеме: используются константы и переменные для обозначения языков и операторы для обозначения трёх операций из раздела 1.1. Регулярные выражения можно определить рекурсивно. В этом определении не только характеризуются правильные регулярные выражения, но и для каждого регулярного выражения  описывается представленный им язык, который обозначается через

Базис состоит из трех частей:

. Константы ε и Ø Являются регулярными выражениями, определяющими языки {ε} и Ø, соответственно, т.е.. и

. Если  - произвольный символ, то  - регулярное выражение, определяющее язык . Т.е. .

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

Лексический анализ

Одним из наиболее ранних применений регулярных выражений было использование их для спецификации компонента компилятора, называемого “лексическим анализатором”. Этот компонент сканирует исходную программу и распознает все лексемы, т.е. подцепочки последовательных символов, логически составляющие единое целое. Типичными примерами лексем являются ключевые слова и идентификаторы, но существует и множество других примеров.

Unix-команда lex и ее GNU-версия flex получают на вход список регулярных выражений в стиле UNIX, за каждым из которых в фигурных скобках следует код, указывающий, что должен делать лексический анализатор, если найдет экземпляр такой лексемы. Такая система называется генератором лексического анализатора, поскольку на ее вход поступает высокоуровневое описание лексического анализатора и по этому описанию она создает функцию, которая представляет собой работающий лексический анализатор.

Такие команды, как lex и flex, оказались очень удобными, поскольку мощность нотации регулярных выражений необходима и достаточна для описания лексем. Эти команды способны использовать процедуру преобразования регулярного выражения в детерминированный конечный автомат для того чтобы генерировать эффективную функцию, разбивающую исходную программу на лексемы. Они превращают задачу построения лексического анализатора в “послеобеденную работу”, тогда как создания этих основанных на регулярных выражениях средств построение лексического анализатора вручную могло занимать несколько месяцев. Кроме того, если по какой-либо причине возникает необходимость модифицировать лексический анализатор, то намного проще изменить одно или два регулярных выражения, чем забираться внутрь загадочного когда, чтобы исправить дефект.

ПРАКТИЧЕСКАЯ ЧАСТЬ