Gramática ambígua

Em ciência da computação, uma gramática livre de contexto é dita ser uma gramática ambígua se existe uma cadeia que pode ser gerada pela gramática em mais de um caminho (ou seja, a cadeia admite mais de uma árvore sintática ou, equivalentemente, mais de uma derivação mais à esquerda). Uma linguagem livre de contexto é inerentemente ambígua se todas as gramáticas livres de contexto geradoras desta linguagem são ambíguas.

Algumas linguagens de programação têm gramáticas ambíguas; neste caso, a informação semântica é necessária para selecionar a árvore sintática pretendida de uma construção ambígua. Por exemplo, em C o seguinte:

x * y ;

pode ser interpretado como:

• A declaração de um identificador chamado y do tipo ponteiro para x, ou
• Uma expressão na qual x é multiplicado por y e então o resultado é descartado.

Para escolher corretamente entre as duas interpretações possíveis, um compilador deve consultar a sua tabela de símbolos para descobrir se x foi declarada como um nome de typedef que é visível neste momento.

Exemplo

A gramática livre de contexto

A → A + A | A − A | a

é ambígua já que existem duas derivações mais à esquerda para a cadeia a + a + a:

	A	→ A + A		A	→ A + A
		→ a + A			→ A + A + A (Primeiro A é substituído por A+A. A substituição do segundo produziria uma derivação similar)
		→ a + A + A			→ a + A + A
		→ a + a + A			→ a + a + A
		→ a + a + a			→ a + a + a

Como outro exemplo, a gramática é ambígua uma vez que 2 existem duas árvores sintáticas para a cadeia a + a − a:

A linguagem que ele gera, porém, não é inerentemente ambígua, o que se segue é uma gramática não ambígua gerando a mesma linguagem:

A → A + a | A − a | a

Reconhecendo gramáticas ambíguas

A questão geral de saber se um gramática não é ambígua é indecidível. Nenhum algoritmo pode existir para determinar a ambiguidade de uma gramática porque o indecidível Problema da Correspondência de Post pode ser codificado como um problema de ambiguidade. Pelo menos, há ferramentas que implementam algum procedimento de semi-decisão para detectar ambiguidade de gramáticas livres de contexto, ver por exemplo (Axelsson, Heljanko & Lange 2008).

Existe uma evidente dificuldade na análise de uma gramática ambígua por um analisador determinístico (ver gramática livre de contexto determinística) mas a análise não determinística impõe uma penalidade de grande eficiência. A maioria das construções de interesse para análise pode ser reconhecida por gramáticas não ambíguas. Algumas gramáticas ambíguas podem ser convertidas para gramáticas não ambíguas, mas não há um procedimento geral para fazer isto, assim como não existe algoritmo para a detecção de gramáticas ambíguas. Compiladores como o YACC incluem recursos para tornar não ambíguas alguns tipos de ambiguidade, por exemplo, usando as restrições de precedência e de associatividade.

Linguagens inerentemente ambíguas

Ambiguidade inerente foi mostrada pela primeira vez em 1961 por Rohit Parikh em uma pesquisa do relatório MIT Parikh (1961) e mais tarde em uma versão da revista Parikh (1966)).

Embora algumas linguagens livres de contexto (o conjunto das cadeias que podem ser geradas por uma gramática) tenham gramáticas ambíguas e não ambíguas, existem linguagens livres de contexto para o qual gramáticas livres de contexto não ambíguas podem existir. Um exemplo de um linguagem inerentemente ambígua é a união de $\{a^{n}b^{m}c^{m}d^{n}|n,m>0\}$ com $\{a^{n}b^{n}c^{m}d^{m}|n,m>0\}$. Este conjunto é livre do contexto, já que a união de duas gramáticas livres de contexto é sempre livre de contexto. Mas Hopcroft & Ullman (1979) dão uma prova de que não há maneira de analisar sequências de forma não ambígua subconjunto (não livre de contexto) $\{a^{n}b^{n}c^{n}d^{n}|n>0\}$, que é a interseção destas duas linguagens.

Referências

• Parikh, Rohit. (janeiro de 1961). Language-generating devices. [S.l.]: Quarterly Progress Report, Research Laboratory of Electronics, MIT 

• Gross, Maurice. (1964). Inherent ambiguity of minimal linear grammars. 7:3. [S.l.]: Information and Control. pp. 366–368 

• Parikh, Rohit. (1966). On Context Free Languages. 13. [S.l.]: Journal of the Association for Computing Machinery. pp. 570–81 

• Michael, Harrison. (1978). Introduction to Formal Language Theory. [S.l.]: Addison-Wesley 

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation 1st ed. [S.l.]: Addison-Wesley 

• Hopcroft, John.; Mowani, Rajeev.; Ullman, Jeffrey. (2001). Introduction to Automata Theory, Languages and Computation (second edition). [S.l.]: Addison Wesley. 217 páginas 

• Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). «Analyzing Context-Free Grammars Using an Incremental SAT Solver». Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08), Reykjavik, Iceland. Col: Lecture Notes in Computer Science. 5126. [S.l.]: Springer-Verlag. pp. 410–422 

Ligações externas

• dk.brics.grammar - um analisador de ambiguidade de gramática.
• CFGAnalyzer - ferramenta para analisar gramáticas livres de contexto no que diz respeito à universalidade de linguagem, ambiguidade e propriedades semelhantes.