Syntaktische Analyse (Parsen)
Gegeben: eine kontextfreie Grammatik G und ein String w.
Fragen: gehort w zu L(G)?Welche Bedeutung hat w?
Vorgehen: Konstruiere Herleitungsbaum zu w
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 1
Syntaktische Analyse eines Programms
Gegeben: Syntax einer Programmierspracheund der Quelltext eines Programms.
Frage: ist dies ein syntaktisch korrektes Programm?Was soll dieses Programm bewirken ?
Aufgabe: Ermittle”Bedeutung“ des Programms,
Konstruktionsverfahren fur Herleitungsbaume(bzw. Syntaxbaume)
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 2
Syntaktische Analyse bzgl einer CFG
• Fur jede CFG gibt es einen Parse-Algorithmusmit worst case Laufzeit O(n3)
(n : Anzahl der Eingabesymbole)CYK: Cocke, Younger, Kasami,
falls Grammatik in Chomsky-Normalform(Alle Regeln von der Form N →W mit |W | ≤ 2
oder Earley-Algorithmus
CYK benutzt dynamisches Programmieren.erzeugt ein Tabelle: pro Paar (N, w) von Nichtterminal N und Wort wein Eintrag True wenn N →∗G w, sonst False
Beschrankung: w sind Unterstrings des Eingabewortes
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 3
Syntaktische Analyse bzgl einer CFG
Praxis: Fur jede Programmiersprachegibt es einen Parser, der effizient arbeitet,
d.h. in O(n), oder in O(n ∗ log(n))
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 4
Parse-Methoden und Beschrankungen
Beschrankung in dieser Vorlesung auf
• einfach implementierbare oder effiziente
• Nur fur eingeschrankte CFGs
• Verarbeitung des Zeichenstroms bzw. des Eingabewortesvon links nach rechts
• evtl. auch mit Vorausschau um einige Zeichen.
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 5
Parse-Methoden: Vorgehensweisen:
Top-Down: Es wird versucht eine Herleitung vorwarts,
vom Startsymbol aus, zu bilden (”forward-chaining“)
Bottom-Up: Es wird versucht eine Herleitung ruckwarts,
vom Wort aus, zu bilden . (”backward-chaining“).
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 6
Parse-Methoden: Vorgehensweisen:
Weiteres Unterscheidungsmerkmal:
R : Konstruktion einer Rechtsherleitung
L : Konstruktion einer Linksherleitung
Gangige Kombinationsmoglichkeiten:
• Top-Down-Verfahren zur Konstruktion einer Linksherleitung• Bottom-Up-Verfahren zur Konstruktion einer Rechtsherleitung
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 7
Beispiel
S ::= ABA ::= 0 | 1B ::= 8 | 9
Frage: Kann”09“ aus dieser Grammatik hergeleitet werden?
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 8
09-Beispiel: Top-down:
Start mit Startsymbol S
Rate die Produktionen; Nutze den zu parsenden String zur Steuerung
Bilde Restproblem
Ziel: Eingabestring bis zum Ende verarbeiten.
Ziel 09 09 9 εNT-Wort S AB BHerleitung S AB 0B 09
Die erzeugte Herleitung ist eine Linksherleitung.
Beachte”09“ wird von links nach rechts bearbeitet
Jedes Eingabezeichen bestimmt eindeutig die Produktion
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 9
09-Beispiel: Bottom-up:
Vorgehen: Regeln ruckwarts auf den gegebenen String anwendendas Startsymbol der Grammatik ist zu erreichen
09 ← A9 ← AB ← S
Eine Rechtsherleitung wurde konstruiert
Beachte: Manchmal sind mehrere Regeln anwendbarManchmal muss man den Teilstring raten,
auf den eine Produktion (ruckwarts) angewendet werden soll.
Im Beispiel: Gleicher Herleitungsbaum
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 10
Beispiel: Suche nach der Herleitung
S ::= A |BA ::= 0A | 1B ::= 0B | 2
Kann”002“ hergeleitet werden?
Ziel 002 002 02 2NT-Wort S A A AHerleitung S A 0A 00A ?
”002“ kann nur aus B hergeleitet werden:
Ziel 002 002 02 2NT-Wort S B B BHerleitung S B 0B 00B 002
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 11
Beispiel: Bemerkungen
Ein deterministischer Top-Down-Parser
muss beim ersten Zeichen von”002“ entscheiden,
ob A, oder B.
Diese Wahl kann falsch sein.
Misslingt eine Herleitung, so muss der Parser zurucksetzen
”Backtracking“
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 12
Rekursiv absteigende Parser
Rekursiv absteigender Parser / Syntaxanalyse
ist an der Form der Regeln der Grammatik orientiert
Methode: Top-Down-Prufung der Anwendbarkeit der Regeln
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 13
Struktur eines rekursiv absteigenden Parsers
• Top-Down bzgl. der Grammatik.
• Eingabewort von links nach rechts
• Backtracking, falls Sackgasse
• Konstruktion einer Linksherleitung
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 14
Struktur eines rekursiv absteigenden Parsers
• Pro Nichtterminal N existiert ein Parser PNder die formale Sprache zu N erkennt.Eingabe: StringAusgabe: Syntaxbaum zu Prefix der Eingabe;
Reststring• Parser zu G ist Pσ zum Startsymbol σ
• Gegeben alle N-Regeln: N → w1 | . . . | wn
PN probiert fur alle wi aus,ob diese zum Anfang des Eingabestrings passenPasst keine, dann
”Fehlschlag“
• Prufung, ob eine Regel ob N → w1 passt:wi = wi1wi2 . . . wim von links nach rechts durchgehenJeweils Parser Pwij aufrufen.I.a. rekursiver Aufruf, falls wij Nichtterminal.
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 15
Eigenschaften eines rekursiv-absteigenden
Parsers
• I.a. exponentiell.• Liefert alle Linksherleitungen fur alle Prafixe• Leicht implementierbar• Leicht erweiterbar auf weitere Einschrankungen• Terminiert nicht fur bestimmte (linksrekursive) Grammatiken,
obwohl eine Herleitung existiert:
Beispiel A ::= A+A | A-A | 1 | . . . | 9
Eingabe: 1+1 : Aber: nur die erste Regel wird (jeweils rekursiv) ver-
sucht:
(A,1+1) → (A+A,1+1) → ((A+A)+A, 1+1) → . . .
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 16
Rekursiv-absteigende Parser
Anmerkung
Programme von Programmiersprachen kann man i.a.
in O(n) oder O(n ∗ log(n)) parsen,
Effiziente rekursiv-absteigende Parser benotigen i.a.:
• Erweiterungen wie Vorausschau
• Umbau der Grammatik (Optimierung der Grammatik)
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 17
Funktionale Kombinator-Parser
Implementierung von rekursiv-absteigenden Parsern in Haskell
Vorteile relativ leicht verstandliche Programmierung1-1-Ubersetzung der Regeln in Programmcode
Pro Nichtterminal N eine Funktion parserN:: String -> [(String, R)]
Prafix der Eingabe 7→(Rest der Eingabe, Resultat (z.B. Syntaxbaum) )
Um Backtracking zu implementieren:
Liste von erfolgreichen Ergebnissen
verzogerte Auswertung ergibt richtige Reihenfolge der Abarbeitung.
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 18
Haskell-Implementierung der
Parser-Kombinatoren
Kombinator (kombiniert Parser)Z.B. Alternative, Sequenz, Resultat-Umbau
module RekParsKomb where
import Char
infixr 6 <*>, <*, *>
infixr 4 <|>, <!>
infixl 5 <@
type Parser a b = [a] -> [([a],b)]
erkennt ein Zeichen:
symbol :: Eq s => s -> Parser s s
symbol a [] = []
symbol a (x:xs) | a ==x = [(xs,x)]
| otherwise = []
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 19
Haskell: Parser-Kombinatoren (2)
erkennt einen String:
token :: Eq s => [s] -> Parser s [s]
-- token :: Eq s => [s] -> Parser s [s]
token k xs | k == (take n xs) = [(drop n xs, k)]
| otherwise = []
where n = length k
testet ein Zeichen der Eingabe:
satisfy :: (s -> Bool) -> Parser s s
satisfy p [] = []
satisfy p (x:xs) = [(xs,x) | p x]
epsilon :: Parser s ()
epsilon xs = [(xs,())]
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 20
Haskell: Parser-Kombinatoren (3)
immer erfolgreich:
succeed :: r -> Parser s r
succeed v xs = [(xs,v)]
immer fehlschlagend:
pfail :: Parser s r
pfail xs = []
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 21
Haskell: Parser-Kombinatoren (4)
Sequenzkombinator :
(<*>) :: Parser s a -> Parser s b -> Parser s (a,b)
(p1 <*> p2) xs = [(xs2, (v1,v2))
| (xs1,v1) <- p1 xs,
(xs2,v2) <- p2 xs1]
Alternativkombinator :
(<|>) :: Parser s a -> Parser s a -> Parser s a
(p1 <|> p2) xs = p1 xs ++ p2 xs
Alternativkombinator-2: nur das erste Ergebnis:
(<!>) :: Parser s a -> Parser s a -> Parser s a
(p1 <!> p2) xs = take 1 (p1 xs ++ p2 xs)
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 22
Haskell: Parser-Kombinatoren (5)
ignoriert Blanks am Anfang:
sp :: Parser Char a -> Parser Char a
sp p = p . dropWhile isSpace
eliminiert alle Whitespaces:
wsp :: Parser Char a -> Parser Char a
wsp p = p . filter (\x -> not (isSpace x))
testet, ob die ganze Eingabe konsumiert wurde :
just :: Parser s a -> Parser s a
just p = filter (null . fst) . p
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 23
Haskell: Parser-Kombinatoren (6)
Operation auf dem Ergebnis des Parse :
(<@) :: Parser s a -> (a-> b) -> Parser s b
(p <@ f) xs = [(ys, f v) | (ys,v) <- p xs]
– ignoriert rechtes Ergebnis:
(<*) :: Parser s a -> Parser s b -> Parser s a
p <* q = p <*> q <@ fst
ignoriert linkes Ergebnis:
(*>) :: Parser s a -> Parser s b -> Parser s b
p *> q = p <*> q <@ snd
list (x,xs) = x:xs
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 24
Haskell: Parser-Kombinatoren (7)
erkennt Folge. d.h. entspricht *:
many :: Parser s a -> Parser s [a]
many p = p <*> many p <@ list
<|> succeed []
many1 p = p <*> many p <@ list
digit :: Parser Char Int
digit = satisfy isDigit <@ f
where f c = ord c - ord ’0’
erkennt Zahl:
natural :: Parser Char Int
natural = many1 digit <@ foldl f 0
where f a b = a*10 + b
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 25
Haskell: Parser-Kombinatoren (8)
Nimmt nur die erste (maximale) Alternative des many: nur erlaubt,
wenn die Grammatik diese Alternativen nicht benotigt
manyex :: Parser s a -> Parser s [a]
manyex p = p <*> many p <@ list
<!> succeed []
many1ex p = p <*> manyex p <@ list
option p = p <@ (\x->[x])
<!> epsilon <@ (\x-> [])
Nimmt nur die erste (maximale) Alternative bei Zahlen:
naturalex :: Parser Char Int
naturalex = many1ex digit <@ foldl f 0
where f a b = a*10 + b
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 26
Haskell: Parser-Kombinatoren (9)
Erkennt Klammerung und ignoriert den Wert der Klammern:
pack:: Parser s a -> Parser s b -> Parser s c -> Parser s b
pack s1 p s2 = s1 *> p <* s2
Erkennt Infix-Folge wie z.B. (1+2+3+4+5): Liste der Argumente:
opSeqInf psymb parg = (parg <*> many (psymb *> parg)) <@ list
paarf f = \(x,y) -> f x y
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 27
Beispiel arithmetische Ausdrucke
Grammatik
Ex ::= PlusPlus ::= SigZ | SigZ PlusrestPlusRest ::= + SigZ PlusRest | epsSigZ ::= B | - BB ::= Z | ( Ex )Z ::= 0 | . . . | 9
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 28
Beispiel arithmetische Ausdrucke
plusausdruecke = just pAriEx
pAriEx :: Parser Char Integer
pAriEx = (wsp pAriPlus)
pAriPlus = (opSeqInf (symbol ’+’) pAriSigZ) <@ sum
Die direkte Implementierung ware:
(pAriSigZ <*> many ((symbol ’+’) *> pAriSigZ)) <@ list
pAriZsymbol = naturalex
pAriSigZ = pAriB <|> (symbol ’-’) *> pAriB <@ (negate)
pAriB = pAriZsymbol <|> (pack (symbol ’(’) pAriEx (symbol ’)’))
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 29
Rekursiv-pradiktive Parser
Optimierte rekursiv absteigende Parser
fur eingeschrankte Grammatiken ( LL(1) ).
Eigenschaft
Die anzuwendende Produktion ist immer eindeutig festgelegt
• abhangig vom aktuellen Nichtterminal und• dem nachsten Symbol der Resteingabe (Lookahead-Symbol)
• kein Zurucksetzen notwendig,• deterministisch Abarbeitung der Eingabe von links nach rechtsAber: man kann nicht fur jede kontextfreie Grammatik
einen rekursiv-pradiktiven Parser konstruieren.
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 30
Rekursiv-pradiktive Parser
Eindeutige Zuordnung:
(Lookahead-Symbol, aktuelles Nichtterminal) 7→ Regel
Tabellengesteuerter rekursiv-pradiktiver Parser:
Die obige Tabelle inklusive Fehlereintrage
reicht aus zur Steuerung des Parsers
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 31
Rekursiv-pradiktive Parser
Sind A→ w1 | . . . | wn die Regeln zu A und
im Zustand A ist a das erste Symbol der Eingabe:
nur eine Regel A→ wi darf anwendbar sein.
Beispiel:
A → bCD | aEF | cG | HH → dabc. . .
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 32
Rekursiv-pradiktive Parser
Sonderrolle:
Es gibt Regel A→ wi mit wi →∗ ε:
Diese wird ausgewahlt, wenn:
• keine passende rechte Seite fur das Lookahead-Symbol und• das Lookahead-Symbol kann auf A folgen und• es gibt nur eine solche Regel fur A
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 33
Rekursiv-pradiktive Parser, ε-Fall
Beispiel:
S → AB | ACA → bCD | aEF | cG | HH → ε. . .B → dAC → eA
Im Zustand A und bei Eingabesymbol d:
A→ H wird ausgewahlt.
Beachte: Gesamtzustand = gesamter Aufrufstack
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 34
FIRST- und FOLLOW-Mengen
Definition Sei G eine CFG mit S als Startsymbol.
Fur w ∈ (T ∪N)∗ und A ∈ N :
first(w) := {x ∈ T | w →∗ xv fur ein Wort v ∈ T ∗}∪{ε} wenn w →∗ ε
follow(A) := {x ∈ T | S →∗ v1Axv2 fur Worte v1, v2 ∈ T ∗}
Diese Mengen kann man in allen rekursiv-absteigenden Parsern
zur Vermeidung von Backtracking verwenden.
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 35
Berechnung von first :
Fixpunktiteration:
f0(Ai) := ∅ fur alle ifj+1(Ai) :=
⋃i fj(wi) wenn Ai ::= w1 | . . . | wk die Regeln zu A sind.
Stopp, wenn sich nichts mehr andert.
Hierbei wird verwendet:
fj(aw) := {a} fur jedes Terminal afj(Aw′) := fj(A) wenn ε 6∈ fj(A)fj(Aw′) := (fj(A) \ {ε}) ∪ fj(w
′) wenn ε ∈ fj(A)fj(ε) := {ε}
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 36
Berechnung von follow :
g0(Ai) := ∅ fur alle igj+1(Ai) := Vereinigung folgender Mengen:
first(w′) ∩ T fur jede Regel Ak → wAiw′
gj(Ak) fur jede Regel Ak → wAiw′
mit ε ∈ first(w′)
Stopp, wenn gj+1(A) = gj(A) fur alle Nichtterminale A.
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 37
Beispiel fur first: Fixpunktberechnung
Ex ::= PlusPlus ::= SigZ | SigZ PlusrestPlusRest ::= + SigZ PlusRest | epsSigZ ::= B | - BB ::= Z | ( Ex )Z ::= 0 | . . . | 9
Ex Plus Plus SigZ B ZRest
∅ ∅ ∅ ∅ ∅ ∅∅ ∅ +, ε - ( 0,...,9
∅ - +, ε -,( 0,...,9, ( 0,...,9
- -,( +, ε 0,...,9, (,- 0,...,9, (,- 0,...,9
-,( 0,...,9, (,- +, ε 0,...,9, (,- 0,...,9, (,- 0,...,9
0,...,9, (,- 0,...,9, (,- +, ε 0,...,9, (,- 0,...,9, (,- 0,...,9
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 38
Beispiel fur follow :
Ex ::= PlusPlus ::= SigZ | SigZ PlusrestPlusRest ::= + SigZ PlusRest | epsSigZ ::= B | - BB ::= Z | ( Ex )Z ::= 0 | . . . | 9
Ex Plus Plus SigZ B ZRest
) ∅ ∅ + ∅ ∅) ) ∅ + + ∅) ) ) + + +
) ) ) +,) + +
) ) ) +,) +,) +
) ) ) +,) +,) +,)
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 39
Konstruktion eines rekursiv-pradiktiven Parsers
Bedingungen fur die Eindeutigkeit:
• Fur jedes A mit A ::= w1 | . . . | wn
falls ε 6∈ first(wi) fur alle i:die Mengen first(wi) mussen paarweise disjunkt sein.
• Fur jedes A mit A ::= w1 | . . . | wn
falls ε ∈ first(wj) fur ein j:die Mengen first(wi), i = 1, . . . , n und follow(A) mussen
paarweise disjunkt sein.
• Fur jedes A mit A ::= w1 | . . . | wn
gibt es maximal ein wi mit ε ∈ first(wi)
Parser benotigt Tabelle (Ai, a) 7→ Rj
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 40
Vorgehen des LL(1)-Parsers
Gegeben a, das Symbol und das aktuelle Nichtterminal A:
• Ist a ∈ first(wi) fur eine Regel A ::= wi, dann nehme diese
Regel.• Ist a 6∈ first(wi) fur alle Regeln A ::= wi,
dann gibt es maximal eine Regel A ::= w mit first(w) = ∅Falls a ∈ follow(A), dann diese Regel.
• Wenn auch dann keine passende Alternative existiert, wird mit
Fehler abgebrochen.
Vorteil: genaue und fruhe Fehlererkennung
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 41
Beispiel: vereinfachte Grammatik fur Ausdrucke
Expr ::= Term RestRest ::= + Term Rest | − Term Rest | εTerm ::= 0 | . . . | 9
• first(Term Rest) = {0,1,2,3,4,5,6,7,8,9}• first(+ Term Rest) = {+},
first(− Term Rest) = {−}• first(Expr ) = first(Term ) = {0,1,2,3,4,5,6,7,8,9}• first(Rest) = {+,−, ε}
• follow(Expr) = ∅.• follow(Rest) = ∅.• follow(Term) = {+,−}.
Diese Grammatik hat somit die LL(1)-Eigenschaft.
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 42
Beispielparser zur Grammatik
E ::= T RR ::= + T R | - T R | εT ::= 0 | . . . | 9
Die Parsefunktionen haben als Wert: (Resteingabe, Pbaum)
data Pbaum = Pblatt Int
| PExp Pbaum Pbaum
| PRest Char Pbaum Pbaum
| PLeer
deriving (Show, Eq)
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 43
Beispielparser zur Grammatik (2)
parseTerm [] = error "Ziffer erwartet; rest = nil"
parseTerm eingabe@(symbol:rest) =
if not (symbol ‘elem‘ [’0’..’9’] )
then error ("Ziffer erwartet; rest = " ++ eingabe)
else (rest,Pblatt (fst (head (reads [symbol]))))
parseRest [] = ([],PLeer)
parseRest eingabe@(operator: rest) =
if not (operator ‘elem‘ [’+’,’-’] )
then error ("+ oder - erwartet; rest = " ++ eingabe)
else
let (rest1,resultat1) = parseTerm rest
(rest2,resultat2) = parseRest rest1
in (rest2, PRest operator resultat1 resultat2)
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 44
Beispielparser zur Grammatik (3)
parseExp :: [Char] -> (String,Pbaum)
parseExp [] = error ("Ziffer erwartet; rest = nil")
parseExp (eingabe@(symbol: rest)) =
if not (symbol ‘elem‘ [’0’..’9’] )
then error ("Ziffer erwartet; rest = " ++ eingabe)
else
let (rest1,resultat1) = parseTerm eingabe
(rest2,resultat2) = parseRest rest1
in (rest2, PExp resultat1 resultat2)
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 45
Beispielparser zur Grammatik (4)
Testbeispiele:
test1::(String,Pbaum)
test1 = parseExp "1 + 2 - 3"
test2::(String,Pbaum)
test2 = parseExp "1+2-3"
Main> test2
("",PExp (Pblatt 1) (PRest ’+’ (Pblatt 2)
(PRest ’-’ (Pblatt 3) PLeer))) :: (String,Pbaum)
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 46
Beispielparser zur Grammatik (3)
Parsebaum:
PExp
||xxxx
xxxx
x
&&LLLLLLLLLL
1 PRest
xxqqqqqqqqqqqq
�� &&NNNNNNNNNNNN
+ 2 PRest
xxppppppppppppp
�� &&NNNNNNNNNNNN
− 3 PLeer
Er entspricht der Grammatik,
aber noch nicht der gewunschten Struktur
des arithmetischen Ausdrucks.
Man braucht eine Nachbearbeitung des Parsebaumes.
Praktische Informatik 2, SS 2005, Folien Kap.4,−2, (15. Juni2005) Seite 47