www.wikidata.de-de.nina.az

LL Parser Im Compilerbau ist ein ein Top Down Parser der die Eingabe von Links nach rechts abarbeitet um eine Linksablei

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.

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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 heisst LL k Parser wenn er wahrend 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 eingeschrankt sind werden LL k Parser oft benutzt Die Entscheidung nach welcher Regel expandiert wird kann allein durch Analyse des Lookahead getroffen werden Eine einfache Moglichkeit zur Implementierung dieser Parsertechnik bietet die Methode des rekursiven Abstiegs Inhaltsverzeichnis 1 Funktionsweise 2 LL 1 Parser 2 1 Beispiel Implementierung in Python 3 Siehe auch 4 EinzelnachweiseFunktionsweise BearbeitenAusgangspunkt ist eine Grammatik G N S P S displaystyle G N Sigma P S nbsp Der Parser arbeitet mit einer Zustandsmenge Q N S S N displaystyle Q N cup Sigma times Sigma times mathbb N nbsp wobei sich ein Zustand q k w z Q displaystyle q k w z in Q nbsp so zusammensetzt k displaystyle k nbsp ist der aktuelle Inhalt eines Laufzeitkellers der fur die Speicherung der aktuellen Symbole verwendet wird k displaystyle k nbsp kann sowohl Terminal als auch Nichtterminalsymbole beinhalten w displaystyle w nbsp ist der Teil der Eingabe der noch nicht gelesen wurde z displaystyle z nbsp ist die Ausgabe eine Folge naturlicher Zahlen die die Nummern der Regeln der Linksableitung enthalt Der nichtdeterministische Automat fur die LL k Analyse ist dann A Q d q 0 F displaystyle mathcal A Q delta q 0 F nbsp q 0 S w ϵ displaystyle q 0 S w epsilon nbsp Anfangszustand F ϵ ϵ z displaystyle F epsilon epsilon z nbsp Endzustand Dabei ist S displaystyle S nbsp das Startsymbol der zugrundeliegenden Grammatik und z displaystyle z nbsp die Linksanalyse der Eingabe w displaystyle w nbsp Die Transitionen d displaystyle delta nbsp setzen sich so zusammen a a a w z a w z displaystyle a alpha aw z vdash alpha w z nbsp Shift oder Verschiebeschritt A b w z a b w z i displaystyle A beta w z vdash alpha beta w zi nbsp Expansions oder Ableitungsschritt wobei die Regel A a displaystyle A rightarrow alpha nbsp in der Regelmenge P displaystyle P nbsp enthalten sein muss und i displaystyle i nbsp die Nummer dieser Regel ist LL 1 Parser BearbeitenDieser Parsertyp verwendet einen Lookahead von einem Zeichen Auf Grund dieser Einschrankung 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 gt 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 gt 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 gt S F at pos 1 found rule S gt S F at pos 2 found rule S gt F at pos 2 found rule F gt n at pos 4 found rule F gt n at pos 7 found rule F gt n input acceptedSiehe auch BearbeitenLR ParserEinzelnachweise Bearbeiten Alfred V Aho Ravi Sethi Jeffrey D Ullman Compilers Principles Techniques and Tools ISBN 0 201 10088 6 S 191 Abgerufen von https de wikipedia org w index php title LL Parser amp oldid 210632570