ImCompilerbau ist einLL-Parser ein Top-Down-Parser, der die Eingabe vonLinks nach rechts abarbeitet, um eineLinksableitung der Eingabe zu berechnen.^[1]

Ein LL-Parser heißtLL(k)-Parser, wenn er während des ParsenskTokens vorausschauen kann und im Gegensatz zumLF-Parser den Kellerinhalt benutzt.k wird dabei alsLookahead bezeichnet. Diesem Parsertyp liegen dieLL(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 desrekursiven Abstiegs.

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

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

DernichtdeterministischeAutomat für die LL(k)-Analyse ist dann:

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

Dabei ist${\displaystyle S}$ das Startsymbol der zugrundeliegenden Grammatik und${\displaystyle z}$ die Linksanalyse der Eingabe${\displaystyle w}$.

Die Transitionen${\displaystyle \delta }$ setzen sich so zusammen:

• ${\displaystyle (a\alpha ,aw,z)⊢(\alpha ,w,z)}$ (Shift- oder Verschiebeschritt)
• ${\displaystyle (A\beta ,w,z)⊢(\alpha \beta ,w,zi)}$ (Expansions- oder Ableitungsschritt), wobei die Regel${\displaystyle A\to \alpha }$ in der Regelmenge${\displaystyle P}$ enthalten sein muss und${\displaystyle i}$ die Nummer dieser Regel ist.

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.

In einem Beispiel soll ein LL(1) Parser die folgende einfache Grammatik abbilden:

   S → F   S → ( S + F )   F → n

Die folgende Python-Implementierung des LL(1)-Parsers zu dieser Grammatik wird auf den Eingabestring((n+n)+n) angewendet:

# Parse tabletable={'@S':{'n':0,'(':1},'@F':{'n':2}}rules=[['@F'],['(','@S','+','@F',')'],['n']]defsyntactic_analysis(string):print('Syntactic analysis of input string:',string)stack=['\n','@S']tokens=list(string)+['\n']position=0whilelen(stack)>0:stackvalue=stack.pop()token=tokens[position]ifnotstackvalue.startswith('@'):ifstackvalue==token:# print('pop', repr(stackvalue))position+=1iftoken=='\n':print('input accepted')breakelse:print('syntax error at input:',repr(token))breakelse:rule=table[stackvalue].get(token,-1)print('at pos',position,'found rule',repr(stackvalue+' -> '+' '.join(rules[rule])))forrinreversed(rules[rule]):stack.append(r)# print('stack:', repr(', '.join(reversed(stack))))syntactic_analysis('((n+n)+n)')

Die Ausgabe des Skripts ergibt bei korrekter Syntax direkt den serialisierten Syntax-Baum:

Syntactic analysis of input string: ((n+n)+n)at pos 0 found rule '@S -> ( @S + @F )'at pos 1 found rule '@S -> ( @S + @F )'at pos 2 found rule '@S -> @F'at pos 2 found rule '@F -> n'at pos 4 found rule '@F -> n'at pos 7 found rule '@F -> n'input accepted

• LR-Parser

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

• Compilerbau