Como provar que uma gramática é inequívoca?

25

Meu problema é como posso provar que uma gramática é inequívoca? Eu tenho a seguinte gramática:

Sstatementif expression then Sif expression then S else S

e fazer isso com uma gramática inequívoca, acho correto:

  • SS1S2

  • S1if expression then Sif expression then S2 else S1

  • S2if expression then S2 else S2statement

Eu sei que uma gramática inequívoca tem uma árvore de análise para cada termo.

user1594
fonte

Respostas:

20

Não é (pelo menos) um meio de provar ambiguidades de uma gramática para a língua L . Consiste em duas etapas:G=(N,T,δ,S)L

  1. Prove .LL(G)
  2. Prove .[zn]SG(z)=|Ln|

O primeiro passo é bem claro: mostre que a gramática gera (pelo menos) as palavras que você deseja, isto é, correção.

O segundo passo mostra que tem tantas árvores de sintaxe para palavras de comprimento n quanto L tem palavras de comprimento n - com 1. isso implica inequívoco. Ele usa a função de estrutura de G, que remonta a Chomsky e Schützenberger [1], a saberGnLnG

SG(z)=n=0tnzn

com o número de árvores de sintaxe G tem para palavras de comprimento n . Claro que você precisa ter | L n | para que isso funcione.tn=[zn]SG(z)Gn|Ln|

O bom é que é (geralmente) fácil de obter para linguagens livres de contexto, apesar de encontrar uma forma fechada para t n pode ser difícil. Transforme G em um sistema de equações de funções com uma variável por não-terminal:SGtnG

[A(z)=(A,a0ak)δ i=0k τ(ai) :AN] with τ(a)={a(z),aNz,aT.

Isso pode parecer assustador, mas é realmente apenas uma transformação sintática, como ficará claro no exemplo. A ideia é que os símbolos terminais gerados são contados no expoente de e porque o sistema tem a mesma forma que G , z n ocorre tão frequentemente na soma de n terminais pode ser gerado por L . Verifique Kuich [2] para detalhes.zGznnG

Resolver este sistema de equações (álgebra computacional!) Produz ; agora você "apenas" precisa puxar o coeficiente (de forma geral fechada). O TCS Cheat Sheet e a álgebra computacional costumam fazer isso.S(z)=SG(z)


Exemplo

Considere a gramática simples com regrasG

.SaSabSbε

É claro que (passo 1, prova por indução). Existem 2 nL(G)={wwRw{a,b}} palíndromos de comprimentonsenfor par,0caso contrário.2n2nn0

A configuração do sistema de equações produz

S(z)=2z2S(z)+1

cuja solução é

.SG(z)=112z2

Os coeficientes de coincidem com os números de paldromas, então G é não ambígua.SG G


  1. A teoria algébrica das línguas livres de contexto de Chomsky, Schützenberger (1963)
  2. Sobre a entropia de linguagens livres de contexto por Kuich (1970)
Rafael
fonte
3
Como você conhece @Raphael, a ambiguidade não é decidível; portanto, pelo menos uma de suas etapas não pode ser mecanizada. Alguma idéia de quais? Obtendo um formulário fechado para ? tn
Martin Berger
2
O sistema de equações pode não ser solucionável por algoritmos se o grau for muito alto e extrair os coeficientes exatos das funções geradoras pode ser (muito) difícil. Na "prática", no entanto, muitas vezes se lida com gramáticas de pequeno "grau" - observe que, digamos, a forma normal de Chomsky leva a sistemas de equações de pequeno grau - e existem métodos para obter pelo menos assintóticos para os coeficientes ; isso pode ser suficiente para estabelecer ambiguidade. Note-se que, a fim de provar unambiguity, mostrando S L ( z ) = S L ( z ) sem puxar coeficientes é suficiente; provar essa identidade pode ser difícil, no entanto. SL(z)=SG(z)
Rafael
Obrigado @Raphael. Você conhece algum texto que desenvolva em detalhes como a indecidibilidade entra em jogo, mesmo que se use, por exemplo, a forma normal de Chomsky? (Eu não pode se apossar de Kuich.)
Martin Berger
@MartinBerger Acabei de redescobrir seu comentário na minha lista de tarefas; Desculpe pelo longo silêncio. Há três passos que (eu acho) não são computáveis em geral: 1) Determinar . 2) computação | L n | . 3) Determine [ z n ] S g ( z ) . Em particular, que representação de L usar para 2)? SG|Ln|[zn]Sg(z)L
Raphael
Por que a representação de um problema? Podemos usar qualquer uma das várias maneiras de representar CFGs para compiladores, por exemplo. Talvez você queira dizer como representar L n ? LLn
Martin Berger
6

Essa é uma boa pergunta, mas alguns usuários do Google diriam que não há um método geral para decidir a ambiguidade , portanto, é necessário tornar sua pergunta mais específica.

reinierpost
fonte
2
O OP solicita técnicas de prova, não algoritmos.
Raphael
Eu também acho; isso pode ser mencionado na pergunta.
Reinierpost
11
O Google não é um oráculo da verdade, porque o conhecimento não é democrático e os resultados do Google são. Nesse caso, eu não contaria com o Google, porque as pessoas geralmente copiam umas das outras sem verificar a exatidão do que copiam. Sem mostrar uma prova, eles podem estar errados.
SasQ
5
@SasQ: Você leu minhas palavras muito literalmente. O que o Google me fornece são os URLs dos artigos que explicam as coisas.
Reinierpost
4

Para algumas gramáticas, é possível uma prova por indução (acima do tamanho da palavra).


Considere, por exemplo, uma gramática sobre Σ = { a , b } fornecida pelas seguintes regras:GΣ={a,b}

SaSabSbε

Todas as palavras de comprimento em L ( G ) - há apenas ε - têm apenas uma derivação à esquerda.1L(G)ε

Suponha que todas as palavras de comprimento para alguns n N tenham apenas uma derivação à esquerda.nnN

Agora considere arbitrária por algum n > 0 . Claramente, w 1Σ . Se w 1 = a , sabemos que a primeira regra em toda derivação à esquerda deve ser S a S a ; se w 1 = b , deve ser S b S bw=w1wwnL(G)Σnn>0w1Σw1=aSaSaw1=bSbSbww


Isso se torna mais difícil se

  • existem vários não terminais,
  • a gramática não é linear e / ou
  • a gramática é recursiva à esquerda.

Pode ajudar a fortalecer a reivindicação de todas as formas sentenciais (se a gramática não tiver terminais não improdutivos) e terminais não raiz "raiz".

Penso que a conversão para a forma normal de Greibach mantém a (des) ambiguidade, para aplicar esta etapa primeiro pode cuidar bem da recursão à esquerda.

A chave é identificar um recurso de cada palavra que corrige (pelo menos) uma etapa de derivação. O resto segue indutivamente.

Raphael
fonte
3

Basically, it's a child generation problem. Start with the first expression, and generate it's children .... Keep doing it recursively (DFS), and after quite a few iterations, see if you can generate the same expanded expression from two different children. If you are able to do that, it's ambiguous. There is no way to determine the running time of this algorithm though. Assume it's safe, after maybe generating 30 levels of children :) (Of course it could bomb on the 31st)

Karthik Kumar Viswanathan
fonte
1
The OP asks for proof techniques, not algorithms.
Raphael
2
that can't possibly be a way to prove if a grammar is ambiguous or not. As a matter of fact when that bombing happens is undecidable.
Sнаđошƒаӽ