LL-Parser

Ein LL-Parser ist ein Top-Down-Parser, der die Eingabe von links nach rechts abarbeitet, um die Linksableitung der Eingabe zu berechnen.

Ein LL-Parser heißt LL(k)-Parser, wenn er während des Parsens k Token vorausschauen kann. k wird dabei als lookahead bezeichnet. Diesem Parsertyp liegen die LL(k)-Grammatiken zu Grunde. Die meisten heute benutzten LL(k)-Parser sind LL(1)-Parser.

LL(k) steht dabei für left-to-right parse, leftmost derivation, k symbols lookahead.

Obwohl die LL(k)-Grammatiken relativ eingeschränkt sind, werden LL(k)-Parser gern benutzt. Die Entscheidung, nach welcher Regel expandiert wird, kann allein durch Analyse des lookahead getroffen werden. Eine einfache Möglichkeit zur Implementierung dieser Parsertechnik bietet Rekursiver Abstieg.

Funktionsweise

Der Parser arbeitet mit einem Zustand Q=(K,E,A), welcher sich so zusammensetzt:

• K ist ein Laufzeitkeller, der für die Speicherung der aktuellen Symbole verwendet wird
• E ist die Eingabe, die noch nicht gelesen wurde
• A stellt die Ausgabe dar.

Der nicht-deterministische Automat für die LL(k)-Analyse ist dann:

• A=(Q,$q_{0}$,D,F)
• $q_{0}=(S,E,\epsilon )$
• $F=(\epsilon ,\epsilon ,z)$

Dabei ist S das Startsymbol der zugrundeliegenden Grammatik und z die Linksanalyse der Eingabe E.

Die Transitionen D setzen sich so zusammen:

• $(a\alpha ,aE,z)\vdash (\alpha ,E,z)$ (shift- oder Verschiebeschritt)
• $(A\beta ,E,z)\vdash (\alpha \beta ,E,zi)$ (Expansions- oder Ableitungsschritt), wobei dann die Regel $A\rightarrow \alpha$ in den Produktionen enthalten sein muß und die Nummer der Produktion i ist.

LL(1) Parser

Dieser Parsertyp verwendet einen Lookahead von einem Zeichen. Auf Grund dieser Einschränkung kann einfach ein deterministischer Parser erstellt werden.

Die o.g. nicht-deterministischen Schritte werden von hier durch den Lookahead determiniert.

Siehe auch

• Parser
• LR-Parser