Expressões regulares

As expressões regulares foram introduzidas em 1956 por Stephen Kleene.

O conjunto das expressões regulares sobre um alfabeto A define-se indutivamente da seguinte forma:

1. () é uma expressão regular (ER) que representa a LR {} (∅).

2. Qualquer que seja o a ∈ A, a é uma ER que representa a LR {a}.

3. Se e1 e e2 são ER representando respectivamente as LR L1 e L2 , então (e1 | e2) é uma ER representando a LR L1 ∪ L2 .

4. Se e1 e e2 são ER representando respectivamente as LR L1 e L2 , então (e1e2) é uma ER representando a LR L1 · L2.

5. Se e1 é uma ER representando a LR L1 , então e*1 é uma ER representando a LR (L1)*.

6. Nada mais é expressão regular.

A evidente semelhança entre LR e ER não é casual. Ambas expressam gramáticas regulares.

Uma expressão regular, tal como uma gramática regular, gera uma linguagem regular.

• Logo, é possível converter uma gramática regular numa expressão regular que represente a mesma linguagem e vice-versa.

Tal como as gramáticas regulares, as expressões regulares são fechadas nas suas operações.

Expressões regulares: exemplos

P: Determine uma ER que represente o conjunto de números binários começados por 1 e terminados por 0.

R: 1(0|1)*0

P: Determine uma ER que representa as sequências definidas sobre o alfabeto A = {a;b;c} que satisfazem o requisito de qualquer símbolo b ter um a imediatamente à sua esquerda e um c imediatamente à sua direita.

R: (a|abc|c)*

P: Determine uma ER que represente as sequências binárias com um numero par de zeros.

R: 1*(01*01*)*

Simplificação notacional

Para simplificar a escrita das expressões regulares (de forma análoga às expressões aritméticas) existe uma precedência bem definida na aplicação dos diferentes operadores.

A ordem decrescente de precedência é a seguinte:

1. Parêntesis;

2. Fecho de Kleene (*);

3. Concatenação (implícita ou . )

4. Escolha (|).

A utilização destas precedências permite simplificar as ER.

• e = (((1*)0)(1*))0)(1*) <=> e = 1*01*01* e1 | e2 · e3* = e1 | (e2 · (e3*))

Expressões regulares: exemplos

Recuperando os exemplos anteriores.

P: Determine uma ER que represente o conjunto de números binários começados por 1 e terminados por 0.

R: 1(0|1)*0 <=> (1((0|1)*))0

P: Determine uma ER que representa as sequências definidas sobre o alfabeto A = {a;b;c} que satisfazem o requisito de qualquer símbolo b ter um a imediatamente à sua esquerda e um c imediatamente à sua direita.

R: (a|abc|c)* <=> ((a | ((ab)c)) |c)*

P: Determine uma ER que represente as sequências binárias com um numero par de zeros.

R: 1*(01*01*)* <=> (1*)(((((0(1*))0)(1*)))*)

Outras extensões notacionais

Existem outras extensões a expressões regulares (utilizadas, por exemplo, em muitos comandos UNIX):

Símbolo	Significado
.	Um símbolo qualquer diferente de \n
^	palavra vazia no início de linha
$	palavra vazia no fim de linha
\<	palavra vazia no início de palavra
\>	palavra vazia no fim de palavra

Gramática para expressões regulares

Podemos definir a linguagem das expressões regulares com uma gramática (A é o conjunto dos caracteres):

• ER -> ER '|' Term {alternativa}

• ER -> Term

• Term -> Term Primary {concatenação}

• Term -> Primary

• Primary -> Factor '*' {iteração}

• Primary -> Factor

• Factor -> '('ER')' {grupo}

• Factor -> A {qualquer terminal}