Parsec

Für Haskell gibt es eine vielzahl von Parsern. Hier sei nur der bottom-up Parser Happy und der top-down Parser Parsec erwähnt. Im folgenden wird eine kleine Einführung in Parsec vollzogen.

Was ist Parsec?

Parsec ist eine mächtige Parser Bibliothek. Es handelt sich hierbei um einen top-down Parser unter der Verwendung von Monaden. Im Allgemeinen wird emphParsec als LL[1]- Parser betrieben. Backtracking ist auch möglich und wird im Kapitel   ausführlich behandelt. Parsec ermöglicht die Ausgabe von aussagekräftigen Fehlermeldungen bei syntaktischen Fehlern. Desweiteren lässt sich mit Parsec eine lexikalische Analyse und das Parsen in einem realisieren. Es ist nicht wie häufig notwendig, jeweils zwei unterschiedliche Tools zu verwenden ( z.B. Lex und Yacc ).

Bei weiterführendem Interesse ist der interessierte Leser auf das Referenzenhandbuch von Parsec verwiesen. Ein Verweis auf die Internetseite findet sich im Anhang.

Beispiele mit Parsec

Bevor Parsec in einem Modul verwendet werden kann, muss die Bibliothek im Haskellmodul bekannt gemacht werden.

> module Main where
> import Parsec

Nachdem Parsec importiert ist, sind die ersten einfachen Beispiele möglich. Die Funktion many ist aus dem Kapitel   schon bekannt. In Parsec ist diese Funktion ebenfalls implementiert. Der folgende Parser simple1 erwartet eine Liste von Buchstaben. Die verwendete Funtion letter ist in hugs vordefiniert.

> -- Ein Parser fuer Identifier 
> simple1 :: Parser [Char] 
> simple1 = many letter

Die Funktionsweise sei Anhand des folgenden Aufruf verdeutlicht. Die Funktion parseTest ist von Parsec und dient zum einfachen Testen von Parsern.

? parseTest simple1 "abc123" 
"abc"

Die Sequenz und Auswahl

Wie schon im Kapitel   über Parser kombinatoren, wurde deutlich wie wichtig ein Operator für Sequenzen und einer für die Auswahl ist. Durch die Verwendung von Monaden in Parsec, muss für die Sequenz kein extra Operator erstellt werden. Es wird der Monadenoperator do für Sequenzen verwendet.

Der folgende Parser openClos0 erwartet ein Klammernpaar.

> openClose0 :: Parser Char
> openClose0  =  do{ char '('
>                  ; char ')' 
>                  }

Allerdings ist ein Klammernpaar nicht sonderlich spannend. Eine weitaus spannendere Version eines Klammernpaarparsers könnte wie folgt aussehen.

openClose1 :: Parser ()
openClose1  = do{ char '('
                ; openClose1
                ; char ')'
                ; openClose1
                }
              <|> return ()

Durch den eigenen rekursiven Aufruf erwartet openClose1 eine Sequenz von Klammerpaaren. Der <|> Operator ist die Auswahl. Wird keine öffnende Klammer gefunden, so wird return() aufgerufen und die Rekursion beendet.

Parser mit Semantik

Ein ähnlicher Parser wie openClose1, bloss das dieser die Anzahl der geschweiften Klammernpaare berechnet. Das Ergebnis der rekursiven Aufrufe wird in den Variablen m und n gespeichert (Achtung: single Assignment). Zum Abbruch der Rekursion wird die Alternative <|> verwendet. Wird keine öffnende Klammer ''{'' gefunden, so wird return 0 ausgeführt.

> noOfBrace = do{ char '{'
>               ; m <- noOfBrace 
>               ; char '}'
>               ; n <- noOfBrace 
>               ; return (1+m+n);
>               }
>             <|> return 0

? parseTest noOfBrace "{}{}" 
2

? parseTest noOfBrace "{{}}{}" 
3

Die Auswahl

Wie in der Einleitung von Kapitel   erwähnt, handelt es sich bei Parsec um einen LL[1]- Parser. Was aber bedeuted LL[1]? Bei der Topdown-Analyse wird ausgehend von der Wurzel eine Reihe von Ableitungsschritten gesucht und ausgeführt. Ohne die Verwendung von Backtracking muss jede Ableitungsfolge in einer Grammatik eindeutig ausgewählt werden können.

Im folgenden soll die Problematik des Backtracking behandelt werden. Es ist zunächst der folgende Ausschnitt einer Grammatik bekannt. Terminalsymbole sind hierbei großgeschrieben. Klein geschrieben sind die nichtterminal Symbole.

cond ::= IF boolexpr THEN stmt FI
       | IF boolexpr THEN stmt ELSE stmt FI

Zusätzlich ist die folgende Symbolfolge (Anweisung) zu verarbeiten:

 IF (a>b) THEN RETURN a ELSE RETURN b FI

Es wird im folgenden betrachtet, wie die gegebene Anweisung nach dem Topdown- Verfahren verarbeitet werden würde. Ein Symbolzeiger zeigt auf das nächst zu bearbeitende Symbol IF. Ein Parserzeiger ``befindet'' sich gerade vor der Produktionsregel cond. Bei der Verarbeitung der Produktionsregeln wird zunächst fälschlicherweise die erste Alternative ``IF boolexpr THEN stmt FI'' ausgewählt. Hierbei werden die Terminalsymbole verglichen und schrittweise Syntaxbäume für die nichtterminal Symbole boolexpr und stmt aufgebaut. Allerdings schlägt ein abschließender Vergleichstest mit FI aus der Grammatik und dem ELSE aus der Symbolfolge fehl. Es muss nun der erzeugte Teilbaum verworfen werden und der Zeiger auf die Symbolfolge wieder an den Anfang gesetzt werden. Der Parserzeiger wird auf die zweite Alternative von cond gesetzt werden. Jetzt kann die zweite und richtige Ableitungsfolge verarbeitet werden. Es werden entsprechend die Terminalsymbole verglichen und für boolexpr und stmt Teilbäume erstellt.

Bei dieser Vorgehensweise und der gegebenen Grammatik ist das Problem, dass unter Betrachtung des ersten Symbols IF keine Aussage getroffen werden kann, welche der beiden Ableitungsregeln angewendet werden soll.

Die gleiche Problematik soll in Parsec mit einer überschaubaren Grammatik behandelt werden. Eine condition besteht aus drei Symbolen der öffnenden Klammer, dem a oder b und einer schließenden Klammer. Bei einer gegebenen Symbolfolge von (b) kann keine Aussage getroffen werden, ob die erste oder zweite Regel ausgewertet werden soll.

cond ::= (a) | (b)

Eine mögliche Implementierung mit Parsec könnte wie folgt aussehen:

> or0 = string "(a)" 
>      <|> 
>      string "(b)"

string ''(a)'' ist hierbei ein eigenständiger Parser der eine Symbolfolge ``(a)'' erwartet. Die Alternative <|> versucht nur den zweiten Parser string''(b)'', wenn der erste Parser keine Symbole verarbeitet hat.

? parseTest or0 "(a)"
"(a)"

? parseTest or0 "(b)"
parse error at (line 1, column 1):
unexpected "b"
expecting "(a)"

Das erste Beispiel wird wie erwartet ausgeführt. Das zweite Beispiel bricht mit einer Fehlermeldung ab. Der Parser string ''(a)'' überprüft und vergleicht Symbol für Symbol und erwartet anstelle des b ein a. Der zweite alternative Parser string ''(b)'' wird nicht überprüft, weil der erste schon Symbole verarbeitet hat. Die zweite Alternative wird somit nie ausgeführt. Eine verbesserte Version von or0 sei wie folgt abgebildet:

> or1 = do { char '('
>        ; char 'a' <|> char 'b'
>        ; char ')'
>        ; return "ok"  
>        }

? parseTest or1 "(a)"
"ok"

? parseTest or1 "(b)"
"ok"

Funktion- und Arbeitsweise von or1 ist wie erwartet. Der erste Parser überprüft das erste Symbol, die öffnende Klammer. Der zweite Parser ist entweder ein a oder b gefolgt von der schließenden Klammer. Für dieses indirekte ``vorrausschauen'' (a) oder (b) gibt es in Parsec einen extra Parser try. try hat die gleiche Funktion wie die oben verwendete Technik im Parser or1. Zum verdeutlichen ist das gleiche Beispiel unter Verwendung von try abgebildet.

> or2 = try( string "(a)" )
>      <|>
>      try( string "(b)" )

Es sei an dieser Stelle darauf hingewiesen, dass in einem Parser unter der Verwendung durch try das Backtracking implementiert werden kann. Es muss aber deutlich sein, dass dieses Zeit und Preformance kostet.

Ein Taschenrechner mit Parsec

Der Vollständigkeit halber wird auch in diesem Kapitel ein kleiner Taschenrechner mit Parsec dargestellt. Es wird allerdings auf die Entwicklung und Funktionsbeschreibung verzichtet.

module MyPCalc1 where

import Parsec
import ParsecExpr

expr :: Parser Integer
expr  = buildExpressionParser table factor
        <?> "expression"

table :: OperatorTable Char () Integer
table  = [
          [binary "*" (*) AssocLeft, binary "/" div AssocLeft],
          [binary "+" (+) AssocLeft, binary "-" (-) AssocLeft]
         ]
    where binary s f assoc
              = Infix( do{ string s; return f} ) assoc

factor = do { char '('
            ; x <- expr
            ; char ')'
            ; return x
            }
         <|> number
         <?> "simple expression" 

number :: Parser Integer
number  = do {
              ds <- many1 digit
             ; return (read ds)
             }
          <?> "number"

Beispielaufrufe:

? parseTest expr "2+5*2"   -- '*' hat hoehere Prioritaet
12

? parseTest expr "(6+2)*3"  
12

? parseTest expr "48/2/2"   -- '/' ist links Assoziativ
12