Регулярные выражения: различия между версиями
Перейти к навигации
Перейти к поиску
KVN (обсуждение | вклад) (Создана новая страница размером '''Регулярные выражения''' (Regular expressions) --- метод задания [[регулярные множес...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Регулярные выражения''' ([[Regular expressions]]) | '''Регулярные выражения''' ([[Regular expressions]]) — | ||
метод задания [[регулярные множества|''регулярных множеств'']]. | метод задания [[регулярные множества|''регулярных множеств'']]. | ||
'''Регулярные выражения''' в некотором алфавите <math>\Sigma</math> и регулярные множества, которые они ''обозначают'', определяются рекурсивно следующим образом: | '''Регулярные выражения''' в некотором алфавите <math>\,\Sigma</math> и регулярные множества, которые они ''обозначают'', определяются рекурсивно следующим образом: | ||
(1) <math>\emptyset | :(1) <math>\emptyset,\,e</math> и <math>\,a</math> для любого <math>a\in\Sigma</math> — регулярные выражения, обозначающие регулярные множества <math>\emptyset,\,\{e\}</math> и <math>\,\{a\}</math>; | ||
выражения, обозначающие регулярные множества <math>\emptyset | |||
(2) если <math>p</math> и <math>q</math> | :(2) если <math>\,p</math> и <math>\,q</math> — регулярные выражения, обозначающие регулярные множества <math>\,P</math> и <math>\,Q</math> соответственно, то <math>\,(p+q),\,(pq)</math> и <math>\,(p)^*</math> — регулярные выражения, обозначающие множества <math>P\cup Q,\,PQ</math> и <math>\,P^*</math> соответственно; | ||
множества <math>P</math> и <math>Q</math> соответственно, то <math>(p+q) | |||
регулярные выражения, обозначающие множества <math>P\cup Q | |||
соответственно; | |||
(3) других регулярных выражений нет. | :(3) других регулярных выражений нет. | ||
Обычно используется запись <math>p^+</math> для сокращенного обозначения | Обычно используется запись <math>\,p^+</math> для сокращенного обозначения | ||
выражения <math>pp^*</math> и, кроме того, устраняются из регулярных выражений | выражения <math>\,pp^*</math> и, кроме того, устраняются из регулярных выражений | ||
лишние скобки там, где это не может привести к недоразумениям. | лишние скобки там, где это не может привести к недоразумениям. | ||
(Предполагается, что наивысшим приоритетом обладает операция <math>^*</math>, | (Предполагается, что наивысшим приоритетом обладает операция <math>\,^*</math>, | ||
затем идет конкатенация и далее операция <math>+</math>.) | затем идет конкатенация и далее операция <math>\,+</math>.) | ||
Говорят, что два регулярных выражения ''равны'' (=), если они | Говорят, что два регулярных выражения ''равны'' (<math>\,=</math>), если они | ||
обозначают одно и то же ''регулярное множество''. | обозначают одно и то же ''регулярное множество''. | ||
Используется и другие методы задания языков, каждый из которых определяет в | Используется и другие методы задания языков, каждый из которых определяет в | ||
точности регулярные множества. Среди них | точности регулярные множества. Среди них — | ||
[[автоматная грамматика|''автоматные грамматики'']], | [[автоматная грамматика|''автоматные грамматики'']], | ||
[[праволинейная грамматика|''праволинейные грамматики'']], | [[праволинейная грамматика|''праволинейные грамматики'']], | ||
| Строка 32: | Строка 28: | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
Текущая версия от 12:03, 31 августа 2011
Регулярные выражения (Regular expressions) — метод задания регулярных множеств.
Регулярные выражения в некотором алфавите [math]\displaystyle{ \,\Sigma }[/math] и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом:
- (1) [math]\displaystyle{ \emptyset,\,e }[/math] и [math]\displaystyle{ \,a }[/math] для любого [math]\displaystyle{ a\in\Sigma }[/math] — регулярные выражения, обозначающие регулярные множества [math]\displaystyle{ \emptyset,\,\{e\} }[/math] и [math]\displaystyle{ \,\{a\} }[/math];
- (2) если [math]\displaystyle{ \,p }[/math] и [math]\displaystyle{ \,q }[/math] — регулярные выражения, обозначающие регулярные множества [math]\displaystyle{ \,P }[/math] и [math]\displaystyle{ \,Q }[/math] соответственно, то [math]\displaystyle{ \,(p+q),\,(pq) }[/math] и [math]\displaystyle{ \,(p)^* }[/math] — регулярные выражения, обозначающие множества [math]\displaystyle{ P\cup Q,\,PQ }[/math] и [math]\displaystyle{ \,P^* }[/math] соответственно;
- (3) других регулярных выражений нет.
Обычно используется запись [math]\displaystyle{ \,p^+ }[/math] для сокращенного обозначения выражения [math]\displaystyle{ \,pp^* }[/math] и, кроме того, устраняются из регулярных выражений лишние скобки там, где это не может привести к недоразумениям. (Предполагается, что наивысшим приоритетом обладает операция [math]\displaystyle{ \,^* }[/math], затем идет конкатенация и далее операция [math]\displaystyle{ \,+ }[/math].)
Говорят, что два регулярных выражения равны ([math]\displaystyle{ \,= }[/math]), если они обозначают одно и то же регулярное множество.
Используется и другие методы задания языков, каждый из которых определяет в точности регулярные множества. Среди них — автоматные грамматики, праволинейные грамматики, регулярные грамматики, конечные автоматы, детерминированные конечные автоматы.
Литература
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
- Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.