View
1
Download
0
Category
Preview:
Citation preview
Grundlagen der Programmierung 2(Comp-E)
Prof. Dr. Manfred Schmidt-Schauÿ
Künstliche Intelligenz und Softwaretechnologie
31. Mai 2007
LR-Parser, Shift-Reduce-Verfahren
Grundlagen der Programmierung 2 Comp-E) - 1 -
• Bottom-Up-Syntaxanalyse
• LR-Parser L: Eingabe von links nach rechts;R: Rechtsherleitung
• Shift-Reduce-Verfahren
• Beachte:Kein Backtrackingnicht auf jede Grammatik anwendbar
Beispiel
Grundlagen der Programmierung 2 Comp-E) - 2 -
E ::= E + EE ::= E * EE ::= (E)E ::= a | b | c
(Eine) Rechtsherleitung von c + b * a
E → E + E→ E + E * E→ E + E * a→ E + b * a→ c + b * a
Vorsicht: es gibt eine weitere Rechtsherleitung
Begriff: Handle
Grundlagen der Programmierung 2 Comp-E) - 3 -
Idee: Herstellung einer Rechtsherleitung ruckwarts.
Handle: rechte Seite v einer Regel
Genauer: Vorkommen von v in einem Wort w,so dass eine Rechtsherleitung ruckwarts moglich ist.
Genauer+: Teil einer Rechtsherleitung aus Startsymbol
Beispiel
Grundlagen der Programmierung 2 Comp-E) - 4 -
E ::= E + EE ::= E * EE ::= (E)E ::= a | b | c
(Eine) Rechtsherleitung von c + b * a mit Handles
E → E + E→ E + E * E→ E + E * a→ E + b * a→ c + b * a
Handle: Benutzung
Grundlagen der Programmierung 2 Comp-E) - 5 -
Handle: Hilfsmittel zur Konstruktion einer Rechtsherleitungin umgekehrter Reihenfolge
Handles sind nicht immer eindeutig
Fortsetzung des Beispiels
Grundlagen der Programmierung 2 Comp-E) - 6 -
Konstruiere Rechtsherleitung von c + b * a
durch Ersetzen von Handles
hergeleitetes Wort Handle Produktionc + b ∗ a c E→ cE + b ∗ a b E→ bE + E ∗ a a E→ aE + E ∗ E E ∗ E E→ E ∗ EE + E E + E E→ E + EE
Methode: Schieben-Reduzieren(Shift-Reduce)
Grundlagen der Programmierung 2 Comp-E) - 7 -
Shift-Reduce Syntax-Analysemethode
Zustand wahrend der Analyse:Aktuelles Zeichen ist zu verarbeitenRest der EingabeStack das bisher (ruckwarts) hergeleitete Wort
Stack + aktuelles Zeichen + Rest der Eingabe = Gesamtwort
Methode: Schieben-Reduzieren (Shift-Reduce)
Grundlagen der Programmierung 2 Comp-E) - 8 -
Aktionen der Analyse:
Schieben: Lesen eines Zeichens der Eingabe und Ablage auf den Stack
Reduzieren: Ersetzen eines obersten Teils des Stacks, des Handle,
mittels einer Produktion ruckwarts
Die Auswahl der Produktion ist abhangig
vom Anfang der Resteingabe und vom Inhalts des Stacks.
Beispiel
Grundlagen der Programmierung 2 Comp-E) - 9 -
$ bezeichnet das Ende der Eingabe und den Boden des Stacks
Stack Eingabe Aktion$ c + b*a$ schiebe$c + b*a$ reduziere mit E ::= c$E + b*a$ schiebe; schiebe$E+b *a$ reduziere mit E ::= b$E+E *a$ schiebe$E+E* a$ schiebe$E+E*a $ reduziere mit E ::= a$E+E*E $ reduziere mit E ::= E*E$E+E $ reduziere mit E ::= E+E$E $ akzeptiere
Die 4 Parser-Aktionen:
Grundlagen der Programmierung 2 Comp-E) - 10 -
Schieben: Zeichen von Eingabe auf Stack
Reduzieren: Handle, d.h. ein oberes Stuck des Stacks durch ein
Nichtterminal ersetzen.
Akzeptieren: Wenn Stack = Startsymbol und die Eingabe leer
Fehlererkennung: Wenn weder Schiebe- noch Reduzieraktion moglich.
Hierbei gilt: das Handle kann nur ein oberer Teil des Stacks sein
Shift-Reduce-Parser: Eigenschaften
Grundlagen der Programmierung 2 Comp-E) - 11 -
Shift-Reduce-Parser sind deterministisch:
Berechnung der nachsten Aktion auf der Basis
des Stackinhalts
und des ersten Symbols der Eingabe
• Shift-Reducer-Parser konnen tabellengesteuert arbeiten.
• Die manuelle Erzeugung der Tabellen aus der Grammatiken
ist komplex
• ε-Produktionen werden in Shift-Reduce-Parsern vermieden.
Korrespondenz: Aktionen zu Rechtsherleitung
Grundlagen der Programmierung 2 Comp-E) - 12 -
Notation: v sei Terminalwort w;v ≡ Stack;Eingaberest
w0AvA7→w−−−−→ w0wv
w0A; vreduz.←−−−− w0w; v
Regeln A 7→ wAB, B 7→ wB
w0AvA7→wAB−−−−−−→ w0wABv
B 7→wB−−−−−→ w0wAwBv
w0A; vreduz.←−−−− w0wAB; v
reduz.←−−−− w0wAwB; v
Korrespondenz: Aktionen zu Rechtsherleitung
Grundlagen der Programmierung 2 Comp-E) - 13 -
Regeln: A 7→ wABabc B 7→ wB↓ ↓
w0Av → w0wABabcv → w0wAwBabcvw0A; v ← w0wABabc; v ← w0wAB; abcv ← w0wAwB; v
↑ ↑ ↑Reduzieren 3 X Schieben Reduzieren
Shift-Reduce-Parser: Fehlerbehandlung
Grundlagen der Programmierung 2 Comp-E) - 14 -
• Schiebe-Reduziere-Konflikt:
unklarer Zustand: Schieben oder Reduzieren? Die Tabelle enthalt
in diesem Fall bereits einen Fehlerausgang.
• Reduziere-Reduziere-Konflikt:
unklarer Zustand: Reduzieren mit welcher Regel?
2 verschiedene Handles, oder ein Handle und 2 Regeln.
• Keine anwendbare Regel
Das sind auch Fehlermeldungen von LR-Parser-Generatoren
Operatorgrammatiken,Operator-Prioritats-Syntaxanalyse
Grundlagen der Programmierung 2 Comp-E) - 15 -
Operatorgrammatiken erlauben die Konstruktion
eines Shift-Reduce Parsers fur:
Basisgrammatik und weitere Angaben zu Operatoren
Operatorgrammatik
Grundlagen der Programmierung 2 Comp-E) - 16 -
Eine Operatorgrammatik liegt vor, wenn:
• keine ε-Produktion• keine rechte Seite einer Produktion hat
direkt benachbarte Nichtterminale• Terminale sind Operatoren oder Klammern,
oder Bezeichner (eigentlich ein Nichtterminal)• wesentliches Nichterminal: Ausdrucke
Operatorgrammatiken; Beispiel
Grundlagen der Programmierung 2 Comp-E) - 17 -
E ::= E + E | − E | E − E | E ∗ E | E/E | (E) | EˆE | E! | Id
Hierbei steht Id (Identifier) fur ein Nichtterminal,
beispielsweise Konstanten, oder Variablen.
Operatoren sind: +,-,*,\,^,!
Klammern sind vorhanden
E: Nichtterminal fur Ausdrucke.
Beachte, dass diese Grammatik mehrdeutig ist:
1-2-3 hat 2 Parsebaume
Operatorgrammatiken : Eindeutigkeit
Grundlagen der Programmierung 2 Comp-E) - 18 -
Weitere Angaben zu den Operatoren um Eindeutigkeit zu erreichen:
• Stelligkeit: wieviele Argumente bindet der Operator?I.a.: 1 oder 2.
• Infix, Prefix,
Postfix:
welchen Ausdruck (welche Ausdrucke) bindet
der Operator?• Prioritaten welcher Operator bindet starker? I.a. sind die
Prioritaten naturliche Zahlen• Assoziativitat: Ist der Operator rechtsassoziativ oder linksasso-
ziativ, oder nicht assoziativ?
Z.B. a+b+c kann als a+(b+c) (rechtsassoziativ)
oder als (a+ b)+ c (linksassoziativ) geklammert
werden.
Operatorgrammatiken; Beispiel
Grundlagen der Programmierung 2 Comp-E) - 19 -
Basisgrammatik:
E ::= E + E | − E | E − E | E ∗ E | E/E | (E) | EˆE | E! | Id
wird eindeutiger durch die Eigenschaften:
• +, ∗, /, ˆ sind zweistellige Infixoperatoren.• − kann zweistelliger Infix- oder einstelliger Prafixoperator sein.• Prioritaten: ! vor ˆ vor einstelligem − vor ∗, / vor +,−.• +, ∗, /,− linksassoziativ, ˆ ist rechtsassoziativ.
1 + 2!ˆ3 entspricht 1 + ((2!)ˆ3)1− 3− 5 ∗ 6! entspricht ((1− 3)− (5 ∗ (6!))
Operatorgrammatiken
Grundlagen der Programmierung 2 Comp-E) - 20 -
Es gilt:
Basisgrammatik + Eigenschaften der Operatoren
ist in eine CFG kodierbar
Aber Datengrundlage eines Shift-Reduce Parser ist
die Basisgrammatik und Eigenschaften der Operatoren
nicht die volle Grammatik.
Operatorgrammatiken, Beispiel
Grundlagen der Programmierung 2 Comp-E) - 21 -
Gegeben: Postfix-Operator ! mit hoher Prioritat,einstelliges − mit geringerer Prioritatbinares + mit geringster Prioritat, linksassoziativZahl sei Nichtterminal fur Zahlenkonstanten.
Grammatik dazu:
E ::= PlusEFakE ::= Zahl | FakE ! | (PlusE)MinE ::= FakE | - MinEPlusE ::= MinE | PlusE + FakE
• - - 1 ! ! ist als - (- ((1!)!)) erkennbar.• Vermutlich ist diese Grammatik eindeutig.• Diese Grammatik ist linksrekursiv
Shift-Reduce Syntaxanalyse fur Operatorgram-matiken
Grundlagen der Programmierung 2 Comp-E) - 22 -
Vorgehen:
Auf dem Stack sind in der Reihenfolge der Eingabe:
• die bisherigen Operatoren,• die offenen Klammern und• Bezeichner und erkannte Ausdrucke (d.h. Herlei-
tungsbaume)
Shift-Reduce Syntaxanalyse; Aktionen
Grundlagen der Programmierung 2 Comp-E) - 23 -
• Wenn ein Bezeichner in der Eingabe ist, dann Schieben
manchmal danach reduzieren, Z.B., wenn −;E auf dem
Stack
• Wenn Tokenstrom zu Ende, dann reduzieren.
• Wenn”(“, dann schieben
• Bei”)“: Wenn der Stack noch offene Operatoren enthalt,
dann reduzieren.
Am Ende muss auf dem Stack”(“ ; E stehen:
Der Klammerausdruck (E) wird erkannt,
und der Syntaxbaum fur E bleibt auf dem Stack.
Operatorgrammatiken: Beispiele
Grundlagen der Programmierung 2 Comp-E) - 24 -
Stack Eingabe-Rest
$E +E $ Reduzieren, da keine Argumente mehr folgen
$(E +E )* 5 + 6 ! $ Reduzieren, da keine Argumente mehr folgen
$(E )* 5 + 6 ! $ Schieben, da Klammerausdruck beendet
$E + (3 + 5 ! $ Schieben
$E : E : 5 : [] $ Schieben da : rechtsassoziativ
Operatorgrammatiken: Beispiele
Grundlagen der Programmierung 2 Comp-E) - 25 -
Stack Rest der Eingabe
$E *E + 5 * 6 ! $ Reduzieren, da ∗ > +
$E +E * 5 + 6 ! $ Schieben, da ∗ > +
$E + E + 5 * 6 ! $ Reduzieren, da + linksassoziativ
$E : E : 5 : [] $ Schieben da : rechtsassoziativ
Operatorgrammatiken: Beispielablauf
Grundlagen der Programmierung 2 Comp-E) - 26 -
$ 1 - 3 - 5 * 6 ! $ S$1 - 3 - 5 * 6 ! $ R$E - 3 - 5 * 6 ! $ S$E - 3 - 5 * 6 ! $ S$E - 3 - 5 * 6 ! $ R$E - E - 5 * 6 ! $ R$E - 5 * 6 ! $ S$E - 5 * 6 ! $ S$E - 5 * 6 ! $ R$E - E * 6 ! $ S$E - E* 6 ! $ S$E - E*6 ! $ R$E - E*E ! $ S$E - E*E! $ R$E - E*E $ R$E - E $ R$E $
Erkannt wurde der Ausdruck: ((1− 3)− (5 ∗ (6!)))
Operatorgrammatiken: Bemerkungen
Grundlagen der Programmierung 2 Comp-E) - 27 -
• Der Parser baut nicht direkt auf einer Grammatik auf.
Definition der erkannten formalen Sprache?• Fehler in der Eingabe sind gut erkennbar:
Wenn es keine erlaubte Aktion mehr gibt• Mehrdeutigkeiten werden durch die Implementierung des Parsers
aufgelost.
Bei gleicher Prioritat”gewinnt“ der fruhere Operator.
• Zweideutigkeit von ’−’ (einstellig Prafix und zweistellig Infix)
wird entschieden durch folgende Vereinbarung: wenn links von −kein Operand, dann einstellig, sonst zweistellig.
• Operatoren, die links mehr als ein Argument konsumieren, sind i.a.
nicht zugelassen.• Die Semantik kann direkt aus dem Syntaxbaum abgelesen werden.
Operatorgrammatiken: Bemerkungen
Grundlagen der Programmierung 2 Comp-E) - 28 -
• Vorteil: Die Operatoren und deren Eigenschaften konnen vom Be-
nutzer definiert werden ( siehe Haskell)• Nachteil einer klammerfreien Eingabe:
vom Benutzer gewollter und vom Parser erkannter Ausdruck konnen
verschieden sein.
auch unter strengem Typsystem usw.
Abhilfe: wenn man unsicher ist, mehr Klammern setzen.• Mogliche Erweiterung: Prioritatsrelationen• Beim Testen muss man auch falsche Eingaben mittesten• Unproblematische Erweiterung in Haskell :
(+) , (+ 1) (1 +) sind ebenfalls Ausdrucke
• es gibt Parsergeneratoren: i.a. Shift-Reduce, z.B. yacc, Happy
Recommended