LL-Parser gehören zur Familie der Top-down-Parser: Sie lesen den Quelltext von links nach rechts und bauen den Syntaxbaum von der Wurzel zu den Blättern auf. Das Kürzel LL steht für „Left-to-right, Leftmost derivation“ — die Eingabe wird links beginnend gelesen, und es entsteht eine Linksableitung. Die Zahl dahinter (LL(1), LL(2), LL(*)) gibt an, wie viele Zeichen der Parser vorausschauen darf: Ein LL(1)-Parser entscheidet mit genau einem Token Lookahead, welche Produktion als Nächstes angewendet wird.
Wie ein LL-Parser arbeitet
Der Parser startet mit dem Startsymbol der Grammatik und ersetzt schrittweise das linkeste Nichtterminal durch die rechte Seite einer Produktion. Damit die Entscheidung deterministisch bleibt, braucht er zwei Informationen: das aktuelle Eingabezeichen (Lookahead) und eine Tabelle, die für jedes Paar aus Nichtterminal und Token die passende Produktion liefert. Diese Parsertabelle wird aus den Mengen FIRST und FOLLOW berechnet: FIRST(X) enthält alle Terminale, mit denen eine Ableitung von X beginnen kann, FOLLOW(X) alle Terminale, die X in einer Satzform folgen dürfen.
Der Ablauf ist vorhersagend: Für jedes Nichtterminal genügt ein Blick auf das aktuelle Token, um die Regel anzuwenden. Ein LL(1)-Parser arbeitet deshalb in linearer Zeit und kann bereits während des Parsens eine symbolische Auswertung oder den AST-Aufbau erledigen.
Voraussetzungen an die Grammatik
Nicht jede Grammatik ist LL(1)-tauglich. Drei typische Hindernisse muss der Parser-Entwickler beseitigen:
- Linksrekursion: Regeln wie A → A β lassen den Top-down-Parser endlos rekursiv absteigen. Sie wird durch Umformung in Rechtsrekursion oder Schleifen beseitigt.
- Gemeinsame Präfixe: Haben zwei Alternativen dasselbe Startsymbol (A → α β | α γ), kann der Parser nicht unterscheiden. Abhilfe schafft die Linksfaktorisierung (α herausziehen).
- Epsilon-Konflikte: Enthält eine Regel A → ε, müssen die FOLLOW-Mengen der beteiligten Nichtterminale disjunkt sein.
LL im Vergleich zu LR
LL-Parser sind einfacher zu verstehen und von Hand zu implementieren als LR-Parser, erkennen aber weniger Grammatiken: Viele reale Sprachkonstrukte (etwa in C++ oder C#) sind nicht LL(1)-fähig, ohne die Grammatik umzubauen. Die praktisch wichtigste LL-Implementierung ist der rekursive Abstieg: jede Grammatikregel wird zu einer eigenen Funktion, ein Token Lookahead entspricht LL(1). Werkzeuge wie ANTLR erweitern das Prinzip zu LL(*), bei dem der Lookahead beliebig groß werden darf; ältere Generationen (LLGen, frühe Java-Compiler) nutzten tatsächlich tabellenbasierte LL-Parser.
Nach der Syntaxanalyse übernimmt die semantische Analyse: Der vom Parser erzeugte Syntaxbaum wird auf Bedeutung geprüft, bevor die Zwischendarstellung und die Codegenerierung folgen. Zusammen mit der lexikalischen Analyse bilden diese Phasen den Frontend-Teil eines Compilers.