Syntaktische Analyse (Parsen) · Syntaktische Analyse bzgl einer CFG • F¨ur jede CFG gibt es einen Parse-Algorithmus mit worst case Laufzeit O(n3) (n : Anzahl der Eingabesymbole)

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)


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


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))


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.


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“).


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


Beispiel

S ::= ABA ::= 0 | 1B ::= 8 | 9

Frage: Kann”09“ aus dieser Grammatik hergeleitet werden?


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


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


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


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“


Rekursiv absteigende Parser

Rekursiv absteigender Parser / Syntaxanalyse

ist an der Form der Regeln der Grammatik orientiert

Methode: Top-Down-Prufung der Anwendbarkeit der Regeln


Struktur eines rekursiv absteigenden Parsers

• Top-Down bzgl. der Grammatik.

• Eingabewort von links nach rechts

• Backtracking, falls Sackgasse

• Konstruktion einer Linksherleitung


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.


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) → . . .


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)


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.


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 = []


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,())]



immer erfolgreich:

succeed :: r -> Parser s r

succeed v xs = [(xs,v)]

immer fehlschlagend:

pfail :: Parser s r

pfail xs = []



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)



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



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



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



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



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


Beispiel arithmetische Ausdrucke

Grammatik

Ex ::= PlusPlus ::= SigZ | SigZ PlusrestPlusRest ::= + SigZ PlusRest | epsSigZ ::= B | - BB ::= Z | ( Ex )Z ::= 0 | . . . | 9


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 ’)’))


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.



Eindeutige Zuordnung:

(Lookahead-Symbol, aktuelles Nichtterminal) 7→ Regel

Tabellengesteuerter rekursiv-pradiktiver Parser:

Die obige Tabelle inklusive Fehlereintrage

reicht aus zur Steuerung des Parsers



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. . .



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


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


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.


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(ε) := {ε}


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.


Beispiel fur first: Fixpunktberechnung


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


Beispiel fur follow :


Ex Plus Plus SigZ B ZRest

) ∅ ∅ + ∅ ∅) ) ∅ + + ∅) ) ) + + +

) ) ) +,) + +

) ) ) +,) +,) +

) ) ) +,) +,) +,)


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.


falls ε ∈ first(wj) fur ein j:die Mengen first(wi), i = 1, . . . , n und follow(A) mussen

paarweise disjunkt sein.


gibt es maximal ein wi mit ε ∈ first(wi)

Parser benotigt Tabelle (Ai, a) 7→ Rj


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


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.


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)


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)



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)



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)



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.


Documents

Syntaktische Analyse (Parsen) · Syntaktische Analyse bzgl einer CFG • F¨ur jede CFG gibt es einen Parse-Algorithmus mit worst case Laufzeit O(n3) (n : Anzahl der Eingabesymbole)