Аноним

Регулярные выражения: различия между версиями

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Регулярные выражения''' (Regular expressions) --- метод задания [[регулярные множес...)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Регулярные выражения''' ([[Regular expressions]]) ---
'''Регулярные выражения''' ([[Regular expressions]])
метод задания [[регулярные множества|''регулярных множеств'']].
метод задания [[регулярные множества|''регулярных множеств'']].


'''Регулярные выражения''' в некотором алфавите <math>\Sigma</math> и регулярные множества, которые они ''обозначают'', определяются рекурсивно следующим образом:
'''Регулярные выражения''' в некотором алфавите <math>\,\Sigma</math> и регулярные множества, которые они ''обозначают'', определяются рекурсивно следующим образом:


(1) <math>\emptyset</math>, <math>e</math> и <math>a</math> для любого <math>a\in\Sigma</math> --- регулярные
:(1) <math>\emptyset,\,e</math> и <math>\,a</math> для любого <math>a\in\Sigma</math> регулярные выражения, обозначающие регулярные множества <math>\emptyset,\,\{e\}</math> и <math>\,\{a\}</math>;
выражения, обозначающие регулярные множества <math>\emptyset</math>, <math>\{e\}</math> и <math>\{a\}</math>


(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>, <math>(pq)</math> и <math>(p)^*</math> ---
регулярные выражения, обозначающие множества <math>P\cup Q</math>, <math>PQ</math> и <math>P^*</math>
соответственно;


(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.


[Касьянов/95]


[[Категория: Теория формальных языков]]
[[Категория: Теория формальных языков]]