Representação de gramáticas livres de contexto

Toda gramática livre de contexto é equivalente a uma gramática na Forma Normal de Chomsky, onde todas as produções podem ser colocadas nas formas

$$A \rightarrow B C$$

$$A \rightarrow a$$

É possível representar esse tipo de gramática usando outros mecanismos de especificação no lugar da notação matemática de conjuntos. Dois mecanismos tipicamente utilizados são a notação BNF e a notação de grafos sintáticos.

A notação BNF (Backus-Naur Form) introduz uma forma de representação textual para descrever gramáticas livres de contexto. BNF foi inicialmente desenvolvida para especificar a linguagem Algol 60, uma das predecessoras da linguagem C.

O principal operador dessa linguagem é o operador binário $::=$, que permite descrever as produções da gramática. O operando do lado esquerdo do operador é o símbolo não-terminal; do lado direito, a sua expansão, que pode conter símbolos terminais e não-terminais.

Na notação BNF, os símbolos não-terminais são delimitados por colchetes angulares, < e >. Por exemplo, a regra

$$<expr> \quad ::= \; ( <expr> )$$

define que uma expressão entre parênteses (o lado direito do operador) pode ser reduzido simplesmente a uma expressão (o símbolo não-terminal do lado esquerdo).

A notação BNF também introduz um conjunto de operadores destinados a simplificar a representação das regras da gramática que envolvam alternativas, repetições e combinações. Esses operadores são descritos na seqüência.

O operador | (ou) permite expressar em uma mesma regra produções alternativas. Por exemplo, a regra

$$<S> \quad ::= \; A \vert B$$

equivale às duas regras

$$<S> ::= \; A$$

$$<S> ::= \; B$$

O operador [ ] (opcional) permite expressar zero ou uma ocorrência do símbolo especificado. Por exemplo, a regra

$$<S> \quad ::= \; [ \alpha ]$$

equivale a

$$<S> ::= \; \varepsilon$$

$$<S> ::= \; \alpha$$

onde $\varepsilon$ representa a string vazia.

O operador ( | ) (fatoração) permite expressar a combinação de símbolos alternativos, como em

$$<S> \quad ::= \; a (b \mid c) d$$

que equivale a

$$<S> ::= \; a b d$$

$$<S> ::= \; a c d$$

O operador * (repetição), assim como para expressões regulares, expressa 0 ou mais ocorrências do símbolo. Por exemplo, a regra

$$<S> \quad ::= \; \alpha^\ast$$

equivale a

$$<S> ::= \; \varepsilon$$

$$<S> ::= \; \alpha \; <S>$$

Assim, a ocorrência do padrão no lado direito de uma produção equivale a $\varepsilon \mid \alpha \mid \alpha\alpha \mid \alpha\alpha\alpha \mid \dots$

O operador $\{ \parallel \}^\ast$ (concatenação) permite expressar a repetição múltipla de símbolos concatenados. Por exemplo, a regra

$$<S> \quad ::= \; \{ A \parallel B \}^\ast$$

equivale a

$$<S> ::= \; A <t>$$

$$<t> ::= \varepsilon$$

$$<t> ::= B A <t>$$

Outro tipo de notação usual para gramáticas é a notação de grafos sintáticos. Esta notação tem o mesmo poder de expressão de BNF, porém define uma representação visual para as regras de uma gramática livre de contexto.

Na notação de grafos sintáticos, símbolos terminais são representados por círculos e símbolos não-terminais, por retângulos. Setas são utilizadas para indicar a seqüência de expansão de um símbolo não-terminal. A Figura 3.1 apresenta alguns exemplos de regras já descritas para o BNF expressas através dessa notação.

Figura: Grafos sintáticos.