o principal diferença entre gramática ambígua e inequívoca é que o gramática ambígua é uma gramática livre de contexto para a qual existe uma string que pode ter mais de uma derivação à esquerda, enquanto uma gramática inequívoca é uma gramática livre de contexto para a qual cada string válida tem uma derivação única à esquerda.

A gramática se refere às regras sintáticas em linguagens naturais. Em 1956, os cientistas da computação introduziram um modelo matemático de gramática para escrever linguagem de computador. Se for possível derivar todas as cadeias de caracteres de uma linguagem usando uma determinada gramática, então diz-se que a linguagem é gerada a partir dessa gramática. A gramática livre de contexto é um tipo de gramática. Esta gramática gera uma linguagem livre de contexto. A gramática livre de contexto pode ser ambígua ou inequívoca. Para uma determinada string, se houver duas ou mais derivações, essa gramática é considerada ambígua. Para uma determinada string, se houver apenas uma derivação única mais à esquerda, essa gramática é considerada uma gramática inequívoca.

Gramática ambígua, gramática inequívoca

O que é gramática ambígua

Uma gramática é considerada ambígua se houver duas ou mais derivações para uma string.

Figura 1: gramática ambígua

Suponha que haja uma gramática definida como segue.

G = ({S}, {a + b, +, *}, P, S}. As regras de produção são as seguintes. S -> S + S | S * S | a | b. Suponha que seja necessário gere a String a + a * b.

Considere, S -> S + S

Substituir 'a' por S mais à esquerda resultará no seguinte.

S-> a + S

Substituir S * S por S é o seguinte.

S-> a + S * S

Substituir 'a' pelo S mais à esquerda dará a saída abaixo.

S -> a + a * S

Substituir 'b' por S dará a seguinte saída.

S -> a + a * b

Esta é a string necessária para gerar.

Ao usar a outra regra de produção, ele dará

S -> S * S

Aplicar S + S à esquerda S dará o seguinte.

S -> S + S * S

Substitua 'a' por S mais à esquerda,

S -> a + S * S

Substituindo 'a' pelo S mais à esquerda,

S -> a + a * S

Substituir 'b' por S dará a seguinte saída.

S -> a + a * b

Novamente, ele gerou a string necessária. Portanto, há mais de uma derivação para gerar a string. Portanto, é uma gramática ambígua.

O que é gramática inequívoca

Em uma gramática ambígua, uma determinada string tem uma derivação única mais à esquerda. Consulte as seguintes regras de produção.

S -> L | a, L -> LS | S

Considere a regra S -> L. Substitua LS em vez de L.

S -> LS

Substitua S, para o primeiro L.

S -> S S

Substituir 'a' pelo S mais à esquerda dará a saída abaixo.

S -> a S

Substituir 'a' por S resultará no seguinte.

S -> a a

Portanto, uma string tem uma derivação única mais à esquerda. Portanto, é uma gramática inequívoca.

Diferença entre gramática ambígua e inequívoca

Definiçã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. A gramática inequívoca é uma gramática livre de contexto para a qual cada string válida tem uma derivação ou árvore de análise sintática exclusiva mais à esquerda.

Número de derivações mais à esquerda

Na gramática ambígua, uma string pode ter duas ou mais derivações à esquerda, mas, na gramática não ambígua, uma string tem uma derivação única à esquerda.

Conclusão

A gramática livre de contexto pode ser ambígua ou inequívoca. A diferença entre a gramática ambígua e não ambígua é que a gramática ambígua é uma gramática livre de contexto para a qual existe uma string que pode ter mais de uma derivação à esquerda enquanto uma gramática inequívoca é uma gramática livre de contexto para a qual toda string válida tem uma derivação única à esquerda.

Referência:

1. “Gramática ambígua”. Wikipedia, Wikimedia Foundation, 17 de julho de 2018, disponível aqui.2. “Projeto do Compilador | Gramática ambígua ”. GeeksforGeeks, 10 de fevereiro de 2018, disponível aqui.3. “Ambiguous Grammar”, Neso Academy, 29 de março de 2017, disponível aqui.

Cortesia de imagem:

1. “Leftmostderivations jaredwf” Por Jaredwf na Wikipedia em inglês - Transferido de en.wikipedia para o Commons por EdwardHades (Domínio Público) via Commons Wikimedia