Jak udowodnić, że gramatyka jest jednoznaczna?

25

Mój problem polega na tym, jak mogę udowodnić, że gramatyka jest jednoznaczna? Mam następującą gramatykę:

Sstatementif expression then Sif expression then S else S

i uczynię to jednoznaczną gramatyką, myślę, że jest poprawne:

  • SS1S2

  • S1if expression then Sif expression then S2 else S1

  • S2if expression then S2 else S2statement

Wiem, że jednoznaczna gramatyka ma jedno drzewo analizy dla każdego terminu.

użytkownik1594
źródło

Odpowiedzi:

20

Nie ma (co najmniej) jednym ze sposobów wykazania jednoznaczność gramatyki dla języka L . Składa się z dwóch kroków:G=(N,T,δ,S)L

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

Pierwszy krok jest całkiem jasny: pokaż, że gramatyka generuje (przynajmniej) słowa, które chcesz, to jest poprawność.

Drugi krok pokazuje, że ma tyle drzew składni dla słów o długości n, jak L ma słowa o długości n - z 1. oznacza to jednoznaczność. Wykorzystuje funkcję struktury G, która sięga do Chomsky'ego i Schützenbergera [1], mianowicieGnLnG

SG(z)=n=0tnzn

z liczba drzew składniowych G ma dla słów o długości n . Oczywiście trzeba mieć | L n | aby to zadziałało.tn=[zn]SG(z)Gn|Ln|

Zaletą jest to, że jest (zwykle) łatwy do uzyskania dla języków bezkontekstowych, chociaż znalezienie zamkniętego formularza dla t n może być trudne. Przekształć G w układ równań funkcji z jedną zmienną na nieterminal:SGtnG

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

Może to wyglądać zniechęcająco, ale tak naprawdę jest to tylko syntaktyczna transformacja, co stanie się jasne w przykładzie. Chodzi o to, że wygenerowane symbole końcowe są liczone w wykładnik i dlatego, że układ ma taką samą postać co G , Z, n zachodzi tak często, w sumie, jak N zaciski mogą być generowane przez G . Szczegóły w Kuich [2].zGznnG

Rozwiązanie tego układu równań (algebra komputerowa!) Daje ; teraz „tylko” trzeba pociągnąć za współczynnik (w zamkniętej, ogólnej formie). TCS Ściągawka i komputer algebra często może zrobić.S(z)=SG(z)


Przykład

Rozważ prostą gramatykę z regułamiG

.SaSabSbε

Oczywiste jest, że (krok 1, dowód przez indukcję). Są 2 nL(G)={wwRw{a,b}} palindromy o długościn,jeżelinjest parzyste, wprzeciwnym razie0.2n2nn0

Ustawienie układu równań daje

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

którego rozwiązaniem jest

.SG(z)=112z2

Współczynniki pokrywają się z liczbą palindromów, więc G jest jednoznaczne.SG G


  1. Algebraiczna teoria języków bezkontekstowych Chomsky'ego, Schützenberger (1963)
  2. O entropii języków bezkontekstowych autorstwa Kuicha (1970)
Raphael
źródło
3
Jak wiesz @Raphael, niejednoznaczność nie jest rozstrzygalna, więc przynajmniej jednego z twoich kroków nie można zmechanizować. Wiesz, które? Otrzymujesz zamknięty formularz dla ? tn
Martin Berger,
2
Układ równań może nie być rozwiązany algorytmicznie, jeśli stopień jest zbyt wysoki, a wyciągnięcie dokładnych współczynników z funkcji generujących może być (zbyt) trudne. W „praktyce” często jednak mamy do czynienia z gramatykami małego „stopnia” - zauważmy, że powiedzmy, że normalna postać Chomsky'ego prowadzi do układów równań małego stopnia - i istnieją metody uzyskania co najmniej -asymptotyków dla współczynników ; może to wystarczyć do ustalenia niejednoznaczności. Zauważ, że aby udowodnić jednoznaczność, wystarczy pokazać S L ( z ) = S G ( z ) bez współczynników ciągnięcia; udowodnienie tej tożsamości może być trudne. SL(z)=SG(z)
Raphael
Dziękuję @Raphael. Czy znasz jakieś teksty, które szczegółowo wyjaśniają, w jaki sposób wchodzi w grę nierozstrzygalność, nawet jeśli używa się np. Normalnej formy Chomsky'ego? (Nie mogę złapać Kuicha).
Martin Berger,
@MartinBerger Właśnie odkryłem twój komentarz na mojej liście rzeczy do zrobienia; przepraszam za długą ciszę. Istnieją trzy etapy, które (chyba) nie są w ogóle obliczeniowy: 1) ustalenia . 2) Oblicz | L n | . 3) Określ [ z n ] S g ( z ) . W szczególności, jakiej reprezentacji L użyć dla 2)? SG|Ln|[zn]Sg(z)L
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
źródło
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
źródło
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
źródło
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наđошƒаӽ