LL-Parser

Im Compilerbau ist ein LL-Parser ein Top-Down-Parser, der die Eingabe von Links nach rechts abarbeitet, um eine Linksableitung der Eingabe zu berechnen.^[1]

Ein LL-Parser heißt LL(k)-Parser, wenn er während des Parsens k Tokens vorausschauen kann und im Gegensatz zum LF-Parser den Kellerinhalt benutzt. k wird dabei als Lookahead bezeichnet. Diesem Parsertyp liegen die LL(k)-Grammatiken zu Grunde.

Obwohl die LL(k)-Grammatiken relativ eingeschränkt sind, werden LL(k)-Parser oft 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 die Methode des rekursiven Abstiegs.

Funktionsweise

Ausgangspunkt ist eine Grammatik G = (N,Σ,P,S). Der Parser arbeitet mit einer Zustandsmenge $Q = (N \cup \Sigma)^* \times \Sigma^* \times \mathbb{N}^*$, wobei sich ein Zustand $q = (k, w, z) \in Q$ so zusammensetzt:

• k ist der aktuelle Inhalt eines Laufzeitkellers, der für die Speicherung der aktuellen Symbole verwendet wird. k kann sowohl Terminal- als auch Nichtterminalsymbole beinhalten.
• w ist der Teil der Eingabe, der noch nicht gelesen wurde.
• z ist die Ausgabe, eine Folge natürlicher Zahlen, die die Nummern der Regeln der Linksableitung enthält.

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

• $\mathcal{A} = (Q, \delta, q_0, F)$
• $q_0 = (S, w, \epsilon)$ (Anfangszustand)
• $F = (\epsilon, \epsilon, z)$ (Endzustand)

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

Die Transitionen δ setzen sich so zusammen:

• $(a\alpha, aw, z) \vdash (\alpha, w, z)$ (Shift- oder Verschiebeschritt)
• $(A\beta, w, z) \vdash (\alpha\beta, w, zi)$ (Expansions- oder Ableitungsschritt), wobei die Regel $A\rightarrow\alpha$ in der Regelmenge P enthalten sein muss und i die Nummer dieser Regel 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 oben genannten nichtdeterministischen Schritte werden dabei durch den Lookahead determiniert.

Siehe auch

• LR-Parser

1. ↑ Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: "Compilers, Principles, Techniques, and Tools", Seite 191, ISBN 0-201-10088-6