Expressões regulares

Gramáticas de tipo 3 são adequadas para representar algumas ``características locais'' de linguagens de programação, tais como definição de formatos de constantes, identificadores e palavras da linguagem. Por exemplo, uma típica definição de identificadores pode ser expressa em uma gramática

$$G = (\{letter,digit\},\{IDENT,REST\},P,IDENT)$$

com as seguintes produções em $P$:

$$IDENT \rightarrow letter \mid letter \; REST$$

$$REST \rightarrow letter \mid digit \mid letter \; REST \mid digit \; REST$$

Uma forma equivalente de definir símbolos ou sentenças que podem ser gerados por gramáticas de tipo 3 é através de expressões regulares. Dado um alfabeto $A$, então são expressões regulares em $A$:

1. um elemento de $A$ ou a string vazia.

   Se $P$ e $Q$ são expressões regulares em A, então também o serão:

2. $PQ$ ($P$ seguido de $Q$),

3. $P\mid Q$ ($P$ ou $Q$),

4. $P^\ast$ (0 ou mais ocorrências de $P$).

Expressões regulares podem ser vistas como expressões criadas a partir da aplicação de três operadores, concatenação, $\mid$ e $\ast$, sendo que $\ast$ tem a maior precedência e $\mid$, a menor. O operador $\mid$ é comutativo e associativo, enquanto que concatenação é associativa mas não comutativa.

No exemplo de identificadores, a expressão regular que descreve um identificador é

$$letter ( letter \mid digit ) ^\ast$$

onde parênteses são utilizados para adequar a precedência dos operadores.

Diz-se que uma expressão regular gera um conjunto regular. Um dado conjunto regular pode ser gerado por mais de uma expressão regular. Entre as propriedades que tornam expressões regulares atraentes do ponto de vista de programadores de sistema estão

1. Dada uma string, existe um algoritmo para determinar se ela é parte de um dado conjunto regular, e
2. Existe um algoritmo para determinar se duas expressões regulares geram o mesmo conjunto regular.

Entretanto, expressões regulares têm muitas limitações. Por exemplo, não é possível expressar através de uma gramática de tipo 3 ou de uma expressão regular sentenças na forma de delimitadores balanceados, tais como (()(())). Entretanto, tais sentenças podem ser facilmente descritas por gramáticas livres de contexto, tal como

$$S \rightarrow ( S )$$

$$S \rightarrow S S$$

$$S \rightarrow \varepsilon$$

Tais tipos de situações são recorrentes em linguagens de programação, onde pares de delimitadores -- tais como ( e ), { e }, [ e ] em C, ou begin e end em Pascal -- devem ocorrer de forma balanceada.