Расширенная нотация для регулярных выражений

Регулярные выражения как языки

Регулярное выражение над алфавитом Σ — это цепочка символов в расширенном алфавите

Σ È {|, *, (, ) }.

Множество всех таких цепочек-выражений образует язык.

Возникает естественный вопрос, к языкам какого типа по классификации Н. Хомского этот язык принадлежит.

К автоматным? Тогда, быть может, правила записи регулярных выражений можно задать регулярным выражением? Нет, нельзя.

Синтаксис регулярных выражений может быть определен только контекстно-свободной, но не автоматной грамматикой. Вот эта грамматика:

R®a | RR | R* | R" | "R | (R) | ε

В этой записи есть ряд условностей:

а обозначает любой символ алфавита Σ,

запись "|", представляет знак «|», используемый в регулярных выражениях и совпадающий с аналогичным знаком, применяемым при записи грамматик.

Приведенная грамматика не отражает принятый для регулярных выражений порядок операций. Грамматика, трактующая структуру регулярного выражения в соответствии с приоритетами операций, может быть записана так:

R® T | R" | "T

T® M | RM

М® a | М* | (R) | ε.

Регулярные выражения - это строки символов, и тем они интересны как средство задания автоматных языков.

Но использование надстрочных знаков «*» и «⁺» несколько затрудняет запись выражений и их считывание компьютерной программой. Получили распространение другие варианты обозначений.

Повторение ноль или более раз обозначают фигурными скобками:

R* = {R}.

Используются также квадратные скобки, обозначающие необязательность заключенного в них выражения:

[R] = (R|ε).

Знаки «*» и «+» в этом случае уже не используются.

Соглашения о способах записи символов, с помощью которых строятся сами выражения (скобки, знак «|»), в случае, если они также входят в терминальный алфавит, могут быть разными.

Можно заключать такие метасимволы в кавычки «"». При необходимости записать саму кавычку ее заключают в апострофы «'», а апостроф, если нужно, записывается в кавычках.

По этим правилам регулярные выражения, обозначающие множество целых со знаком и множество идентификаторов, будут выглядеть так:

[ +|- ] ц { ц }

б { б|ц }.

На этом мы заканчиваем рассмотрение автоматных грамматик, в ходе которого удалось построить простые и эффективные методы распознавания автоматных языков.

С помощью автоматных грамматик определяется синтаксис простейших элементов языков программирования: идентификаторов, чисел, других констант, знаков операций и разделителей.