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.

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

• k {\displaystyle k} ist der aktuelle Inhalt eines Laufzeitkellers, der für die Speicherung der aktuellen Symbole verwendet wird. k {\displaystyle k} kann sowohl Terminal- als auch Nichtterminalsymbole beinhalten.
• w {\displaystyle w} ist der Teil der Eingabe, der noch nicht gelesen wurde.
• z {\displaystyle 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:

• A = ( Q , δ , q 0 , F ) {\displaystyle {\mathcal {A}}=(Q,\delta ,q_{0},F)}
• q 0 = ( S , w , ϵ ) {\displaystyle q_{0}=(S,w,\epsilon )} (Anfangszustand)
• F = ( ϵ , ϵ , z ) {\displaystyle F=(\epsilon ,\epsilon ,z)} (Endzustand)

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

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

• ( a α , a w , z ) ⊢ ( α , w , z ) {\displaystyle (a\alpha ,aw,z)\vdash (\alpha ,w,z)} (Shift- oder Verschiebeschritt)
• ( A β , w , z ) ⊢ ( α β , w , z i ) {\displaystyle (A\beta ,w,z)\vdash (\alpha \beta ,w,zi)} (Expansions- oder Ableitungsschritt), wobei die Regel A → α {\displaystyle A\rightarrow \alpha } in der Regelmenge P {\displaystyle P} enthalten sein muss und i {\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 table
table = {'@S': {'n': 0, '(': 1},
         '@F': {'n': 2}}

rules = [['@F'],
         ['(', '@S', '+', '@F', ')'],
         ['n']]

def syntactic_analysis(string):
    print('Syntactic analysis of input string:', string)
    stack = ['\n', '@S']
    tokens = list(string) + ['\n']
    position = 0
    while len(stack) > 0:
        stackvalue = stack.pop()
        token = tokens[position]
        if not stackvalue.startswith('@'):
            if stackvalue == token:
                # print('pop', repr(stackvalue))
                position += 1
                if token == '\n':
                    print('input accepted')
                    break
            else:
                print('syntax error at input:', repr(token))
                break
        else:
            rule = table[stackvalue].get(token, -1)
            print('at pos', position, 'found rule', repr(stackvalue +
                    ' -> ' +  ' '.join(rules[rule])))
            for r in reversed(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