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

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.

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:

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.$a-b-c$$(a-b)-c$$a-(b-c) = a-b+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 .

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]

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).

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 .

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.

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).