Funktionale Programmierung: Ableitung von regulären Ausdrücken

Ableitungen von Regulären Ausdrücken	als Trainingslager für die Verarbeitung und Transformation von Ausdrücken

Reguläre Ausdücken	können direkt operationalisiert werden. Traditionell werden R.E.s in deterministische endliche Automaten transformiert, um ein operationales Modell für die Worterkennung mit regulären Sprachen zu realisiern.
	Dieses geht aber auch direkt. Das Verfahren ist in den Unterlagen zur Vorlesung Compilerbau beschrieben.
	Die Idee dabei ist die, dass aus einem R.E. und dem ersten Zeichen einer Eingabe ein R.E. für den Rest der Eingabe berechnet wird.
	In den Compilerbau-Unterlagen ist auch schon eine Datenstruktur skizziert, mit der man reguläre Ausdrücke als Repräsentanten für reguläre Mengen aufbauen kann.
	Für die Operationalisierung benötigt man folgende Funktionen:
	nullable :: RE a -> Bool delta :: RE a -> a -> RE a delta' :: RE a -> [a] -> RE a match :: RE a -> [a] -> Bool
1. Aufgabe	Vervollständigen Sie die Codefragmente aus den Unterlagen, entwickeln Sie auf möglichst systematische Weise Testfälle (mit Char als Eingabealphabet) und entwickeln Sie eine trace-Funktion, mit der man beobachten kann, wie die Ableitungen schrittweise aufgebaut werden und sich beim Parsen verändern. Hierfür ist die Funktion deltaTest vorgesehen.
	deltaTest :: RE a -> [a] -> [RE a]
	Für die Untersuchung des Wachsens von Ausdrücken sind insbesondere die Wiederholungen in Kombination mit Sequenz und Auswahl interessant, Beispiele `a, (a\|b), (a\|b)`
Erste Schritte	Die Typdefinitionen und erste einfache kleine Funktionen für die Lösung.
	module DeltaRE where import Prelude hiding (seq) data RE a = Zero -- {} \| Unit -- {ε} \| Dot -- whole Alphabet \| Sym a -- {a} \| Star (RE a) -- r* \| Plus (RE a) -- r+ \| Seq (RE a) (RE a) -- r1 . r2 \| Union (RE a) (RE a) -- r1 \| r2 \| Isect (RE a) (RE a) -- r1 & r2 \| Diff (RE a) (RE a) -- r1 - r2 deriving (Eq, Ord, Read, Show) type Regex = RE Char -- ------------------------------------------------------------ nullable :: RE a -> Bool nullable Zero = False nullable Unit = True nullable Dot = False nullable (Sym _x) = False nullable (Star _r) = True nullable (Plus r) = nullable r nullable (Seq r1 r2) = nullable r1 && nullable r2 nullable (Union r1 r2) = nullable r1 \|\| nullable r2 nullable (Isect r1 r2) = nullable r1 && nullable r2 nullable (Diff r1 r2) = nullable r1 && not (nullable r2) -- ------------------------------------------------------------ delta :: Eq a => RE a -> a -> RE a delta Zero _a = Zero delta Unit _a = Zero delta Dot _a = Unit delta (Sym x) a \| a == x = Unit \| otherwise = Zero delta (Star r) a = Seq (delta r a) (Star r) delta (Plus r) a = delta (Seq r (Star r)) a delta (Seq r1 r2) a \| nullable r1 = Union dr1 dr2 \| otherwise = dr1 where dr1 = Seq (delta r1 a) r2 dr2 = delta r2 a delta (Union r1 r2) a = Union (delta r1 a) (delta r2 a) delta (Isect r1 r2) a = Isect (delta r1 a) (delta r2 a) delta (Diff r1 r2) a = Diff (delta r1 a) (delta r2 a) -- ------------------------------------------------------------ delta' :: Eq a => RE a -> [a]-> RE a delta' re [] = re delta' re (a:w) = delta' (delta re a) w match :: Eq a => RE a -> [a]-> Bool match re w = nullable (delta' re w) -- ------------------------------------------------------------ -- -- readable output showR :: Regex -> String showR = showRegex 6 prio :: RE a -> Int prio Zero = 0 prio Unit = 0 prio Dot = 0 prio (Sym _) = 0 prio (Star _) = 1 prio (Plus _) = 1 prio (Seq _ _) = 2 prio (Isect _ _)= 3 prio (Diff _ _) = 4 prio (Union _ _)= 5 showRegex :: Int -> Regex -> String showRegex p r = par $ (showRegex' r) where pr = prio r par s \| pr > p = "(" ++ s ++ ")" \| otherwise = s showRegex' Zero = "{}" showRegex' Unit = "()" showRegex' Dot = "." showRegex' (Sym a) \| a `elem` "\\(){}.+\|&-" = '\\' : [a] \| otherwise = [a] showRegex' (Star r1) = showRegex pr r1 ++ "" showRegex' (Plus r1) = showRegex pr r1 ++ "+" showRegex' (Seq r1 r2) = showRegex pr r1 ++ showRegex pr r2 showRegex' (Union r1 r2) = showRegex pr r1 ++ "\|" ++ showRegex pr r2 showRegex' (Isect r1 r2) = showRegex pr r1 ++ "&" ++ showRegex pr r2 showRegex' (Diff r1 r2) = showRegex pr r1 ++ "-" ++ showRegex pr r2 -- ------------------------------------------------------------
Download	DeltaRE.hs
2. Aufgabe	Erweitern Sie die Datenstruktur und die Funktionen so, dass folgende Operatoren in R.E.s möglich sind:
`.`	für ein beliebiges Zeichen aus dem Alphabet
`r+`	für eine mindestens einmalige Wiederholung
`r & r`	für einen Mengendurchschnitt
`r - r`	für einen Mengensubtraktion
Tests	Sinnvolle Beispiele für diese Erweiterung sind reguläre Ausdrücke für Kommentare aus C (/**/ aber nicht //*/) oder alle Bezeichner einer Sprache außer Schlüsselwörter.
Verfeinerung	der Datenstruktur: Dieses kann für die Performanz wichtig sein. Eine Ineffizienz besteht darin, nur mit einzelnen Symbolen als Blätter zu arbeiten. Symbolmengen werden dann zu sehr großen Ausdrücken. Hier kann es günstiger sein, mit Symbol-Mengen zu arbeiten, die entweder als explizite Listen oder als Funktionen repräsentiert werden.

3. Aufgabe	Ersetzen Sie die expliziten Konstruktoraufrufe durch Aufrufe von so genannten intelligenten Konstruktorfunktionen. Diese sollen dafür sorgen, dass die durch das Ableiten entstehenen Ausdrücke in ihrer Größe nicht wachsen, d.h. in dieses Funktionen werden die Gesetzte der Booleschen Algebra zur partiellen Auswertung und Vereinfachung ausgenutzt. Ziel dabei ist, dass die Größe des abgeleiteten Ausdrucks nicht von der Länge der Eingabe abhängt.
	Wählen Sie dafür eine hinreichende Menge von Transformationsregeln.
4. Aufgabe	Entwickeln Sie einen Parser für die Syntaxanalyse von regulären Ausdrücken und den Aufbau des Ausdrucksbaums.
Beispiel-Parser	Noch mit fehlenden Konstruktor-Funktionen.
	-- ------------------------------------------------------------ module RegexParser ( parseRegex ) where import Data.Maybe import Text.ParserCombinators.Parsec import DeltaRE(Regex) import SmartConstr -- ------------------------------------------------------------ parseRegex :: String -> Either String Regex parseRegex = either (Left . show) Right . parse ( do r <- regExp eof return r ) "" -- ------------------------------------------------------------ regExp :: Parser Regex regExp = do r1 <- branch rs <- many branch1 return (foldr1 mkUnion $ r1:rs) where branch1 = do _ <- char '\|' branch branch :: Parser Regex branch = do rs <- many piece return $ foldr mkSeq mkUnit rs piece :: Parser Regex piece = do r <- atom quantifier r quantifier :: Regex -> Parser Regex quantifier r = ( do _ <- char '?' return $ mkOpt r ) <\|> ( do _ <- char '' return $ mkStar r ) <\|> ( do _ <- char '+' return $ mkRep 1 r ) <\|> ( do _ <- char '{' res <- quantity r _ <- char '}' return res ) <\|> ( return r ) quantity :: Regex -> Parser Regex quantity r = do lb <- many1 digit quantityRest r (read lb) quantityRest :: Regex -> Int -> Parser Regex quantityRest r lb = ( do _ <- char ',' ub <- many digit return ( if null ub then mkRep lb r else mkRng lb (read ub) r ) ) <\|> ( return $ mkRng lb lb r) atom :: Parser Regex atom = char1 <\|> charClass <\|> between (char '(') (char ')') regExp char1 :: Parser Regex char1 = do c <- satisfy $ (`notElem` ".\\?+{}()\|[]") return $ mkSym c charClass :: Parser Regex charClass = charClassEsc <\|> charClassExpr <\|> wildCardEsc charClassEsc :: Parser Regex charClassEsc = do _ <- char '\\' singleCharEsc singleCharEsc :: Parser Regex singleCharEsc = do c <- singleCharEsc' return $ mkSym c singleCharEsc' :: Parser Char singleCharEsc' = do c <- satisfy (`elem` "nrt\\\|.?*+(){}-[]^") return $ maybe c id . lookup c . zip "ntr" $ "\n\r\t" charClassExpr :: Parser Regex charClassExpr = between (char '[') (char ']') charGroup charGroup :: Parser Regex charGroup = do r <- ( negCharGroup -- a ^ at beginning denotes negation, not start of posCharGroup <\|> posCharGroup ) s <- option mkZero -- charClassSub ( do _ <- char '-' charClassExpr ) return $ mkDiff r s posCharGroup :: Parser Regex posCharGroup = do rs <- many1 (charRange <\|> charClassEsc) return $ foldr1 mkUnion rs charRange :: Parser Regex charRange = try seRange <\|> xmlCharIncDash seRange :: Parser Regex seRange = do c1 <- charOrEsc' _ <- char '-' c2 <- charOrEsc' return $ mkSymRng c1 c2 charOrEsc' :: Parser Char charOrEsc' = satisfy (`notElem` "\\-[]") <\|> singleCharEsc' xmlCharIncDash :: Parser Regex xmlCharIncDash = do c <- satisfy (`notElem` "\\[]") return $ mkSym c negCharGroup :: Parser Regex negCharGroup = do _ <- char '^' r <- posCharGroup return $ mkCompl r wildCardEsc :: Parser Regex wildCardEsc = do _ <- char '.' return $ mkDot -- mkSym (`notElem` "\n\r") -- ------------------------------------------------------------
Download	RegexParser.hs
5. Aufgabe	Schreiben Sie eine Anwendung, die ähnliche Funktionalität besitzt wie das `grep`-Kommando.
6. Aufgabe	Schreiben Sie eine Anwendung, die ähnliche Funktionalität besitzt wie das `scan`-Kommando aus Ruby. Mit diesem kann man über einen regulären Ausdruck einen Text in Wörter zerlegen. Alle diese Wörter passen auf den R.E., alle anderen Zeichen werden als Worttrenner interpretiert und gelöscht.

Ableitung von regulären Ausdrücken

Aufgabe