Sprachtheoretischer Vergleich von LL- und LR-Grammatiken

67

Die Leute sagen oft, dass LR (k) -Parser leistungsfähiger sind als LL (k) -Parser. Diese Aussagen sind die meiste Zeit vage; Sollten wir insbesondere die Klassen für ein festes oder die Vereinigung über alles ? Wie ist die Situation wirklich? Insbesondere interessiert mich, wie sich LL (*) einfügt.kk

Soweit ich weiß, sind die jeweiligen Grammatiksätze, die LL- und LR-Parser akzeptieren, orthogonal. Lassen Sie uns also über die Sprachen sprechen, die von den jeweiligen Grammatiksätzen generiert werden. Es sei die Klasse von Sprachen, die durch Grammatiken erzeugt werden, die von einem -Parser analysiert werden können, und ähnlich für andere Klassen.LR(k)LR(k)

Ich interessiere mich für folgende Beziehungen:

  • LL(k)?LR(k)
  • i=1LL(k)?i=1LR(k)
  • i=1LL(k)=?LL()
  • LL()?i=1LR(k)

Einige davon sind wahrscheinlich einfach; Mein Ziel ist es, einen "vollständigen" Vergleich zu erstellen. Referenzen sind willkommen.

Raphael
quelle
2
Vielleicht kann dir das helfen! Bild der Grammatikhierarchie
Andrea Tucci
1
@AndreaTucci: Ja, aber das deckt nur die Grammatik ab, nicht die generierten Sprachen.
Raphael

Antworten:

60

Es sind zahlreiche Sicherheitsbehälter bekannt. Lassen Haltung und bezeichnet richtigen Containment. Let Unvergleichbarkeit bezeichnen.×

Sei , .LL=kLL(k)LR=kLR(k)

Grammatikstufe

Für LL

  • LL(0)LL(1)LL(2)LL(2)LL(k)LLLL()
  • SLL(1)=LL(1),SLL(k)LL(k),SLL(k+1)×LL(k)

Die meisten davon sind in Eigenschaften deterministischer Top-Down-Grammatiken von Rosenkrantz und Stearns belegt. ist eine eher triviale Übung. In dieser Präsentation von Terence Parr wird auf Folie 13 platziert. Die in der Arbeit LL-regular enthaltenen Grammatiken von Jarzabek und Krawczyk zeigen , und ihr Beweis erstreckt sich trivial aufSLL(k+1)×LL(k)LL()LLLLRLLLL()

Für LR

  • LR(0)SLR(1)LALR(1)LR(1)
  • SLR(k)LALR(k)LR(k)
  • SLR(1)SLR(2)SLR(k)
  • LALR(1)LALR(2)LALR(k)
  • LR(0)LR(1)LR(2)LR(k)LR

Dies sind alles einfache Übungen.

LL gegen LR

  • LL(k)LR(k) ( Eigenschaften deterministischer Top-Down-Grammatiken plus rekursiver linker Grammatik)
  • LL(k)×SLR(k),LALR(k),LR(k1) (einfache Übung)
  • LLLR (jede linksrekursive Grammatik)
  • LL()×LR (linke Rekursion versus willkürlicher Lookahead)

Sprachniveau

Für LL

  • LL(0)LL(1)LL(2)LL(k)LLLL()
  • SLL(k)=LL(k)

Die meisten davon sind in Eigenschaften deterministischer Top-Down-Grammatiken belegt . Das Äquivalenzproblem für LL- und LR-reguläre Grammatiken von Nijholt verweist auf Arbeiten, die . Die Artikel LL-regular Grammatiken von Jarzabek und Krawczyk zeigen , und ihr Beweis erstreckt sich trivial aufLL(k)LL()LLLLRLLLL()

Für LR

  • LR(0)SLR(1)=LALR(1)=LR(1)=SLR(k)=LALR(k)=LR(k)=LR

Einige davon wurden von Knuth in seinem Aufsatz Über die Übersetzung von Sprachen von links nach rechts, in dem er LR (k) einführte, bewiesen, der Rest wird in Transforming LR (k) Grammatics to LR (1), SLR (1) und (1,1) Bounded-Right-Context-Grammatiken von Mickunas et al.

LL gegen LR

  • { a i b j | i j }LLLR(1) (Einschließung folgt aus dem Obigen, ist das kanonische Beispiel für strikte Einschließung){aibj|ij}
  • LL()×LR (die Sprache zeigt die Hälfte der Behauptung, und die Einführung des Äquivalenzproblems für LL- und LR-reguläre Grammatiken von Nijholt nimmt Bezug auf Artikel die andere Hälfte zeigen){aibj|ij}
  • LR(1)=DCFL (siehe zB Referenz hier ).
Alex ten Brink
quelle
Hervorragende Antwort, ich hatte bereits abgestimmt. Ich hätte gedacht, Frank deRemer hätte LALR <= LR in seiner LALR-Originalarbeit bewiesen? (1969?)
user207421
@EJP: ist unmittelbar, wenn Sie definieren, indem Sie Zustände reduzieren . deRemer hat nur bewiesen, dass seine Konstruktion den gleichen Parser erzeugt. Die Grammatikklassen sind nicht gleich, was eine schöne Übung (oder sogar eine schöne Frage für diese Seite) ist. Die Gleichheit der Sprachklassen ist viel schwieriger: Lesen Sie die Zeitung, wenn Sie wirklich die Details wollen;)LALR(k)LR(k)LALRLR
Alex ten Brink
1
@AlextenBrink Ich habe die Zeitung gelesen und wurde von Frank de Remer unterrichtet, aber es ist mehr als 30 Jahre her ;-) Vielen Dank für all die Details.
user207421
Es kann hilfreich sein, Beispielgrammatiken für jede Ungleichung zu sammeln.
o11c
1
@o11c Ich denke das würde eine einzelne Antwort überfordern. Mein Eindruck ist, dass Alex, wo nötig, gute Referenzen gegeben hat; er gibt für einige "leichte Übung" an. Ich denke, wenn ein Leser keine Grammatik finden kann, kann er eine neue Frage zu diesem speziellen Fall stellen.
Raphael