Vorlesung: Praxis der Funktionalen Programmierung | Index

Bessere Parser

Annotierter Eingabestrom

Wir hatten den Parsertyp

String -> [ (a, String) ]

benutzt. Daß wir Zeichen gelesen hatten, war nicht wesentlich; es hätte irgendein Listentyp sein können. Also verallgemeinern wir zu

[s] -> [ (a, [s]) ]

Wir nutzen das wie folgt: wir wollen an jedes Eingabezeichen noch weiter Informationen anheften: seine Position im Quelltext (Zeile und Spalte). Wir definieren einen passenden Typ

module Position where

data Position = Position
     { zeile :: Int
     , spalte :: Int
     , inhalt :: String -- der gesamten Zeile
     }
     | EOF

instance Eq Position where
    EOF == EOF = True
    p @ Position {} == q @ Position {}  =  
	       (zeile p, spalte p) == (zeile q, spalte q)
    p == q  =  False

instance Ord Position where
    EOF `compare` EOF = EQ
    EOF `compare` q   = GT
    p `compare` EOF   = LT
    p `compare` q  =  (zeile p, spalte p) `compare` (zeile q, spalte q)


instance Show Position where
    showsPrec _ EOF = showString "Ende des Eingabestroms"
    showsPrec _ p @ Position { zeile = z, spalte = s, inhalt = i} = 
        let (vor, nach) = splitAt (s-1) i
	in  showString $
	    unlines [ "Zeile " ++ show z ++ ", Spalte " ++ show s
		    , vor 
		    , take (s-1) (repeat '^') ++  nach
		    ]

annotate :: String -> [ (Char, Position) ]
annotate input = concat
	       $ map annotate_line
	       $ zip [1..] 
	       $ map ( \ l -> l ++ "\n" ) 
	       $ lines input

annotate_line :: (Int, String) -> [ (Char, Position) ]
annotate_line (z, i) = do
    (s, c) <- zip [1..] i
    return $ ( c, Position { zeile = z, spalte = s, inhalt = i } )

und denken dann an eine Benutzung

[(Char, Pos)] -> [ (a, [(Char, Pos)]) ]

Beliebige Ausgabe-Monade

Wir beherrschen den Nichtdeterminismus, indem wir mit Listen von Ergebnissen rechnen.

[s] -> [ (a, [s]) ]

Statt Listen könnten wir auch eine andere Instanz von MonadPlus nehmen. Das führt zum verallgemeinerter Parser-Typ

module General_Parser_Type 

( GP (..), run

, MonadPlus (plus)
)

where

import MonadPlus

data GP m s a = GP ( [s] -> m (a, [s]) )

instance Monad m => Functor (GP m s) where
    fmap f (GP p) = GP $ \ input ->
	 do  (x, rest) <- p input 
	     return (f x, rest)

instance Monad m => Monad (GP m s) where
    return x = GP $ \ input -> return (x, input) 
    GP p >>= f = GP $ \ input -> do
	   (x, rest) <- p input
	   let GP q = f x
	   (y, rest') <- q rest
	   return (y, rest') 

instance MonadPlus m => MonadPlus (GP m s) where
    GP p `plus` GP q = GP $ \ input ->
        p input `plus` q input


run :: GP m s a -> [s] -> m (a, [s])
run (GP p) input = p input

Dabei denken wir vorwiegend an Maybe. Das entspricht einer Liste mit null oder einem Element, beschränkt also die Suchbäume auf die Breite 1, und beschleunigt damit die Parser.

Es ist jedoch Vorsicht geboten:

Just x `plus` Just y = Just x

d. h. wir vergessen das zweite Resultat. Das `plus` auf Maybe ist also nicht symmetrisch; wir müssen uns gut überlegen, in welcher Reihefolge wir die Argumente hinschreiben. Typischer Fall:

many1 :: Parser a -> Parser [a]
many1 p = do x  <- p
	     xs <- many p
	     return $ x : xs

many ::  Parser a -> Parser [a]
many p =      many1 p
       `plus` return []

Das ist in unserem Sinne richtigrum, denn das many1 p wird bevorzugt, bis es nicht mehr geht, und erst dann kommt return [] dran.

Fehlermeldungen

Bei Maybe stört uns, daß Nothing sehr wenig darüber aussagt, warum das Parsen fehlschlug. Wir möchten das Nothing mit der Fehlerposition annotieren.

module Fehler 

( Fehler, falsch, export
)

where

import MonadZero
import MonadPlus
import Position

data Fehler a = Falsch  Position
	      | Richtig a
     deriving Show

falsch :: Position -> Fehler a
falsch p = Falsch p

instance Functor Fehler where
    fmap f (Falsch  p) = Falsch p
    fmap f (Richtig x) = Richtig (f x)

instance Monad Fehler where
    return x = Richtig x
    Richtig x >>= f  =  f x
    Falsch  p >>= f  =  Falsch p

instance MonadPlus Fehler where
    Richtig x `plus` _         = Richtig x     
    Falsch  p `plus` Richtig y = Richtig y
    Falsch  p `plus` Falsch  q = Falsch (max p q)

export :: Fehler a -> Either String a
export (Falsch  p) = Left (show p)
export (Richtig x) = Right x

Beachte die Instanz von MonadPlus: von zwei fehlgeschlagenen Parses nehmen wir den längeren, d. h. wir informieren den User über den längsten korrekten Präfix der Eingabe. Damit wird unser Parser-Typ zu

module Position_Parser_Basic

( Parser, parse
, item, eof, pos
, guard, plus
)

where


import General_Parser_Type

import Fehler
import Position

import MonadZero 
import MonadPlus (plus)

type Parser = GP Fehler (Char, Position)

instance MonadZero Parser where
  -- das geht nur mit dem switch  hugs -98
  -- weil Parser ein Typ-Synonym ist
  zero = GP $ \ input -> case input of
     ((c, p) : cps) -> falsch p
     []		    -> falsch EOF


item :: Parser Char
item = GP $ \ input -> case input of
     ((c, p) : cps) -> return (c, cps) 
     []		   -> falsch EOF

eof :: Parser ()
eof = GP $ \ input -> case input of
    []		   -> return ((), []) 
    ((c, p) : cps)  -> falsch p

pos :: Parser Position
pos = GP $ \ input -> case input of
    ((c, p) : cps) -> return (p, cps)
    []		   -> return (EOF, [])


parse :: Parser a -> String -> Either String a
parse p input = export $ do
    (x, rest) <- run p $ annotate input
    return x

Dieses Modul hat das gleiche Inteface wie das ursprüngliche Parser_Basic.hs. Damit können wir die Parser-Kombinatoren ohne weiteres nachnutzen (Quelltext) und auch die Anwendungen (Quelltext) merken davon nichts - aber die Fehlermeldungen sind nun viel informativer.

http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de