|
|
Ambigüidade
Uma gramática que produz mais de uma derivação à esquerda (ou direita) para uma sentença é dita como sendo ambígua. Isto é , uma gramática será ambígua se uma sentença w puder ser obtida a partir do símbolo inicial S por duas derivações à esquerda (ou direita) diferentes.
Uma gramática ambígua produz mais de uma árvore de sintaxe para pelo menos uma sentença .
Como exemplo de gramática ambígua, temos
E::= E + E | E * E | Numero
onde Numero representa qualquer número natural.
A sentença 3 + 4 * 5 pode ser gerada de duas formas usando derivação à esquerda:
E => E + E => Numero + E => 3 + E => 3 + E * E => 3 + Numero – E => 3 + 4 * E => 3 + 4 * Numero => 3 + 4 * 5
e
E => E * E => E + E * E => Numero + E * E => 3 + E * E=> 3 + Numero * E => 3 + 4 * E => 3 + 4 * Numero => 3 + 4 * 5
Admitimos que +, * e os números naturais são terminais.
Ambigüidade é indesejável porque ela associa dois significados diferentes a uma sentença como 3 + 4 * 5.
No primeiro caso, a primeira derivação é
E => E + E
o que implica que a multiplicação 4 * 5 será gerada pelo segundo E de "E + E". Isto significa que a multiplicação deverá ser avaliada antes da soma, já que o resultado de 4 * 5 é necessário para E + E. Então, esta derivação considera que * possui maior precedência do que +, associando 23 como resultado de 3 + 4 * 5.
No segundo caso, a primeira derivação é
E => E * E
e o primeiro E "E * E" deve gerar 3 + 4, pois + vem antes de * na sentença 3 + 4 * 5.
Sendo assim, esta seqüência de derivações admite que a soma deve ser calculada antes da multiplicação.
Portanto é considerado que + possui maior precedência do que *.
Associatividade e Precedência de Operadores
Na maioria das linguagens de programação, os operadores aritméticos +, -, * e / são associativos à esquerda. Isto é, "3 + 4 * 5" é avaliado como "(3 + 4) * 5". Quando um operando, como 4, estiver entre dois operadores de mesma precedência (neste caso, + e - ), ele será associado ao operador mais à esquerda, neste caso, +. Por isto dizemos que os operadores aritméticos são associados à esquerda.
A gramática
Expr ::= Expr + Term | Expr - Term | Term
Term ::= Term * Numero | Termo / Numero | Numero
com terminais +, -, * , / e Numero, associa todos os operadores à esquerda.
Para entender como + é associativo à esquerda, basta examinar a produções Expr ::= Expr + Term
Tanto Expr quanto Term podem produzir outras expressões. Mas Term nunca irá produzir um terminal +, como pode ser facilmente comprovado examinando-se a gramática.
Então, todos os símbolos + obtidos pela derivação de "Expr + Term" se originarão de Expr. Isto implica que, em uma derivação para obter uma sentença com mais de um terminal +, como 2 + 6+1, o não terminal Expr de "Expr + Term", deverá se expandir para resultar em todos os símbolos +, exceto o último:
Expr => Expr + Term => Expr + 1 => Expr + Term + 1 => 2 + 7 +1
Implícito nesta derivação está que, para fazer a soma Expr + Term primeiro devemos fazer todas as somas em Expr, que está à direita de + em "Expr + Term".
Então, os operadores + à esquerda devem ser utilizados primeiro do que os + da direita, resultando então em associatividade à esquerda.
Voltando à gramática, temos que a regra
Expr ::= Expr + Term | Expr - Term | Term
produz, no caso geral, uma seqüência de somas e subtrações de não terminais Term:
Expr => Term + Term - Term + Term - Term
Então, as somas e subtrações ocorrerão quando todos os não-terminais Term forem avaliados.
Examinando a regra para Term,
Term ::= Term * Numero | Term / Numero | Numero
descobrimos que Term nunca gerará + ou -. Então, para avaliar Expr, devemos avaliar uma
seqüência de somas e subtrações. E, antes disto, devemos executar todas as multiplicações e divisões geradas por Term. Isto implica que * e / possuem maior precedência do que + e -.
Um operador * possuirá maior precedência do que + quando * tomar os seus operadores antes do que +. Isto é , se houver um operando (número) entre um - e um +, este será ligado primeiro ao *.
Um exemplo é a expressão 3 + 4 * 5
onde 4 está entre + e * e é avaliada como = 3 + (4 * 5)