Derivações canônicas

Mesmo considerando expressões simples como essa do exemplo, há diversas opções para a seqüência de aplicação das regras que poderiam levar ou não ao reconhecimento da sentença, o que dificultaria a automação desse processo. Portanto, é importante ter formas sistemáticas de aplicações dessas regras que levem a uma conclusão sobre a validade ou não da sentença.

Essa forma sistemática de aplicação das regras de uma gramática é estabelecida através das derivações canônicas. Duas formas de derivação canônica são estabelecidas, as derivações mais à esquerda e mais à direita.

Na derivação mais à esquerda (leftmost derivation), a opção é aplicar uma regra da gramática ao símbolo não-terminal mais à esquerda da forma sentencial sendo analisada. A correspondente seqüência de regras aplicadas é denominada a seqüência de reconhecimento mais à esquerda, ou leftmost parse.

Similarmente, na derivação mais à direita (rightmost derivation) o símbolo não-terminal mais à direita é sempre selecionado para ser substituído usando alguma regra da gramática. No caso desse tipo de derivação, a seqüência de reconhecimento mais à direita, ou rightmost parse, é o reverso da seqüência de regras associada à derivação.

A Figura 3.10 apresenta as duas derivações canônicas para a sentença $(id+id)\times id$ segundo a gramática da Figura 3.7. A Figura 3.10a apresenta a derivação mais à esquerda, destacando em cada derivação qual o símbolo não-terminal que está sendo analisado. Para esse caso, a seqüência de reconhecimento mais à esquerda associada é

$$2,3,4,5,1,2,4,6,4,6,6.$$

Por sua vez, a seqüência de reconhecimento mais à direita, associada à derivação canônica da Figura 3.10b, é dada por

$$6,4,2,6,4,1,5,4,6,3,2.$$

Figura: Derivações canônicas para a sentença $(id+id)\times id$.

[derivação mais à esquerda]

$$\mathbf{E} \Rightarrow \mathbf{T}$$

$$\Rightarrow \mathbf{T} \times F$$

$$\Rightarrow \mathbf{F} \times F$$

$$\Rightarrow (\mathbf{E}) \times F$$

$$\Rightarrow (\mathbf{E}+T) \times F$$

$$\Rightarrow (\mathbf{T}+T) \times F$$

$$\Rightarrow (\mathbf{F}+T) \times F$$

$$\Rightarrow (id+\mathbf{T}) \times F$$

$$\Rightarrow (id+\mathbf{F}) \times F$$

$$\Rightarrow (id+id) \times \mathbf{F}$$

$$\Rightarrow (id+id) \times id$$

[derivação mais à direita]

$$\mathbf{E} \Rightarrow \mathbf{T}$$

$$\Rightarrow T \times \mathbf{F}$$

$$\Rightarrow \mathbf{T} \times id$$

$$\Rightarrow \mathbf{F} \times id$$

$$\Rightarrow (\mathbf{E}) \times id$$

$$\Rightarrow (E+\mathbf{T}) \times id$$

$$\Rightarrow (E+\mathbf{F}) \times id$$

$$\Rightarrow (\mathbf{E}+id) \times id$$

$$\Rightarrow (\mathbf{T}+id) \times id$$

$$\Rightarrow (\mathbf{F}+id) \times id$$

$$\Rightarrow (id+id) \times id$$

Observe que uma dada produção é utilizada o mesmo número de vezes nas duas derivações canônicas. Assim, a regra 1 foi usada uma vez; a regra 2, duas; a regra 3, uma; a regra 4, três; a regra 5, uma; e a regra 6, três vezes.