next up previous contents
Next: Árvores gramaticais Up: Análise sintática Previous: Reconhecimento de sentenças   Sumário

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 é

$\displaystyle 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

$\displaystyle 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]

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

[derivação mais à direita]

$\displaystyle \mathbf{E}$ $\displaystyle \Rightarrow \mathbf{T}$    
  $\displaystyle \Rightarrow T \times \mathbf{F}$    
  $\displaystyle \Rightarrow \mathbf{T} \times id$    
  $\displaystyle \Rightarrow \mathbf{F} \times id$    
  $\displaystyle \Rightarrow (\mathbf{E}) \times id$    
  $\displaystyle \Rightarrow (E+\mathbf{T}) \times id$    
  $\displaystyle \Rightarrow (E+\mathbf{F}) \times id$    
  $\displaystyle \Rightarrow (\mathbf{E}+id) \times id$    
  $\displaystyle \Rightarrow (\mathbf{T}+id) \times id$    
  $\displaystyle \Rightarrow (\mathbf{F}+id) \times id$    
  $\displaystyle \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.


next up previous contents
Next: Árvores gramaticais Up: Análise sintática Previous: Reconhecimento de sentenças   Sumário
Ivan L. M. Ricarte 2003-02-14