Syntaktische Analyse (Parsen) · Syntaktische Analyse bzgl einer CFG • F¨ur jede CFG gibt es...

Preview:

Citation preview

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

Recommended