Transcript
Prof. Dr. Manfred Schmidt-Schauß K¨ unstliche Intelligenz/Softwaretechnologie
Fachbereich Informatik und Mathematik/ Institut f¨ ur Informatik Goethe-Universit¨ at Frankfurt am Main
Grundlagen der Programmierung 2 Sommersemester 2016
Aufgabenblatt Nr. 6 Abgabe: Mittwoch 25. Mai 2016 vor! der Vorlesung
Aufgabe 1 (100 Punkte) Die Syntax einer erweiterten Form der Aussagenlogik sei durch die folgende kontextfreie Grammatik definiert: F ::= /\{FS} | \/{FS} | A FS ::= F | F, FS A ::= Var | (A /\ A) | (A \/ A) | (−A) | (A => A) | (A <=> A) | 0 | 1 Dabei sind die Symbole {, }, (, ), /, \, −, =, <, >, 0, 1 und , Terminalsymbole und Var stellt eine beliebige Zeichenkette bestehend aus Buchstaben dar. Außerdem sei L die Sprache, die von dieser Grammatik erzeugt wird. a) Geben Sie eine Linksherleitung f¨ ur den Ausdruck (((a => b) /\ (c <=> b)) \/ (-a)) an. (15 Punkte) b) Geben Sie eine Rechtsherleitung f¨ ur das Wort /\{((-a) \/ b),(a => b)} an.
(15 Punkte)
c) Ein Lexer ist eine Funktion, die einen Ausdruck der Sprache L als String erh¨alt und diesen in eine Liste von Token zerlegt, wobei Leerzeichen und Zeilenumbr¨ uche entfernt werden. Der Datentyp f¨ ur Token sei in Haskell wie folgt definiert: data Token = TokenVar String | TokenAnd | TokenOr | TokenNeg | TokenImp | TokenBiimp | TokenSymbol Char | TokenVal Bool deriving(Eq,Show)
---------
Variable /\ \/ => <=> ’(’, ’)’, ’{’, ’}’, ’,’ 0, 1
Implementieren Sie in Haskell eine Funktion lexer :: String -> [Token], die einen Ausdruck als String erwartet und diesen einer lexikalischen Analyse unterzieht, dabei Leerzeichen und Zeilenumbr¨ uche entfernt und eine Liste von Token als Ergebnis liefert. Sollten im String Zeichen enthalten sein, die nicht der Sprache entsprechen, so soll ein Fehler erzeugt werden. Zur Erzeugung von Fehlermeldungen k¨ onnen Sie die vordefinierte Funktion error verwenden. Hier ein Beispielaufruf der Funktion lexer: *> lexer "/\\{((-a) /\\ b)}" [TokenAnd,TokenSymbol ’{’,TokenSymbol ’(’,TokenSymbol ’(’,TokenNeg,TokenVar "a", TokenSymbol ’)’,TokenAnd,TokenVar "b",TokenSymbol ’)’,TokenSymbol ’}’] 1
Beachten Sie, dass in Haskell-Strings der Backslash \ doppelt eingegeben werden muss, um als solcher erkannt zu werden. (25 Punkte) d) Ausdr¨ ucke der Sprache L lassen sich in Haskell durch den folgenden Datentyp darstellen: data Formula = FAnd | FOr | Var | And | Or | Neg | Imp | Biimp | Val deriving(Eq,Show)
[Formula] [Formula] String Formula Formula Formula Formula Formula Formula Formula Formula Formula Bool
----------
/\{s1,...,sn} \/{s1,...,sn} Variable (s /\ t) (s \/ t) (-s) (s => t) (s <=> t) 0, 1
Implementieren Sie mit den in der Vorlesung vorgestellten funktionalen Parserkombinatoren1 einen Parser parseF :: Parser Token Formula f¨ ur Ausdr¨ ucke der Sprache L, der als Eingabe eine Liste von Token erwartet und u ¨berpr¨ uft, ob die Token einen syntaktisch korrekten Ausdruck der Sprache L darstellen. Liegt das durch die Token dargestellte Wort in der Sprache, soll der Parser als Ausgabe den entsprechenden Syntaxbaum in der Datenstruktur Formula erzeugen. Beispielaufruf: *> parseF (lexer "/\\{((-a) /\\ b)}") [([],FAnd [And (Neg (Var "a")) (Var "b")])] Der Typ Parser Token Formula des Parsers parseF ist ein Typsynonym f¨ ur [Token] -> [([Token], Formula)]. Ein Parser ist also eine Funktion, die ein Liste von Token verarbeitet und eine Liste von Paaren zur¨ uck gibt, wobei das erste Element des Paars die Liste der Token ist, die noch nicht verarbeitet wurden. Das zweite Element repr¨asentiert den aufgebauten Syntaxbaum. In der Datei CombParser.hs sind hilfreiche Funktionen definiert.
(40 Punkte)
e) Implementieren Sie eine Funktion parseFormula :: String -> Formula, die einen String der Sprache L nimmt und den dazugeh¨ origen Syntaxbaum liefert. Nutzen Sie hierzu die L¨osungen aus den vorigen Teilaufgaben. (5 Punkte)
1
Die Datei CombParser.hs mit der Implementierung der Parserkombinatoren ist auf der PRG-2 Webseite verf¨ ugbar.
2
