LR Parser

LR Parser

Ein LR-Parser ist ein Bottom-Up-Parser für LR-Grammatiken. Bei diesen kontextfreien Grammatiken wird die Eingabe von links nach rechts abgearbeitet, um die Rechtsreduktion zum Startsymbol zu berechnen.

Inhaltsverzeichnis

Allgemeines

Ein LR-Parser heißt LR(k)-Parser, wenn er während des Parsens k Token vorausschauen kann. k wird dabei als Lookahead bezeichnet.
LR(k) ist eine Abkürzung für Parsen von links nach rechts mit Rechtsreduktionen, k Symbole Lookahead.

LR-Parser per Hand zu schreiben birgt ein großes Fehlerrisiko, weswegen hier meistens Parsergeneratoren verwendet werden.

Aufbau und Arbeitsweise eines LR-Parsers

Ein LR-Parser besteht aus einem Kellerspeicher, einer Aktions-Tabelle und einer GoTo-Tabelle. Das oberste Element im Keller gibt den aktuellen Zustand des Parsers an. Bei Programmstart liegt nur der Startzustand im Keller. In der Aktionstabelle wird vermerkt, was bei jeder Kombination aus Zustand und Eingabezeichen zu tun ist. Mögliche Aktionen sind:

  • Shift(z): Bewege den Zeiger im Eingabestrom einen Schritt weiter und lege den aktuellen Zustand in den Keller. Wechsle dann in den Zustand z.
  • Reduce(n): Wende die Regel n an. D.h. nimm soviele Elemente aus dem Keller, wie die Regel Elemente auf der rechten Seite hat. Schaue anschließend in der Goto-Tabelle nach, welches der nächste Zustand ist und lege ihn in den Keller.
  • Accept: Akzeptiere die Eingabe. D.h. die Eingabe ist gültig und der Parser terminiert.
  • Error: Ist eine Zustands-Eingabe-Konstellation in der Tabelle nicht beschrieben, dann wird die Eingabe abgelehnt und der Parser terminiert.

Beispiel eines Parsers

Wir betrachten folgende Grammatik in BNF:

E ::= E "*" B | E "+" B | B .
B ::= "0" | "1" .

Diese Grammatik lässt sich in folgende, einzelne Reduktionsregeln umwandeln:

  1. E * B ← E
  2. E + B ← E
  3. B ← E
  4. 0 ← B
  5. 1 ← B

Markiert man das Ende der Eingabe mit einem $-Zeichen (Regel E $ ← S) so sehen die Aktions- und GoTo-Tabelle für einen LR(0)-Parser dazu folgendermaßen aus:

Aktion GoTo
Zustand * + 0 1 $ E B
0 s1 s2 3 4
1 r4 r4 r4 r4 r4
2 r5 r5 r5 r5 r5
3 s5 s6 acc
4 r3 r3 r3 r3 r3
5 s1 s2 7
6 s1 s2 8
7 r1 r1 r1 r1 r1
8 r2 r2 r2 r2 r2

Wie man diese Tabellen aus der Grammatik erstellt wird im Abschnitt Erstellen der Aktions- und Goto-Tabelle beschrieben.

Beispiel eines Parse-Vorgangs

Als Eingabe sei die Zeichenkette "1+1" gegeben.

1. Der Startzustand ist hier 0, also startet der Parser nur mit einer 0 im Keller, und der Lesezeiger steht auf dem ersten Zeichen der Eingabe.

Ausgabe: 1+1$
Keller: 0
Eingabe: 1 + 1 $

2. Wir schauen nun in der Aktionstabelle was beim Zustand 0 und der Eingabe "1" zu tun ist: s2, d.h. wir legen den Zustand 2 in den Keller und lesen das nächste Zeichen.

Aktion: Lege 2 in den Keller
Ausgabe: 1+1$
Keller: 0 2
Eingabe: 1 + 1 $

3. Mit der Eingabe "+" sollen wir im Zustand 2 Regel 5 anwenden. Die Regel 5 hat ein Element auf der rechten Seite. Daher nehmen wir ein Element aus dem Keller und sehen in der Goto-Tabelle den nächsten Zustand nach. Im Zustand 0 (die 2 haben wir ja gerade weggenommen) wird nach Anwendung einer Regel, die auf der linken Seite ein B stehen hat in den Zustand 4 gewechselt.

Aktion: Reduziere 1\leftarrow B
Ausgabe: 1+1\$ \Leftarrow_r B+1\$
Keller: 0 4
Eingabe: B + 1 $

4. Jetzt kommt erneut eine Reduktion. Diesmal mit Regel 3. Wir wechseln in den Zustand 3.

Aktion: Reduziere B\leftarrow E
Ausgabe: 1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$
Keller: 0 3
Eingabe: E + 1 $

5. Jetzt kommt ein Shift. Wir wechseln in den Zustand 6.

Aktion: Lege + in den Keller.
Ausgabe: 1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$
Keller: 0 3 6
Eingabe: E + 1 $

6. Shift, neuer Zustand: 2

Aktion: Lege 1 in den Keller.
Ausgabe: 1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$
Keller: 0 3 6 2
Eingabe: E + 1 $

7. Reduktion mit Regel 5, neuer Zustand ist 8

Aktion: Reduziere 1 \leftarrow B.
Ausgabe: 1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$\Leftarrow_r E+B\$
Keller: 0 3 6 8
Eingabe: E + B $

8. Reduktion mit Regel 2. Wir nehmen daher drei Elemente aus dem Keller. Dann liegt die 0 ganz oben, und wir wechseln in den Zustand 3, da die Regel 2 ein E auf der linken Seite hat.

Aktion: Reduziere E + B \leftarrow E.
Ausgabe: 1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$\Leftarrow_r E+B\$ \Leftarrow_r E\$
Keller: 0 3
Eingabe: E $

9. Accept. Die Eingabe gehört zur Grammatik und wir sind fertig.

Erstellen der Aktions- und Goto-Tabelle

Um die Tabelle zu erhalten wird aus der Grammatik ein deterministischer endlicher Automat (DFA) erstellt und aus diesem werden die Zustände und die Übergänge in die Tabelle geschrieben. Je nachdem welche Art von LR-Parser konstruiert wird, gibt es leichte Änderungen des Konstruktionsablaufs. Ein solcher Ablauf wird zum Beispiel für SLR-Parser beschrieben.

Siehe auch

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Parser (magazine) — Parser: New Poetry Poetics is an annual journal of anarchist poetry and poetics from Vancouver, BC, edited by Roger Farr and Reg Johanson. The first issue was published in May 2007, featuring writing by Alice Becker Ho, Alfredo M. Bonanno, P.… …   Wikipedia

  • parser — (izg. pàrser) m DEFINICIJA inform. program koji obavlja sintaktičku analizu nekog jezika; sintaktički analizator ETIMOLOGIJA engl …   Hrvatski jezični portal

  • parser — pars er, n. One who parses. [1913 Webster] …   The Collaborative International Dictionary of English

  • Parser — Ein Parser [ˈpɑːʁzɐ] (engl. to parse, „analysieren“, bzw. lateinisch pars, „Teil“; im Deutschen gelegentlich auch Zerteiler) ist ein Computerprogramm, das in der Computertechnik für die Zerlegung und Umwandlung einer beliebigen Eingabe in ein für …   Deutsch Wikipedia

  • Parser combinator — In functional programming, a parser combinator is a higher order function which accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some… …   Wikipedia

  • Parser Combinator — In mathematics and functional programming, Higher Order functions (HOF) are defined as the functions that can take functions as their input and can also produce functions as their output. The use of a HOF as an infix operator in a function… …   Wikipedia

  • Parser — Это статья о языке программирования, об алгоритме синтаксического анализа см. Синтаксический анализ. Parser Семантика: мультипарадигменный Тип исполнения: Интерпретатор компилирующего типа Появился в …   Википедия

  • Parser-Generator — Ein Parsergenerator ist ein Computerprogramm, das unter Eingabe einer Spezifikation einen Parser erzeugt. Inhaltsverzeichnis 1 Grundlagen 2 Algorithmen 3 Siehe auch 4 Weblinks // …   Deutsch Wikipedia

  • Parser — Pạr|ser 〈m. 3; EDV〉 Bestandteil eines Compilers, Programm, das die syntaktische Analyse eines Quellprogramms durchführt, um es in eine Maschinensprache zu übertragen [zu engl. parse „(grammatisch) analysieren“] * * * Pạr|ser , der; s, [engl.… …   Universal-Lexikon

  • Parser (CGI language) — Infobox programming language name = Parser paradigm = multiparadigm macro, object oriented year = since 1997 designer = Konstantin Morshnev (Art. Lebedev Studio) developer = Alexander Petrosyan (Art. Lebedev Studio) latest release version = 3.2.2 …   Wikipedia

  • Parser Grammar Engine — The Parser Grammar Engine (originally Parrot Grammar Engine) or PGE is a compiler and runtime for a Perl 6 rules for the Parrot virtual machine. [cite web | url=http://search.cpan.org/ ltoetsch/parrot 0.2.2/compilers/pge/README | title=Parrot… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”