next up previous contents
Next: Analisadores sintáticos Up: Análise sintática Previous: Derivações canônicas   Sumário

Árvores gramaticais

Uma outra forma de representar a derivação associada ao reconhecimento de uma sentença é através da utilização de uma árvore gramatical. Nesse tipo de representação

  1. a raiz da árvore é o símbolo sentencial;
  2. as folhas da árvore são símbolos terminais, na seqüência em que ocorrem na sentença analisada; e
  3. os nós intermediários da árvore correspondem a símbolos não terminais, onde um nó cujo rótulo é $ P$ com filhos $ s_1, s_2,
\dots, s_n$ pode ocorrer apenas se houver uma regra $ P
\rightarrow s_1\;s_2\dots\;s_n$ na gramática.

Considere como exemplo a gramática da Figura 3.7. Uma árvore gramatical para uma sentença dessa gramática só poderá conter nós na forma especificada na Figura 3.11a, onde os nós correspondentes aos símbolos terminais estão destacados. A árvore gramatical para a sentença $ (id+id)\times id$ é apresentada na Figura 3.11b.

Figura: Árvore gramatical.
[Nós para a gramática de expressões]
\includegraphics[width=45mm]{grexp0.eps}
[Árvore para $ (id+id)\times id$]
\includegraphics[width=5cm]{ptree0.eps}

O problema de reconhecimento de uma sentença em uma gramática é essencialmente um problema de, dada uma sentença composta por tokens da linguagem, encontrar uma seqüência de reconhecimento mais à esquerda (leftmost parse), ou uma seqüência de reconhecimento mais à direita (rightmost parse), ou uma árvore gramatical para a expressão.

Na maior parte das situações, seqüências de reconhecimento e árvores gramaticais são únicas. Quando uma sentença pode ser gerada em uma gramática por mais de uma derivação mais à esquerda ou mais à direita ou tem mais de uma árvore gramatical, diz-se que a gramática que gera esta sentença é ambígua.

Considere a produção em uma gramática que representa um comando condicional de uma linguagem de programação, onde a cláusula else é opcional:

$\displaystyle cond$ $\displaystyle \rightarrow$   if$\displaystyle \; ( \; expr \; ) \; cmnd$    
$\displaystyle cond$ $\displaystyle \rightarrow$   if$\displaystyle \; ( \; expr \; ) \; cmnd \;$   else$\displaystyle \;cmnd$    

onde adicionalmente uma das definições possíveis de $ cmnd$ fosse estabelecida pela produção

$\displaystyle cmnd \rightarrow cond $

Para essas produções, o trecho de código

  if ( e1 ) if ( e2 ) c1 else c2
poderia dar margem a duas árvores gramaticais distintas, uma associada ao padrão adotado em linguagens de programação que associa o else ao último if possível (Figura 3.12a) e outra, não-usual porém gramaticalmente correta, que assume que o último if é que tem a cláusula else vazia (Figura 3.12b).

Figura: Árvores gramaticais para comando if-else.
[Interpretação usual]
\includegraphics{agif1.eps}
[Outra interpretação possível]
\includegraphics{agif2.eps}

Em alguns casos é possível transformar uma gramática ambígua em uma gramática sem ambiguidades. Entretanto, dada uma gramática qualquer não existe um algoritmo que indique se a gramática é ambígua ou não.


next up previous contents
Next: Analisadores sintáticos Up: Análise sintática Previous: Derivações canônicas   Sumário
Ivan L. M. Ricarte 2003-02-14