Регулярные выражения и синтаксические диаграммы
Многие языковые конструкции удобно описываются регулярными выражениями. Эти выражения вводятся через понятие "регулярное множество".
Определение. Пусть - конечный алфавит. Регулярное множество в алфавите определяется рекурсивно следующим образом:
1) - регулярное множество;
2) {e}-регулярное множество;
3) {a}-регулярное множество для всех ;
4) если P и Q -регулярные множества, то регулярными являются
множества:
(объединение);
PQ (конкатенация);
(итерация), где итерация множества P определяется так:
5) ничто другое не является регулярным множеством в алфавите .
Определение. Регулярные выражения в алфавите обозначают регулярные множества и определяются следующим образом:
1) - обозначает пустое множество ;
2) е - обозначает множество {e};
3) если , то а - обозначает {a};
4) если p и q обозначают P и Q соответственно, то
(p+q) - обозначает ,
(pq) - обозначает PQ,
- обозначает ;
5) ничто другое не является регулярным выражением.
Замечания:
1. Можно показать, что .
2. Лишние скобки могут устраняться из выражений, если это не приводит к недоразумениям.
3. Приоритеты операций: "*", "конкатенация", "+".
Регулярные выражения имеют следующие алгебраические свойства: если - регулярные выражения, то:
- играет роль нуля ( свойство 8);
е - играет роль единицы (свойство 7).
Цепочки символов, образующие лексемы языков программирования, почти всегда оказываются регулярными множествами и представимы в виде соответствующих регулярных выражений . Для некоторых из лексем представление их регулярными выражениями оказывается слишком громоздким. Для более компактного описания лексем обычно используют расширенные регулярные выражения .
Определение. Расширенные регулярные выражения и множества, которые они обозначают определяются рекурсивно следующим образом :
1. Если R - регулярное выражение, то оно является расширенным и будет обозначать множество R .
2. Если R - расширенное регулярное выражение , то:
а) R+ - расширенное регулярное выражение , обозначающее множество RR* (R+ = RR* ) ;
б) R*n - расширенное регулярное выражение , обозначающее множество {e} R RR ... Rn ( или R*n = );
в) R+n - расширенное регулярное выражение , обозначающее множество R RR ... Rn ( или R+n = ).
3. Если R1 и R2 - расширенные регулярные выражения , то R1 - R2 и R1R2 - расширенные регулярные выражения, обозначающие следующие множества: R1 - R2 = { x / xR1 и xR2 }; R1R2 = { x / xR1 и xR2 }.
4. Ничто другое не является расширенным регулярным выражением.
Пример 4.1. Пусть требуется описать идентификаторы и константы языка при помощи регулярных определений: Описание идентификаторов: <буква> = A | B | ... | Z <цифра> = 0 | 1 | ... | 9 < идентификатор> = <буква> ( <буква> / <цифра>)*8
В практике разработки формальных языков для их описания нередко используют синтаксические диаграммы. Синтаксическая диаграмма является эквивалентным представлением грамматики языка и в ряде случаев она оказывается предпочтительнее в силу своей большей наглядности и компактности, так как это графическое описание синтаксиса языка. Название языковых конструкций пишется в левой части, а справа в отображаются возможные символы алфавита, в название конструкции. Для обозначение вариантов граф разветвляется, для обозначения повторов организуется петля.
Пример . Пусть задано регулярное определение , описывающее вещественные константы где Ц - терминальный символ Ц{0,1,...,9}.