Entendendo ambiguidade na prática
Uma gramática é ambígua quando uma mesma string pode ser derivada por mais de uma árvore sintática diferente. Isso acontece frequentemente quando o autor da linguagem não define claramente a precedência de operadores ou a associatividade de construções. O caso clássico é a expressão a + b * c: sem regras de precedência, ela pode ser interpretada como (a + b) * c ou a + (b * c), e ambas as derivações são válidas pela gramática pura. O problema não é apenas acadêmico. Quando você passa uma gramática ambígua para um analisador LALR(1) como o usado pelo Bison ou YACC, o resultado é um conflito shift-reduce. O gerador para e mostra onde a ambiguidade existe, mas não resolve sozinho — ele só denuncia o defeito. O erro de compilação do parser é a primeira evidência prática de que sua gramática está mal formulada.
o'que é ambiguidade e por que ela quebra parsers
Ambiguidade é a propriedade de uma gramática livre de contexto em que existe pelo menos uma sentença com duas ou mais árvores de derivação distintas. Não é uma questão de o parser ser fraco ou forte demais — é a gramática em si que falha nesse aspecto. Um parsing table bem formado exige que cada célula tenha no máximo uma ação. Quando duas ações competem na mesma célula, a ambiguidade se materializa como conflito. Uma coisa que poucos iniciantes entendem: ambiguidade e conflito não são a mesma coisa. Uma gramática pode ser ambígua, mas você ainda assim conseguir construir um parser determinístico se usar tabelas de precedência manuais. É exatamente o que o Bison permite com %left, %right e %nonassoc. Você não resolve a ambiguidade da gramática — você a contorna impondo ordem de avaliação.
Outro ponto contraintuitivo: transformar uma gramática ambígua em uma não-ambígua equivalente não é sempre possível de forma sistemática. Existem linguagens intrinsecamente ambígias, o que significa que nenhuma gramática livre de contexto pode descrevê-las sem ambiguidade. A gramática de "else pendente" em C é um exemplo famoso. A solução prática não é eliminar a ambiguidade, mas sim adicionar regras que a tornem inofensiva — a regra do else mais próximo é uma convenção que elimina a ambiguidade sem mudar a gramática original. Eu tive um problema específico com uma gramática de expressões aritméticas que suportava funções com argumentos múltiplos, como foo(a, b). A ambiguidade surgia porque a vírgula também era usada em listas de parâmetros de outras construções. O parser gerava conflitos shift-reduce em todos os pontos de ocorrência de vírgula. A solução foi criar não-terminal separado para argumentos de função e um para listas genéricas, eliminando a sobreposição. Isso reduziu os conflitos de 47 para zero em uma única passada.
Como identificar e resolver ambiguidade
O primeiro passo é rodar a gramática pelo gerador de parser e observar os conflitos reportados. Cada conflito aponta para um non-terminal e uma posição específica onde o analisador não consegue decidir entre shift ou reduce. Anotar esses pontos e traçar a sentença problemática ajuda a entender o que está causando o duplo parsing. Uma abordagem direta é reformular a gramática introduzindo níveis de precedência como não-terminais distintos. Em vez de tratar todas as operações no mesmo nível, separe em camadas: expressão, termo, fator. Cada nível corresponde a um operador ou grupo de operadores com a mesma prioridade. Isso elimina a ambiguidade porque cada estrutura só pode ser reduzida em seu próprio nível.
👉 Clique no botão abaixo para saber mais sobre o assunto!
A segunda abordagem, mais rápida mas menos elegante, é usar diretivas de precedência. No Bison, você declara %left para operadores esquerdo-associativos, %right para direito-associativos e %nonassoc para operadores que não devem ser encadeados. A ordem dos declaradores define a prioridade: quanto mais baixo no arquivo, maior a precedência. Depois disso, o parser usa essas declarações para resolver automaticamente os conflitos. Se você estiver usando um parser gerador que não suporta declarações de precedência, como o ANTLR em modo padrão, a solução é diferente. O ANTLR resolve ambiguidade através de predicações sintáticas e regras de prioridade embutidas. Você pode usar {...}? para restringir qual alternativa deve ser escolhida com base em predicados avaliativos. Isso é mais flexível, mas também mais propenso a erros se não for usado com cuidado.
Um aviso importante: ambiguidade resolvida com declarações de precedência é uma solução pragmática, não uma correção teórica. A gramática continua ambígua em papel. Qualquer pessoa que legar seu arquivo de definição décadas depois vai precisar ler a documentação do parser para entender por que certos constructions funcionam. Documente a decisão explicitamente nos comentários do arquivo de gramática.
armadilhas comuns que eu vejo acontecer
O erro mais frequente é assumir que uma gramática ambígua funciona bem em todos os contextos. Um parser LL(1) rejeita gramáticas ambíguas completamente, então o erro aparece desde o início. Já um parser LR(1) ou LALR(1) pode produzir tabelas funcionando com conflitos ignorados, mas o comportamento resultante pode variar entre gerações ou opções de compilação. Isso gera bugs intermitentes que são pesadíssimos de reproduzir. Outro erro comum é tentar resolver ambiguidade adicionando regras recursivas extras. O efeito colateral é o aumento exponencial do tamanho da tabela de parsing, o que degrada o desempenho em tempo de execução. Se você notar que a tabela do parser cresceu 30% ou mais após uma modificação na gramática, provavelmente introduziu redundância desnecessária.
Ambiguidade em regras de reescrita também aparece em processadores de linguagem natural. Modelos de tag POS podem atribuir categorias diferentes à mesma palavra dependendo do contexto, e a ambiguidade lexical exige técnicas de desambiguação baseadas em estatística ou regras contextuais. O tratamento aqui é fundamentalmente diferente: você não tem a garantia de uma árvore sintática correta, então usa heurísticas em vez de decisões determinísticas. Se sua gramática tem muitos conflitos e a abordagem manual de reescrita está ficando inviável, considere mudar de estratégia. Parsadores tipo packrat com PEG (Parsing Expression Grammar) lidam com ambiguidade de forma diferente: a ordem das alternativas importa, e a primeira correspondência vence. Isso elimina a ambiguidade estrutural, mas muda o comportamento de sua gramática, então testar todas as entradas de validação é essencial antes de fazer a migração.
O tempo médio para diagnosticar e corrigir ambiguidades em uma gramática intermediária — digamos entre 20 e 50 regras — fica entre 45 minutos e 2 horas, dependendo de quão entrelaçadas estão as regras conflitantes. Gramáticas maiores que 100 regras costumam exigir refatoração parcial, não apenas ajustes pontuais.
