Gramática ambígua - Ambiguous grammar

Na ciência da computação , uma gramática ambígua é uma gramática livre de contexto para a qual existe uma string que pode ter mais de uma derivação ou árvore de análise à esquerda , enquanto uma gramática inequívoca é uma gramática livre de contexto para a qual cada string válida tem uma única à esquerda derivação ou árvore de análise. Muitas línguas admitem gramáticas ambíguas e não ambíguas, enquanto algumas línguas admitem apenas gramáticas ambíguas. Qualquer linguagem não vazia admite uma gramática ambígua ao tomar uma gramática inequívoca e introduzir uma regra ou sinônimo duplicado (a única linguagem sem gramáticas ambíguas é a linguagem vazia). Uma linguagem que só admite gramáticas ambíguas é chamada de linguagem inerentemente ambígua , e há linguagens sem contexto inerentemente ambíguas . Gramáticas livres de contexto determinísticas são sempre inequívocas e são uma subclasse importante de gramáticas não ambíguas; existem gramáticas não determinísticas não ambíguas, no entanto.

Para linguagens de programação de computador , a gramática de referência é frequentemente ambígua, devido a questões como o problema do outro pendente . Se presentes, essas ambigüidades são geralmente resolvidas adicionando regras de precedência ou outras regras de análise contextual , de forma que a gramática geral da frase seja inequívoca. Alguns algoritmos de análise (como ( analisadores Earley ou GLR ) podem gerar conjuntos de árvores de análise (ou "florestas de análise") a partir de strings sintaticamente ambíguas .

Exemplos

Linguagem trivial

O exemplo mais simples é a seguinte gramática ambígua para a linguagem trivial, que consiste apenas na string vazia:

A → A | ε

… O que significa que uma produção pode ser ela mesma novamente ou a string vazia. Assim, a string vazia tem derivações mais à esquerda de comprimento 1, 2, 3 e, na verdade, de qualquer comprimento, dependendo de quantas vezes a regra A → A é usada.

Esta linguagem também possui uma gramática inequívoca, consistindo em uma única regra de produção :

A → ε

… O que significa que a produção única pode produzir apenas a string vazia, que é a string única no idioma.

Da mesma forma, qualquer gramática para uma linguagem não vazia pode se tornar ambígua adicionando duplicatas.

Corda unária

A linguagem regular de strings unárias de um determinado caractere, digamos 'a'(a expressão regular a*), tem a gramática inequívoca:

A → aA | ε

… Mas também tem a gramática ambígua:

A → aA | Aa | ε

Isso corresponde a produzir uma árvore associativa à direita (para a gramática inequívoca) ou permitir a associação à direita e à esquerda. Isso é elaborado a seguir.

Adição e subtração

A gramática livre de contexto

A → A + A | A - A | uma

é ambíguo, pois há duas derivações mais à esquerda para a string a + a + a:

     UMA → A + A      UMA → A + A
     → a + A      → A + A + A (primeiro A é substituído por A + A. A substituição do segundo A produziria uma derivação semelhante)
     → 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, pois há duas árvores de análise para a string a + a - a:

Leftmostderivations jaredwf.svg

A linguagem que ele gera, no entanto, 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 | uma

Outro pendurado

Um exemplo comum de ambigüidade em linguagens de programação de computador é o problema do else pendente . Em muitas linguagens, a instrução elseem If – then (–else) é opcional, o que resulta em condicionais aninhadas com várias maneiras de serem reconhecidas em termos de gramática livre de contexto.

Concretamente, em muitas línguas, pode-se escrever condicionais em duas formas válidas: a forma if-then e a forma if-then-else - na verdade, tornando a cláusula else opcional:

Em uma gramática contendo as regras

Statement → if Condition then Statement |
            if Condition then Statement else Statement |
            ...
Condition → ...

algumas estruturas de frase ambíguas podem aparecer. A expressão

if a then if b then s else s2

pode ser analisado como

if a then begin if b then s end else s2

ou como

if a then begin if b then s else s2 end

dependendo se o elseestá associado ao primeiro ifou ao segundo if.

Isso é resolvido de várias maneiras em diferentes idiomas. Às vezes, a gramática é modificada para que não seja ambígua, como exigindo uma endifdeclaração ou tornando-a elseobrigatória. Em outros casos, a gramática é deixada ambígua, mas a ambigüidade é resolvida tornando a gramática geral da frase sensível ao contexto, por exemplo, associando um elsecom o mais próximo if. Neste último caso, a gramática não é ambígua, mas a gramática livre de contexto é ambígua.

Uma gramática inequívoca com múltiplas derivações

A existência de múltiplas derivações da mesma string não é suficiente para indicar que a gramática é ambígua; apenas várias derivações à esquerda (ou, equivalentemente, várias árvores de análise) indicam ambigüidade.

Por exemplo, a gramática simples

S → A + A
A → 0 | 1

é uma gramática inequívoca para o idioma {0 + 0, 0 + 1, 1 + 0, 1 + 1}. Embora cada uma dessas quatro strings tenha apenas uma derivação à esquerda, ela tem duas derivações diferentes, por exemplo

S  A + A ⇒ 0 + A ⇒ 0 + 0

e

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

Apenas a primeira derivação é a mais à esquerda.

Reconhecendo gramáticas ambíguas

O problema de decisão de se uma gramática arbitrária é ambígua é indecidível porque pode ser mostrado que é equivalente ao problema de correspondência Post . Pelo menos, existem ferramentas que implementam algum procedimento de semidecisão para detectar ambigüidade de gramáticas livres de contexto.

A eficiência da análise gramatical livre de contexto é determinada pelo autômato que a aceita. Gramáticas livres de contexto determinísticas são aceitas por autômatos pushdown determinísticos e podem ser analisadas em tempo linear, por exemplo, pelo analisador LR . Este é um subconjunto das gramáticas livres de contexto que são aceitas pelo autômato pushdown e podem ser analisadas em tempo polinomial, por exemplo, pelo algoritmo CYK . Gramáticas livres de contexto não ambíguas podem ser não determinísticas.

Por exemplo, a linguagem de palíndromos de comprimento par no alfabeto de 0 e 1 tem a gramática livre de contexto não ambígua S → 0S0 | 1S1 | ε. Uma string arbitrária desta linguagem não pode ser analisada sem ler todas as suas letras primeiro, o que significa que um autômato pushdown tem que tentar transições de estado alternativas para acomodar os diferentes comprimentos possíveis de uma string semi-analisada. No entanto, remover a ambigüidade gramatical pode produzir uma gramática livre de contexto determinística e, assim, permitir uma análise mais eficiente. Os geradores de compiladores, como o YACC, incluem recursos para resolver alguns tipos de ambigüidade, como o uso de restrições de precedência e associatividade.

Linguagens inerentemente ambíguas

A existência de linguagens inerentemente ambíguas foi provada com o teorema de Parikh em 1961 por Rohit Parikh em um relatório de pesquisa do MIT.

Embora algumas linguagens livres de contexto (o conjunto de strings que podem ser gerados por uma gramática) tenham gramáticas ambíguas e não ambíguas, existem linguagens livres de contexto para as quais nenhuma gramática livre de contexto inequívoca pode existir. Um exemplo de linguagem inerentemente ambígua é a união de com . Este conjunto é livre de contexto, uma vez que a união de duas linguagens livres de contexto é sempre livre de contexto. Mas Hopcroft & Ullman (1979) fornecem uma prova de que não há maneira de analisar sequências de forma inequívoca no subconjunto comum (não livre de contexto) .

Veja também

Referências

  1. ^ Willem JM Levelt (2008). Uma introdução à teoria das linguagens formais e autômatos . Publicação de John Benjamins. ISBN 978-90-272-3250-2.
  2. ^ Scott, Elizabeth (1º de abril de 2008). "Análise estilo SPPF de reconhecedores Earley" . Notas Eletrônicas em Ciência da Computação Teórica . 203 (2): 53–67. doi : 10.1016 / j.entcs.2008.03.044 .
  3. ^ Tomita, Masaru. " Um algoritmo de análise livre de contexto aumentado e eficiente ." Computational linguistics 13.1-2 (1987): 31-46.
  4. ^ Hopcroft, John ; Motwani, Rajeev ; Ullman, Jeffrey (2001). Introdução à teoria, linguagens e computação dos autômatos (2ª ed.). Addison-Wesley. Teorema 9.20, pp. 405–406. ISBN 0-201-44124-1.
  5. ^ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "Analisando Gramáticas Livres de Contexto Usando um Solucionador SAT Incremental" (PDF) . Proceedings of the 35th International Colloquium on Automata, Languages ​​and Programming (ICALP'08), Reykjavik, Islândia . Notas de aula em Ciência da Computação . 5126 . Springer-Verlag. pp. 410–422. doi : 10.1007 / 978-3-540-70583-3_34 .
  6. ^ Knuth, DE (julho de 1965). "Sobre a tradução das línguas da esquerda para a direita" (PDF) . Informação e controle . 8 (6): 607–639. doi : 10.1016 / S0019-9958 (65) 90426-2 . Arquivado do original (PDF) em 15 de março de 2012 . Página visitada em 29 de maio de 2011 .
  7. ^ Hopcroft, John ; Motwani, Rajeev ; Ullman, Jeffrey (2001). Introdução à teoria, linguagens e computação dos autômatos (2ª ed.). Addison-Wesley. pp. 249-253. ISBN 0-201-44124-1.
  8. ^ Parikh, Rohit (janeiro de 1961). Dispositivos geradores de linguagem . Relatório Trimestral de Progresso, Laboratório de Pesquisa de Eletrônica, MIT.
  9. ^ p.99-103, Sect.4.7

Notas

links externos

  • dk.brics.grammar - um analisador de ambigüidade gramatical.
  • CFGAnalyzer - ferramenta para analisar gramáticas livres de contexto com respeito à universalidade da linguagem, ambigüidade e propriedades semelhantes.