Comment prouver qu'une grammaire est sans ambiguïté?

25

Mon problème est de savoir comment prouver qu'une grammaire est sans ambiguïté? J'ai la grammaire suivante:

Sstatementif expression then Sif expression then S else S

et en faire une grammaire sans ambiguïté, je pense que c'est correct:

  • SS1S2

  • S1if expression then Sif expression then S2 else S1

  • S2if expression then S2 else S2statement

Je sais qu'une grammaire non ambiguë a un arbre d'analyse pour chaque terme.

user1594
la source

Réponses:

20

Il existe (au moins) une façon de prouver l’ambiguïté d’une grammaire pourlangage L . Il se compose de deux étapes:G=(N,T,δ,S)L

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

La première étape est assez claire: montrez que la grammaire génère (au moins) les mots que vous voulez, c'est l'exactitude.

La deuxième étape montre que a autant d'arbres de syntaxe pour les mots de longueur n que L a de mots de longueur n - avec 1. cela implique une ambiguïté. Il utilise la fonction de structure de G qui remonte à Chomsky et Schützenberger [1], à savoirGnLnG

SG(z)=n=0tnzn

avec le nombre d'arbres de syntaxe G a pour les mots de longueur n . Bien sûr, vous devez avoir | L n | pour que cela fonctionne.tn=[zn]SG(z)Gn|Ln|

La bonne chose est que est (généralement) facile à obtenir pour les langages sans contexte, bien que trouver une forme fermée pour t n puisse être difficile. Transformez G en un système d'équations de fonctions avec une variable par non terminal:SGtnG

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

Cela peut sembler intimidant, mais ce n'est en réalité qu'une transformation syntaxique, comme cela apparaîtra clairement dans l'exemple. L'idée est que les symboles terminaux générés sont comptés dans l'exposant de et que le système a la même forme que G , z n se produit le plus souvent dans la somme en tant que n bornes peuvent être générés par G . Consultez Kuich [2] pour plus de détails.zGznnG

La résolution de ce système d'équation (algèbre informatique!) Donne ; il ne vous reste plus qu'à "tirer" le coefficient (sous forme fermée et générale). La triche TCS et l'algèbre informatique peuvent souvent le faire.S(z)=SG(z)


Exemple

Considérez la grammaire simple avec des règlesG

.SaSabSbε

Il est clair que (étape 1, preuve par induction). Il y a 2 nL(G)={wwRw{a,b}} palindromes de longueurnsinest pair,0sinon.2n2nn0

Configuration des rendements du système d'équations

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

dont la solution est

.SG(z)=112z2

Les coefficients de coïncident avec le nombre de palindromes, doncSG est sans ambiguïté.G


  1. La théorie algébrique des langues sans contexte par Chomsky, Schützenberger (1963)
  2. Sur l'entropie des langages hors contexte par Kuich (1970)
Raphael
la source
3
As you know @Raphael, ambiguity is not decidable, so at least one of your steps cannot be mechanised. Any idea which ones? Getting a closed form for tn?
Martin Berger
2
The equation system may not be solvable algorithmically if the degree is too high, and pulling the exact coefficients out of the generating functions can be (too) hard. In "practice", though, one often deals with grammars of small "degree" -- note that, say, Chomsky normal form leads to equation systems of small degree -- and there are methods to get at least -asymptotics for the coefficients; this may be sufficient to establish ambiguity. Note that in order to prove unambiguity, showing SL(z)=SG(z) without pulling coefficients is enough; proving this identity may be hard, though.
Raphael
Merci @Raphael. Connaissez-vous des textes qui développent en détail comment l'indécidabilité entre en jeu même si l'on utilise par exemple la forme normale de Chomsky? (Je n'arrive pas à mettre la main sur Kuich.)
Martin Berger
SG|Ln|[zn]Sg(z). In particular, what representation of L to use for 2)?
Raphael
Why is representation of L a problem? We can use any of the multiple ways of representing CFGs for compilers for example. Maybe you mean how to represent Ln?
Martin Berger
6

This is a good question, but some Googling would have told you that there is no general method for deciding ambiguity, so you need to make your question more specific.

reinierpost
la source
2
The OP asks for proof techniques, not algorithms.
Raphael
I think so, too; it might be mentioned in the question.
reinierpost
1
Google is not an oracle of truth, because knowlede is not democratic, and Google results are. I wouldn't count on Google in this case, because people often copy-cat one from another without checking the correctness of what they copy. Without showing a proof, they might be wrong.
SasQ
5
@SasQ: You read my words too literally. What Google gives me is the URLs to aticles that explain things.
reinierpost
4

For some grammars, a proof by induction (over word length) is possible.


Consider for example a grammar G over Σ={a,b} given by the following rules:

SaSabSbε

All words of length 1 in L(G) -- there's only ε -- have only one left-derivation.

Assume that all words of length n for some nN have only one left-derivation.

Now consider arbitrary w=w1wwnL(G)Σn for some n>0. Clearly, w1Σ. If w1=a, we know that the first rule in every left-derivation has to be SaSa; if w1=b, it has to be SbSb. This covers all cases. By induction hypothesis, we know that there is exactly one left-derivation for w. In combination, we conclude that there is exactly one left-derivation for w as well.


This becomes harder if

  • there are multiple non-terminals,
  • the grammar is not linear, and/or
  • the grammar is left-recursive.

It may help to strengthen the claim to all sentential forms (if the grammar has no unproductive non-terminals) and "root" non-terminals.

I think the conversion to Greibach normal form maintains (un)ambiguity, to applying this step first may take care of left-recursion nicely.

The key is to identify one feature of every word that fixes (at least) one derivation step. The rest follows inductively.

Raphael
la source
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
la source
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наđошƒаӽ