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
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
é apresentada na
Figura 3.11b.
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:
![]() |
![]() ![]() |
|
![]() |
![]() ![]() ![]() |
Para essas produções, o trecho de código
if ( e1 ) if ( e2 ) c1 else c2poderia 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).
[Interpretação usual]
[Outra interpretação possível]
|
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.