Blog: Vergleich von LL(k) mit LL(*)

[SebastianSossna]

GLR und PEG Parser

GLR und PEG zählen zu den Bottom- Up-Parsern und werden als nicht deterministische Parser bezeichnet. Beide Parser akzeptieren mehrdeutige Grammatiken aber akzeptieren immer die erste Interpretation¹. Dies führt dazu, dass Regeln wie A->a|ab akzeptiert werden, aber ab nie erreichbar ist. Grammatikaktionen können nur schwer in nicht deterministischen Parser umgesetzt werden, wobei Sie sehr nützlich sind (Bsp. Ausgaben auf der Konsole oder Symboltabellenmanipulationen)¹. Bottom-up-Parsing kann auch unvorhersehbar sein, da ein Zustand mehrere Stellen in der Grammatik repräsentiert, während Top-down-Parsing, wie LL, durch eine direkte Zuordnung zu Grammatikelementen einfacher zu verstehen ist¹. Außerdem ist die Fehlerbehandlung bei Bottom-Up-Parsern eingeschränkt, da der Parser nicht ausreichend über den Kontext, in dem der Fehler aufgetaucht ist, informiert ist. Daher ist das Überspringen von Token nicht möglich und es können auch keine aussagekräftigen Fehlermeldungen zurückgeliefert werden¹.

LL Parsing

LL-Parsing liest eine Eingabe von links nach rechts und leiten von links an ab. LL-Parser arbeiten Top-Down. Das bedeutet, dass von der Startregel ausgehend nach unten. Dem gegenüber steht das LR-Parsing, welches die Eingabe ebenso von links nach rechts liest, aber von rechts an ableitet. Sie arbeiten als Bottom-Up parser. LR- Parser können im Allgemeinen eine größere Klasse von Grammatiken parsen, da LR- Parser mit linksrekursion und komplexeren Konstrukten besser umgehen können. Auch wenn LL-Parser im Allgemeinen mehr Lookahead als LR-Parser zum Parsen der selben Sprache benötigen, sind LL-Parser praktikabler².

<sup>3

3</sup>
In der unteren Grafik sieht man zwei Ableitungsbäume der Grammatik, welche in der oberen Grafik zu sehen ist. eines LL Parsers bei Eingabe "id + id + id".

<sup>4

4</sup>]
In (3) sieht man den Ableitungsbaum der Grammatik (2) eines LR Parsers bei Eingabe "abcde".

LL(1), LL(k) und Lookahead

Ein LL(1) parser nutzt das Konzept des Lookaheads und gehört auch zu den LL Parsern. Der Anzahl der Vorschautoken des Lookaheads beim LL(1) parser beträgt ein Token. Das Prinzip des Lookaheads ist eine bestimmte Anzahl an Folgetoken anzuschauen, ohne diese zu konsumieren. Der Lookahead dient dazu die Mehrdeutigkeiten in einer Grammatik aufzulösen.

S-> Aab | Bab
A-> a 
B-> b 

Für diese Grammatik reicht LL(1) aus.

S-> Aab | Bab
A-> a| aA | aB
B-> b| bB | bA

Bei dieser Grammatik reicht LL(1) nicht mehr aus. Da mit einem Vorschautoken nicht entschieden werden kann, welche Regel die nächste ist.

Bei solchen Grammatiken benötigen wir mehr vorschautoken. Wir sprechen dann vom LL(k)-Parser, wobei k für eine beliebige, aber feste Anzahl an Vorschautoken steht. Es wird also vor dem Parsen die Anzahl an Vorschautokens festgelegt, die Anzahl der Vorschautoken kann während des Parsens nicht angepasst werden. Wenn die Grammatik sehr komplex wird, benötigt man einen umso größeren Lookahead. Nun könnte man das Problem der Wahl der Anzahl an Vorschautoken mit der Länge der Eingabe lösen. Mehr vorschautoken werden nicht benötigt, da man nicht mehr als die Anzahl der Eingabetoken einlesen kann. Somit ist der Lookahead direkt von den der Eingabemenge beschränkt. Ein Lookahead der, der Länge der Eingabe entspricht, ist in der Praxis allerdings sehr ineffizient, da längere Programme umso länger zum Parsen brauchen. Solch ein langer Lookahead ist nicht nötig. Hier kann ein dynamischer Lookahead das Parsen effizienter machen.

Grammatiken der LL Parser

LL -Parser können bestimmte Klassen von kontextfreien Grammatiken parsen. Wobei LL(1) weniger Klassen von kontextfreien Grammatiken parsen kann als LL(k) und LL(*) wiederrum kann noch mehr parsen. LL- Parser können keine linksrekursiven Grammatiken parsen. Wobei ALL(*) direkte Linksrekursion auflösen kann und somit auch Grammatiken mit direkter Linksrekursion parsen kann. LL(*) kann in einigen Fällen auch Kontextsensitive Sprachen erkennen ¹.

Eine Grammatik, welche Sprachen wie a^nb^nc^n->n>0 erzeugt, wäre nicht kontextfrei, da a, b und c gleich oft vorhanden sein müssen und dies ist mit kontextfreien Grammatiken nicht darstellbar. Daher können LL-Parser diese Grammatiken nicht parsen.

Vergleich LL(1) | LL(k) | LL(*)

Merkmal	LL(1)	LL(k)	LL(*)
Lookahead	1 Token	k Token (wobei k > 1)	Unbeschränkt (Im Schnitt k<=2)
Ausdruckskraft	Begrenzt; kann nur einfache kontextfreie Grammatiken parsen	Höher als LL(1); kann komplexere kontextfreie Grammatiken parsen	Sehr hoch; kann alle kontextfreien Grammatiken parsen, die keine Linksrekursion enthalten und einige kontextsensitive Grammatiken1
Linksrekursion	Kann keine Linksrekursion verarbeiten	Kann keine Linksrekursion verarbeiten	Kann keine Linksrekursion verarbeiten ( ALL(*) aber direkte Linksrekursion!)
Verwendung	Häufig in einfachen Compilern und Tools	Verwendet in spezialisierten Anwendungen	Verwendet in modernen Parser-Generatoren wie ANTLR

LL(*)

LL(*) ist ein Parsing-Algorithmus, welcher zur Klasse der LL Parser gehört und als Erweiterung des LL(k) Parsers betrachtet werden kann. Eine wesentliche Characteristik vom LL(*)-Parser ist, dass die Anzahl an Vorschautoken beliebig lang sein kann und situativ gewählt wird. Durch diesen adaptiven Ansatz ist LL(*) in der Lage komplexere Strukturen zu handhaben, aber dennoch Effizient beim Parsen zu sein. In der Praxis ist der LL(*)- Parser bei größeren und komplexeren Eingaben effizienter als der LL(k) parser. Der Unterschied der Effizienz zwischen LL(k) und LL(*) wird wie folgt gut verdeutlicht:
"In practice, LL(*) parsers only look one or two tokens ahead on average despite needing to backtrack occasionally."¹

LL(*) kann einige Mehrdeutigkeiten in der Grammatik und tote Produktionen identifizieren¹
Auch unterstützt LL(*) source-level debugging und kann qualitative Fehlermeldungen produzieren¹. Programmierer haben die Möglichkeit außerdem Grammatik Aktionen zu implementieren¹.

Wahl des Lookaheads bei LL(*)

Der LL(*) Parser erzeugt für jede Grammatikregel einen DFA. Mit dessen Hilfe lässt sich frühzeitig aussagen wie viele Vorschautoken der Parser beim Parsen einer bestimmten Grammatikregel benötigt. LL(*) kann mit Backtracking ( auch bekannt als PEG mode ) weitere Vereinfachungen bei der Anzahl der Vorschautoken bewirken. Dadurch verändert sich der DFA und es kann in einigen Fällen dazu kommen, dass Backtracking eingesetzt werden muss.

Grammar to DFA

G =(N; T; P; S; Π; M)

N sei die Menge der Nichtterminalen.

T sei die Menge der Terminalen.

P sei die Menge der Produktionen

S∈N sei das Startsymbol.

Π sei die Menge an semantischen Prädikaten ohne Nebeneffekte

M sei die Menge der Grammatik-Aktionen

DFA M = (S; Q;Σ;Δ;D0; F)

S ist der Systemzustand vom Parser mitgegeben

Q ist die Menge der Zustände

Σ ist unser Kantenalphabet TUΠ

Δ ist die Menge der Übergangsfunktionen QxΣ->Q

D0∈Q ist unser Startzustand

F ist die Menge der finalen Zustände f1, f2, ..., fn, mit einem fi∈Q für jede Produktionsregel

DFA Konstruktion (no PEG mode)

¹
Hier ist eine ANTLR3.3 Grammatik.

¹
Hier sehen wir den lookahead DFA für die Regel s.

Wenn LL(*) bei dieser Regel versucht seinen Input zu parsen, dann würde er bei einem "int" als input einen Lookahead von k=1 benötigen. Wenn jedoch eine ID als bekommt, benötigt LL(*) einen Lookahead von k=2, da wir mit ID alleine noch nicht in einem Endzustand sind. Wir müssen dann noch ein weiteres Token anschauen, um einen Endzustand zu erreichen. Bei einem unsigned weiß der Parser allerdings nicht wie groß der Lookahead ist und muss beliebig viele Vorschautoken ansehen, bis der Parser auf ein int oder eine ID stößt, um zum Endzustand zu gelangen.

Das Backtracking muss bei ANTLR 3.3 vom Programmierer explizit über syntaktische Prädikate ( options {backtrack=true}) vom Parser gefordert werden. Dieser Modus wird "PEG mode" genannt. Wenn die DFA's erstellt werden und der PEG mode aktiviert ist, dann werden zusätzliche Zustände gebildet, um Backtracking vermeiden zu können.

DFA Konstruktion (PEG mode)

¹
Hier ist eine andere ANTLR 3.3 Grammatik mit einem syntaktischen Prädikat, um das Backtracking zu aktivieren.

¹
In diesem Bild ist der lookahead DFA für die Regel s2 im PEG mode dargestellt.

Wir sehen, dass der DFA mit k=1 lookahead bei der Eingabe von ID oder INT direkt in einen Endzustand kommen kann und kein Backtracking benötigt. Ansonsten ist hier auch ein zusätzlicher Zustand s4 vorhanden, um die rekursive Regel auflösen zu können. Normalerweise würde man s4 weglassen und eine Kante zu s1 zurück führen bei jedem weiteren "-". Damit hätte man weniger Kanten und weniger Zustände. Aber durch diese Einführung können wir hier den Lookahead auf k=3 setzen und müssten nicht mehr mit einem beliebigen Lookahead umgehen. Wenn nun in unserem Eingabestrom "---" vorhanden ist, dann kann der DFA dies nicht auflösen und erreicht keinen gültigen Zustand. der DFA muss dann mit Backtracking weiter arbeiten. Hier ist es wichtig zu erwähnen, dass wir beliebig viele solcher zusätzlichen Zustände generieren können. In der ANTLR 3.3 spezifikation gibt es eine interne Konstante m, welche eben die Anzahl dieser Zustände festlegt. In unserem Beispiel wäre der Wert von m =1.

Ausblick ALL(*)

ALL(*) steht für Adaptive LL(*). ALL(*) ist eine Weiterentwicklung von LL(*). ALL(*) wird in ANTLR4 verwendet. Sowohl LL(*) alsauch ALL(*) können kontextfreie Grammatiken und einige kontextsensitive Grammatiken parsen, wobei LL(*) keine Linksrekursion verarbeiten kann und ALL(*) direkte Linksrekursion verarbeiten kann⁵. Dafür wird die Grammatik so umgeschrieben, dass die direkte Linksrekursion aufgelöst werden kann⁵. ALL(*) verwendet bessere Parsing-Strategien, um Konflikte bei der Wahl der Regeln effizienter zu lösen. Dadurch ist ALL(*) in der praxis besser geeignet komplexe, mehrdeutige Grammatiken effizient zu parsen.

Laufzeit

⁵

In dieser Grafik repräsentiert ANTLR4 den ALL(*) Parser und ANTLR3 den LL(*) parser.
Die Markierten Laufzeiten sind miteinander zu vergleichen. Wenn man genau hinsieht, dann bemerkt man, dass der händisch erstellte Javac Parser schneller ist als ALL(*). Und der Vergleich zwischen ANTLR3 und ANTLR4 zeigt, dass LL(*) langsamere Ergebnisse geliefert hat als ALL(*).

Quellen

Footnotes

1. Terence Parr and Kathleen Fisher. 2011. LL(*): the foundation of the ANTLR parser generator. SIGPLAN Not. 46, 6 (June 2011), 425–436. https://doi.org/10.1145/1993316.1993548 ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹ ↩¹² ↩¹³ ↩¹⁴

2. Parr, Terence J. and Dieb, Henry G., "A Practical approach to LL(k); LLm(n)" (1992). ECE Technical Reports. Paper 307. http://docs.lib.purdue.edu/ecetr/307 ↩

3. A. V. Aho, S. C. Johnson, and J. D. Ullman. 1975. Deterministic parsing of ambiguous grammars. Commun. ACM 18, 8 (Aug. 1975), 441–452. https://doi.org/10.1145/360933.360969 ↩ ↩²

4. Donald E. Knuth (1965). On the translation of languages from left to right. , 8(6), 607–639. doi:10.1016/s0019-9958(65)90426-2  ↩ ↩²

5. Terence Parr, Sam Harwell, and Kathleen Fisher. 2014. Adaptive LL(*) parsing: the power of dynamic analysis. SIGPLAN Not. 49, 10 (October 2014), 579–598. https://doi.org/10.1145/2714064.2660202 ↩ ↩² ↩³