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

Bearbeiten

Ausgangspunkt ist eine Grammatik  . Der Parser arbeitet mit einer Zustandsmenge  , wobei sich ein Zustand   so zusammensetzt:

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

  •  
  •   (Anfangszustand)
  •   (Endzustand)

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

Die Transitionen   setzen sich so zusammen:

  •   (Shift- oder Verschiebeschritt)
  •   (Expansions- oder Ableitungsschritt), wobei die Regel   in der Regelmenge   enthalten sein muss und   die Nummer dieser Regel ist.

LL(1)-Parser

Bearbeiten

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.

Beispiel Implementierung in Python

Bearbeiten

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

Siehe auch

Bearbeiten

Einzelnachweise

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