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.
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.
Ich interessiere mich für folgende Beziehungen:
Einige davon sind wahrscheinlich einfach; Mein Ziel ist es, einen "vollständigen" Vergleich zu erstellen. Referenzen sind willkommen.
Antworten:
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
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(∗) LL⊂LLR LL⊂LL(∗)
Für LR
Dies sind alles einfache Übungen.
LL gegen LR
Sprachniveau
Für LL
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(∗) LL⊂LLR LL⊂LL(∗)
Für 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
quelle