Por que as gramáticas ambíguas são ruins?

30

Entendo que, se existem 2 ou mais árvores de derivação esquerda ou direita, a gramática é ambígua, mas não consigo entender por que é tão ruim que todo mundo queira se livrar dela.

HIRAK MONDAL
fonte
1
Relacionado, mas não idêntico: softwareengineering.stackexchange.com/q/343872/206652 (aviso de isenção de responsabilidade: escrevi a resposta aceita)
marstato
Consulte também: " Localizando uma gramática inequívoca ".
Rob
1
De fato, a forma inequívoca é melhor para usos práticos, a forma inequívoca usa menos número de regras de produção e cria uma árvore menor em alta (portanto, o compilador eficiente leva menos tempo para analisar). A maioria das ferramentas fornece capacidade de resolver ambiguidade explicitamente fora da gramática lateral.
Grijesh Chauhan
3
"todo mundo quer se livrar dele". Bem, isso não é verdade. Em idiomas comercialmente relevantes, é comum ver a ambiguidade adicionada à medida que os idiomas evoluem. Por exemplo, o C ++ adicionou intencionalmente a ambiguidade std::vector<std::vector<int>>em 2011, que costumava exigir um espaço entre >>antes. A principal ideia é que essas linguagens têm muito mais usuários que fornecedores, portanto, corrigir um pequeno incômodo para os usuários justifica muito trabalho dos implementadores.
MSalters 11/06

Respostas:

52

Considere a seguinte gramática para expressões aritméticas: Considere a seguinte expressão: Qual é o seu valor? Aqui estão duas possíveis árvores de análise:

XX+XXXXXX/Xvarconst
abc

(X - X) - X insira a descrição da imagem aqui

De acordo com o da esquerda, devemos interpretar como , que é a interpretação usual. De acordo com o da direita, devemos interpretá-lo como , o que provavelmente não é o que se pretendia.abc(ab)ca(bc)=ab+c

Ao compilar um programa, queremos que a interpretação da sintaxe seja inequívoca. A maneira mais fácil de fazer isso é usar uma gramática inequívoca. Se a gramática for ambígua, podemos fornecer regras de desempate, como precedência do operador e associatividade. Essas regras podem ser expressas de maneira equivalente, tornando a gramática inequívoca de uma maneira particular.


Analise as árvores geradas usando o gerador de árvore de sintaxe .

Yuval Filmus
fonte
12
@HIRAKMONDAL O fato de a sintaxe ser ambígua não é um problema real. o problema é que as duas árvores de análise diferentes têm um comportamento diferente. Se o seu idioma possui uma gramática ambígua, mas todas as árvores de análise de uma expressão são semanticamente equivalentes, isso não seria um problema (por exemplo, tome o exemplo do Yuval e considere o caso em que é o seu único operador +).
Bakuriu
14
@Bakuriu O que você disse é verdade, mas "semanticamente equivalente" é uma tarefa difícil. Por exemplo, a aritmética de ponto flutuante não é realmente associativa (portanto, as duas árvores "+" não seriam equivalentes). Além disso, mesmo que a resposta tenha saído da mesma maneira, a ordem de avaliação indefinida é muito importante nos idiomas em que as expressões podem ter efeitos colaterais. Então, o que você disse é tecnicamente verdadeiro, mas, na prática, seria muito incomum que a ambiguidade de uma gramática não tivesse repercussões no uso dessa gramática.
Richard Rast 10/06
Atualmente, alguns idiomas verificam o excesso de números inteiros nas adições, portanto, mesmo a + b + c para números inteiros depende da ordem da avaliação.
gnasher729 10/06
3
Pior ainda, em alguns casos, a gramática não fornece nenhuma maneira de alcançar o significado alternativo. Eu já vi isso nas linguagens de consulta, nas quais a escolha da gramática de escape (por exemplo, o dobro do caractere especial para evitá-lo) impossibilita a expressão de certas consultas.
Stop Harming Monica
12

Em contraste com as outras respostas existentes [ 1 , 2 ], existe de fato um campo de aplicação, onde gramáticas ambíguas são úteis . No campo do processamento de linguagem natural (NLP), quando você deseja analisar a linguagem natural (NL) com gramáticas formais, você tem o problema de que o NL é inerentemente ambíguo em diferentes níveis [adaptado de Koh18, cap. 6.4]:

  • Ambuigidade sintática:

    Peter perseguiu o homem no carro esportivo vermelho

    Peter ou o homem estavam no carro esportivo vermelho?

  • Ambuigidade semântica:

    Peter foi ao banco

    Um banco para sentar ou um banco para retirar dinheiro?

  • Ambuigidade pragmática:

    Dois homens carregavam duas malas

    Eles carregavam as malas juntas ou cada homem carregava duas malas?

Diferentes abordagens para a PNL lidam de maneira diferente com o processamento em geral e em particular essas ambuigidades. Por exemplo, seu pipeline pode ter a seguinte aparência:

  1. Analisar NL com gramática ambígua
  2. Para cada AST resultante: execute a geração do modelo para gerar significados semânticos ambíguos e descartar ambiguidades sintáticas impossíveis da etapa 1
  3. Para cada modelo resultante: salve-o em seu cache.

Você faz esse pipeline para cada frase. Quanto mais texto, digamos, do mesmo livro que você processar, mais você poderá descartar modelos supérfluos impossíveis, que sobreviveram até a etapa 3, das frases anteriores.

Ao contrário da linguagem de programação, podemos abandonar o requisito de que toda sentença NL tenha semântica precisa. Em vez disso, podemos apenas contabilizar vários modelos semânticos possíveis durante a análise de textos maiores. De tempos em tempos, idéias posteriores nos ajudam a descartar ambiguidades anteriores.

Se você deseja sujar as mãos com analisadores capazes de produzir várias derivações para gramática ambígua, dê uma olhada na Estrutura gramatical . Além disso, [Koh18, cap. 5] tem uma introdução mostrando algo semelhante ao meu pipeline acima. Observe que, como [Koh18] são notas de aula, as notas podem não ser tão fáceis de entender por si mesmas sem as aulas.


Referências

[Koh18]: Michael Kohlhase. "Processamento de linguagem natural baseado em lógica. Semestre de inverno 2018/19. Notas de aula." URL: https://kwarc.info/teaching/LBS/notes.pdf . URL da descrição do curso: https://kwarc.info/courses/lbs/ (em alemão)

[Koh18, cap. 5]: Veja o capítulo 5, "Implementando fragmentos: estruturas gramaticais e lógicas", em [Koh18]

[Koh18, cap. 6.4] Veja o capítulo 6.4, "O papel computacional das ambiguidades", em [Koh18]

ComFreek
fonte
Muito obrigado .. Eu tinha a mesma dúvida e vc a limpou .. :)
HIRAK MONDAL
1
Sem mencionar problemas com o Buffalo buffalo buffalo Buffalo buffalo buffalo ... para um número adequado de buffalo
Hagen von Eitzen
Você escreve "em contraste", mas eu chamaria isso de o outro lado da moeda pelo que respondi. A análise de idiomas naturais com gramáticas ambíguas é tão difícil que os analisadores tradicionais não conseguem!
Davislor 10/06
1
@ComFreek Eu deveria ser mais preciso aqui. Uma breve olhada no GF (Obrigado pelo link!) Mostra que ele lê gramáticas sem contexto com três extensões (como permitir reduplicação) e retorna uma lista de todas as derivações possíveis. Algoritmos para fazer isso existem desde os anos 50. No entanto, ser capaz de lidar com CFGs totalmente gerais significa que seu pior tempo de execução aumenta e, na prática, mesmo ao usar um analisador geral como GLL, os engenheiros de software tentam usar um subconjunto de CFGs, como gramáticas LL, que podem ser analisado com mais eficiência.
Davislor 11/06
1
@ComFreek Portanto, os computadores não podem lidar com CFG (embora as línguas naturais não sejam realmente livres de contexto e a tradução automática realmente útil use técnicas completamente diferentes). É que, se você precisar que seu analisador lide com ambiguidade, isso exclui certos atalhos que o tornariam mais eficientes.
Davislor 11/06
10

Mesmo se houver uma maneira bem definida de lidar com a ambiguidade (expressões ambíguas são erros de sintaxe, por exemplo), essas gramáticas ainda causam problemas. Assim que você introduz ambiguidade em uma gramática, um analisador não pode mais ter certeza de que a primeira correspondência obtida é definitiva. Ele precisa continuar tentando todas as outras maneiras de analisar uma declaração, para descartar qualquer ambiguidade. Você também não está lidando com algo simples como uma linguagem LL (1), portanto não pode usar um analisador simples, pequeno e rápido. Sua gramática possui símbolos que podem ser lidos de várias maneiras; portanto, você deve estar preparado para voltar muito.

Em alguns domínios restritos, é possível provar que todas as formas possíveis de analisar uma expressão são equivalentes (por exemplo, porque elas representam uma operação associativa). (a + b) + c = a + (b + c).

Davislor
fonte
9

Does IF a THEN IF b THEN x ELSE ymédia

IF a THEN
    IF b THEN
        x
    ELSE
        y

ou

IF a THEN
    IF b THEN x
ELSE
    y

? Também conhecido como o problema dos outros pendentes .

David Richerby
fonte
1
Esse é um bom exemplo, mostrando que mesmo uma gramática não ambígua (como em Java, C, C ++, ...) permite ambigüidades aparentes (!) Da perspectiva humana. Apesar de estarmos formal e computacionalmente bem, agora temos mais um problema de desenvolvimento de UX / livre de bugs.
ComFreek 10/06
5

Veja a análise mais irritante em C ++, por exemplo:

bar foo(foobar());

É uma declaração foode função do tipo bar(foobar())(o parâmetro é um ponteiro de função retornando a foobar) ou uma declaração foode variável do tipo inte inicializada com um padrão inicializado foobar?

Isso é diferenciado nos compiladores, assumindo o primeiro, a menos que a expressão dentro da lista de parâmetros não possa ser interpretada como um tipo.

quando você obtém uma expressão tão ambígua, o compilador tem 2 opções

  1. suponha que a expressão seja uma derivação específica e adicione um pouco de ambiguidade à gramática para permitir que a outra derivação seja expressa.

  2. erro e exigem desambiguação de qualquer maneira

O primeiro pode cair naturalmente, o segundo exige que o programador do compilador conheça a ambiguidade.

Se essa ambiguidade permanecer sem ser detectada, é possível que dois compiladores diferentes padronizem para diferentes derivações para essa expressão ambígua. Levando o código a não ser portátil por razões não óbvias. O que leva as pessoas a supor que é um bug em um dos compiladores, enquanto na verdade é uma falha na especificação da linguagem.

catraca arrepiante
fonte
5

Eu acho que a pergunta contém uma suposição que é apenas limítrofe correta, na melhor das hipóteses.

Na vida real, é bastante comum simplesmente viver com gramáticas ambíguas, desde que não sejam (por assim dizer) muito ambíguas.

Por exemplo, se você olhar as gramáticas compiladas com o yacc (ou similar, como bison ou byacc), verá que alguns produzem avisos sobre "conflitos de turno / redução de N" ao compilá-los. Quando o yacc encontra um conflito de mudança / redução, isso indica uma ambiguidade na gramática.

Um conflito de mudança / redução, no entanto, geralmente é um problema bastante menor. O gerador do analisador resolverá o conflito em favor da "mudança" e não da redução. A gramática é perfeita se é isso que você deseja (e parece funcionar perfeitamente na prática).

Um conflito de troca / redução geralmente surge em um caso nesta ordem geral (usando maiúsculas para não terminais e minúsculas para terminais):

A -> B | c
B -> a | c

Quando encontramos a c, há uma ambiguidade: devemos analisar o cdiretamente como um Aou devemos analisá-lo como um B, que por sua vez é um A? Em um caso como esse, o yacc escolhe uma rota mais simples / mais curta e analisa a rota cdiretamente como uma A, em vez de seguir a rota c-> B-> A. Isso pode estar errado, mas, se houver, provavelmente significa que você tem um erro muito simples em sua gramática e não deve permitir a copção como uma possibilidade A.

Agora, por outro lado, poderíamos ter algo mais parecido com isto:

A -> B | C
B -> a | c
C -> b | c

Agora, quando encontramos um c, temos um conflito entre tratar o ccomo a Bou a C. Há muito menos chances de uma estratégia automática de resolução de conflitos escolher o que realmente queremos. Nenhuma delas é uma "mudança" - ambas são "reduções"; portanto, é um "conflito de redução / redução" (que aqueles que estão acostumados a yacc e geralmente reconhecem como um problema muito maior do que um conflito de mudança / redução).

Portanto, embora eu não tenha certeza se chegaria ao ponto de dizer que alguém realmente aceita a ambiguidade em sua gramática, em pelo menos alguns casos é menor o suficiente para que ninguém realmente se importe muito com isso. Em resumo, eles podem gostar da idéia de remover toda ambiguidade - mas não o suficiente para sempre fazê-lo. Por exemplo, uma gramática pequena e simples que contém uma ambiguidade menor pode ser preferível a uma gramática maior e mais complexa que elimina a ambiguidade (especialmente quando você entra no campo prático de realmente gerar um analisador da gramática e descobrir que o inequívoco a gramática produz um analisador que não será executado na máquina de destino).

Jerry Coffin
fonte
cara, gostaria de ter tido uma excelente explicação sobre conflitos de redução de turnos há 5 meses! ^^; +1
HotelCalifornia