Motivation

Als ich gerade anfing, Haskell zu lernen, war ich sehr verärgert über die weit verbreitete Verwendung komplexer Abstraktionen anstelle spezifischer Lösungen. Es schien mir viel besser, immer dem KISS-Prinzip zu folgen und Fahrräder mit elementaren Sprachkonstrukten zu schreiben, als all diese Typklassen zu verstehen, um irgendwo eine vermeintlich bequeme Konstruktion zu schreiben.

Ich hatte kein gutes Beispiel dafür, wo sich die Anstrengungen zur Entwicklung des "Materials" auszahlen würden. Eines der erfolgreichsten Beispiele für mich waren Parser. Jetzt spreche ich oft über sie, wenn sie mich fragen, welche allgemeinen Aufgaben Sie Haskell wunderbar verwenden können.

Ich möchte Anfängern anbieten, auch diesen Weg zu gehen und eine kleine Basis von Funktionen von Grund auf neu zu erstellen, um Parser bequem zu implementieren, und dann einen eigenen Parser zu schreiben, dessen Code die für das Parsen verwendete Grammatik fast buchstäblich wiederholt.

Ich hoffe, dies hilft jemandem, die Angst vor Abstraktionen zu überwinden und ihm den richtigen Umgang mit ihnen beizubringen (ja, ich denke immer noch, dass es manchmal effizienter ist, ein Fahrrad zu schreiben).

Ich habe keinen Zweck und keine Lust, einen Haskell-Kurs aus einem Artikel von Grund auf neu zu erstellen, daher gehe ich davon aus, dass der Leser mit der Syntax und den unabhängig entwickelten einfachen Programmen vertraut ist. Für alle Fälle werde ich kurz auf Typklassen eingehen, bevor ich mit der Beschreibung der Implementierung fortfahre.

Für diejenigen, die noch nie an Haskell geschrieben haben, aber verstehen möchten, was hier passiert, empfehle ich, dass Sie sich zuerst die entsprechende Seite zu Learn X in Y Minuten ansehen. Als ausgezeichnetes russischsprachiges Buch für Anfänger empfehle ich "Über Haskell als Mensch" von Denis Shevchenko.

Ich werde versuchen, die einfachsten Sprachkonstrukte zu verwenden, die Anfänger verstehen können. Am Ende des Artikels wird ein Link zum Quell-Repository angegeben, in dem in einigen Teilen des Codes ein bequemerer und kürzerer Eintrag verwendet wird, der auf den ersten Blick weniger klar sein kann.

Und ja, meine Herren Haskellisten, viele Dinge werden sehr einfach und ungeschickt erklärt, für spezielle Fälle nicht sehr abstrakt, ohne Begriffe aus der Kategorietheorie und andere beängstigende Wörter zu verwenden. Ich bin froh, dass du sie kennst und sie sie natürlich leicht beherrschen. Ich kenne sie auch, aber ich halte es nicht für notwendig, eine solche Menge an Informationen in diesem Zusammenhang unvorbereiteten Lesern zur Verfügung zu stellen.

Typklassen

Klassen vom Typ Haskell haben nichts mit Klassen in C ++ und anderen objektorientierten Sprachen zu tun. Wenn wir eine Analogie zu OOP ziehen, sind Typklassen eher eine Überladung von Methoden und Funktionen.

Klassen bestimmen, welche Aktionen mit Objekten der Typen ausgeführt werden können, aus denen die Klasse besteht. Zum Beispiel können alle Zahlen auf Gleichheit verglichen werden, aber alles kann bis auf komplexe geordnet werden, und im Allgemeinen können Funktionen überhaupt nicht verglichen werden. Die Klasse der Typen, die verglichen werden können, heißt Eq , Geordnet - Ord (Typen müssen nicht numerisch sein). Was durch Übersetzen in eine Zeichenfolge gedruckt werden kann, gehört zur Show Klasse. Es gibt die "entgegengesetzte" Read Klasse, die bestimmt, wie Zeichenfolgen in Objekte des gewünschten Typs konvertiert werden.

Für eine Reihe von Standardtypklassen (wie Eq , Show , Read ...) können Sie den Compiler auffordern, die gewünschte Funktionalität auf Standardweise zu implementieren, indem Sie das Schlüsselwort deriving nachdem Sie den Typ bestimmt haben:

 data Point = Point { xCoord :: Float , yCoord :: Float } deriving (Eq, Show)

Sie können Ihre eigenen Typklassen definieren:

 class PrettyPrint a where pPrint :: a -> String

Hier ist PrettyPrint der Name der Klasse, a ist eine Typvariable. Dem Schlüsselwort where folgt eine Liste der sogenannten Klassenmethoden, d.h. Funktionen, die auf Objekte vom Typ dieser Klasse angewendet werden können.

Um die Zugehörigkeit eines Datentyps zu einer Klasse anzuzeigen, wird die folgende Konstruktion verwendet:

 instance PrettyPrint Point where pPrint (Point xy) = "(" ++ show x ++ ", " ++ show y ++ ")"

In der Sprache können Sie Einschränkungen für die Typklassen festlegen, auf die sich Funktionsargumente beziehen müssen:

 showVsPretty :: (Show a, PrettyPrint a) => a -> (String, String) showVsPretty x = (show x, pPrint x)

Bei jedem Funktionsaufruf prüft der Compiler, ob diese Typanforderungen erfüllt sind, und zeigt im Fehlerfall einen Fehler an (dies geschieht natürlich in der Kompilierungsphase).

 >>> showVsPretty (Point 2 3) ("Point {xCoord = 2.0, yCoord = 3.0}","(2.0, 3.0)") >>> showVsPretty "str" error: No instance for (PrettyPrint [Char]) arising from a use of 'showVsPretty'

Implementierung

Der Parser erhält eine Eingabezeichenfolge, die er nach vordefinierten Regeln analysieren und den Wert des benötigten Typs abrufen muss (z. B. eine Ganzzahl). In diesem Fall endet die Eingabezeile möglicherweise nicht und der Rest dient als Eingabe für die weitere Analyse. Außerdem ist unser Parser im Allgemeinen nicht deterministisch, d. H. gibt mehrere mögliche Analyseergebnisse als Liste zurück.

Ein Tupel aus zwei Elementen (String, a) eignet sich zur Beschreibung eines Ergebnisses der Parser-Operation, wobei a eine Typvariable ist, die einen beliebigen Benutzertyp bezeichnen kann.

Da der Parser die Zeichenfolge nach bestimmten Regeln analysiert, beschreiben wir sie als eine Funktion, die eine Zeichenfolge als Eingabe verwendet und eine Ergebnisliste zurückgibt:

 newtype Parser a = Parser { unParser :: String -> [(String, a)] }

Wir werden das Parsen als erfolgreich betrachten, wenn die Ergebnisliste aus einem Element besteht und die Eingabezeichenfolge vollständig verarbeitet wurde. Wir implementieren eine Hilfsfunktion, die versucht, die gesamte Zeichenfolge eindeutig zu analysieren:

 parseString :: String -> Parser a -> Maybe a parseString s (Parser p) = case (ps) of [("", val)] -> Just val _ -> Nothing

Einfache Parser

Wir implementieren mehrere einfache Parser, die sich dann als nützlich erweisen, um komplexere Kombinationen zu erstellen.

Wir beginnen mit dem Parsen eines einzelnen Zeichens, das ein Prädikat erfüllen muss. Wenn die Eingabezeichenfolge leer ist, ist das Ergebnis der Arbeit eine leere Liste. Andernfalls überprüfen wir den Wert des Prädikats für das erste Zeichen der Zeichenfolge. Wenn True zurückgegeben wird, ist das Ergebnis der Analyse dieses Zeichen. Geben Sie es mit dem Rest der Zeichenfolge zurück. Andernfalls schlägt auch die Analyse fehl.

 predP :: (Char -> Bool) -> Parser Char predP p = Parser f where f "" = [] f (c : cs) | pc = [(cs, c)] | otherwise = []

Jetzt können wir einen Parser schreiben, der am Anfang der Zeile ein bestimmtes Zeichen enthält. Verwenden Sie dazu das gerade geschriebene predP und übergeben Sie ihm als Argument eine Funktion, die sein Argument mit dem von uns benötigten Zeichen vergleicht:

 charP :: Char -> Parser Char charP char = predP (\c -> c == char)

Der folgende einfachste Fall: Ein Parser, der nur eine bestimmte Zeichenfolge als Ganzes akzeptiert. Nennen stringP es stringP . Die Funktion im Parser vergleicht die Eingabezeile mit der gewünschten und gibt bei gleichen Zeilen eine Liste mit einem Element zurück: einem Paar leerer Zeilen (am Eingang ist nichts mehr übrig) und der ursprünglichen. Andernfalls ist die Analyse fehlgeschlagen und eine leere Ergebnisliste wird zurückgegeben.

 stringP :: String -> Parser String stringP s = Parser f where fs' | s == s' = [("", s)] | otherwise = []

Sehr oft müssen Sie Zeichen mit einer bestimmten Eigenschaft überspringen, während sie an den Zeilenanfang gehen (z. B. Leerzeichen). Darüber hinaus ist das Ergebnis der Analyse für uns nicht wichtig und wird in Zukunft nicht mehr nützlich sein. Wir schreiben eine skip , die die Anfangszeichen der Zeichenfolge skip , während der wahre Wert des Prädikats erhalten bleibt. Als Analyseergebnis verwenden wir ein leeres Tupel.

 skip :: (Char -> Bool) -> Parser () skip p = Parser (\s -> [(dropWhile ps, ())])

Die nächsten beiden Parser sind einander sehr ähnlich. Beide überprüfen das Eingabezeilenpräfix, nur das erste gibt dieses Präfix zurück, wenn es erfolgreich ist, und das zweite gibt ein leeres Tupel zurück, d.h. Mit dieser Option können Sie eine beliebige Zeile am Anfang der Eingabe überspringen. Die Implementierung verwendet die im Modul isPrefixOf definierte Funktion Data.List .

 prefixP :: String -> Parser String prefixP s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, s)] else [] skipString :: String -> Parser () skipString s = Parser f where f input = if s `isPrefixOf` input then [(drop (length s) input, ())] else []

Wenig später werden wir eine einfachere Implementierung der letzteren Funktion in Betracht ziehen und die Codeduplizierung beseitigen.

Parser als Funktor

Wir können eine ganze Klasse von Containertypen unterscheiden, für die Folgendes zutrifft: Wenn Sie wissen, wie Objekte in einem Container konvertiert werden, können Sie die Container selbst konvertieren. Das einfachste Beispiel ist eine Liste als Container und eine map , die in fast allen Hochsprachen verfügbar ist. In der Tat können Sie alle Elemente einer Liste vom Typ [a] durchgehen, die Funktion a -> b auf jede anwenden und eine Liste vom Typ [b] .

Diese Typklasse heißt Functor , die Klasse verfügt über eine fmap Methode:

 class Functor f where fmap :: (a -> b) -> fa -> fb

Angenommen, wir wissen bereits, wie Zeichenfolgen in Objekte eines bestimmten Typs a analysiert werden, und wir wissen außerdem, wie Objekte vom Typ a in Objekte vom Typ b konvertiert werden. Kann man sagen, dass es dann einen Parser für Objekte vom Typ b ?

Wenn es in Form einer Funktion ausgedrückt wird, hat es den folgenden Typ:

 (a -> b) -> Parser a -> Parser b

Dieser Typ stimmt mit dem Typ der fmap Funktion überein. fmap wir also, den Parser zu einem Funktor zu machen. Erstellen wir einen Parser mit Werten vom Typ b von Grund auf neu, der zuerst den ersten Parser aufruft (wir haben bereits einen) und dann die Funktion auf die Ergebnisse seiner Analyse anwendet.

 instance Functor Parser where fmap :: (a -> b) -> Parser a -> Parser b fmap f (Parser p1) = Parser p2 where p2 :: String -> [(String, b)] p2 s = convert (p1 s) convert :: [(String, a)] -> [(String, b)] convert results = map (\(s, val) -> (s, f val)) results

Die Funktion fmap hat ein praktisches Infix-Synonym: fmap fx == f <$> x .

Wenn wir eine Funktion als Argument für fmap , die einfach das erste Argument durch einen neuen Wert ersetzt, erhalten wir eine weitere nützliche Operation, die bereits in zwei Fällen für alle Funktoren implementiert ist (sie unterscheiden sich nur in der Reihenfolge der Argumente):

 (<$) :: Functor f => a -> fb -> fa ($>) :: Functor f => fa -> b -> fb

Erinnern Sie sich an den Parser, der eine bestimmte Zeile überspringt ( skipString )? Jetzt können Sie es wie folgt implementieren:

 skipString :: String -> Parser () skipString s = () <$ prefixP s

Parser-Kombinationen

In Haskell sind alle Funktionen standardmäßig aktiviert und teilweise verwendbar. Dies bedeutet, dass eine Funktion von n Argumenten tatsächlich eine Funktion eines Arguments ist und eine Funktion von n-1 Argumenten zurückgibt:

 cons :: Int -> [Int] -> [Int] cons = (:) cons1 :: [Int] -> [Int] cons1 = cons 1 --  cons

Wir wenden eine Funktion aus drei Argumenten mit fmap auf einen Wert im Parser fmap . Die Typen sind wie folgt:

 f :: c -> a -> b p :: Parser c (fmap fp) :: Parser (a -> b)

Der Funktionsparser hat sich herausgestellt ?! Natürlich ist eine Situation möglich, in der sich die Darstellung der Funktion tatsächlich in der Eingabezeile befindet, aber ich möchte diese Funktion verwenden oder vielmehr die Parser (a -> b) und Parser a kombinieren können, um Parser b :

 applyP :: Parser (a -> b) -> Parser a -> Parser b

Der Typ dieser Funktion ist dem fmap Typ sehr ähnlich, nur die Funktion selbst, die angewendet werden muss, befindet sich ebenfalls im Container. Dies gibt ein intuitives Verständnis dafür, wie die Implementierung der Funktion applyP aussehen sollte: applyP sich die Funktion aus dem Container (als Ergebnis der Anwendung des ersten Parsers), rufen Sie die Werte ab, auf die die Funktion applyP werden soll (Ergebnis der Anwendung des zweiten Parsers), und "packen" Sie die mit dieser Funktion konvertierten Werte zurück in den Container (neuen Parser erstellen). In der Implementierung verwenden wir das Listenverständnis:

 applyP :: Parser (a -> b) -> Parser a -> Parser b applyP (Parser p1) (Parser p2) = Parser f where fs = [ (sx, fx) | (sf, f) <- p1 s, -- p1     (sx, x) <- p2 sf] -- p2   ,

Es gibt eine Applicative Klasse mit einer Methode mit demselben Prototyp. Die zweite Methode der Klasse heißt pure und wird verwendet, um einen Wert, einschließlich eines funktionalen, zu "wickeln" oder zu "heben" (zu heben ). Bei der Implementierung für den Parser fügt die Funktion pure ihr Argument zum Ergebnis des Parsers hinzu, ohne die Eingabezeichenfolge zu ändern.

 class Functor f => Applicative f where pure :: a -> fa (<*>) :: f (a -> b) -> fa -> fb instance Applicative Parser where pure x = Parser (\s -> [(s, x)]) pf <*> px = Parser (\s -> [ (sx, fx) | (sf, f) <- unParser pf $ s, (sx, x) <- unParser px $ sf])

Die Funktion applyP ist das <*> aus der Klasse Applicative . Typen, die zu dieser Klasse gehören, werden als anwendungsbezogene Funktoren bezeichnet.

Für anwendungsbezogene Funktoren sind zwei Hilfsfunktionen implementiert, die für uns nützlich sind:

 (*>) :: fa -> fb -> fb (<*) :: fa -> fb -> fa

Diese Funktionen führen zwei aufeinanderfolgende Aktionen aus und geben nur das Ergebnis einer von ihnen zurück. Für Parser können sie beispielsweise verwendet werden, um führende Leerzeichen zu überspringen, bevor ein Teil eines Strings analysiert wird, der eine semantische Last trägt.

Durch die Kombination von <$> und <*> können Sie sehr praktische Designs erstellen. Betrachten Sie den folgenden Datentyp:

 data MyStructType = MyStruct { field1 :: Type1 , field2 :: Type2 , field3 :: Type3 }

Der Konstruktor der Werte MyStruct ist ebenfalls eine Funktion, in diesem Fall vom Typ Type1 -> Type2 -> Type3 -> MyStructType . Sie können mit dem Konstruktor wie mit jeder anderen Funktion arbeiten. Angenommen, Parser wurden bereits für die Arten von Strukturfeldern geschrieben:

 parser1 :: Parser Type1 parser2 :: Parser Type2 parser3 :: Parser Type3

Mit der Funktion fmap können Sie MyStruct teilweise auf den ersten dieser Parser anwenden:

 parserStruct' :: Parser (Type2 -> Type3 -> MyStructType) parserStruct' = MyStruct <$> parser1

Versuchen wir, die Funktion anzuwenden, die sich jetzt "innerhalb" des Parsers befindet. Dazu müssen Sie bereits <*> :

 parserStruct'' :: Parser (Type3 -> MyStructType) parserStruct'' = parserStruct' <*> parser2 parserStruct :: Parser MyStructType parserStruct = parserStruct'' <*> parser3

Als Ergebnis haben wir einen Parser für die gesamte Struktur erhalten (hier gehen wir natürlich davon aus, dass in der ursprünglichen Zeile die Darstellungen der Felder in einer Reihe stehen). Das gleiche kann in einer Zeile gemacht werden:

 parserStruct :: Parser MyStructType parserStruct = MyStruct <$> parser1 <*> parser2 <*> parser3

Solche Konstruktionen treten häufig in Anwendungsfällen auf.

Angenommen, wir versuchen, einen Parser zu schreiben, der einfache arithmetische Ausdrücke analysiert, in denen Ganzzahlen und Bezeichner als Operanden vorhanden sein können. Erstellen Operand für sie einen separaten Operand :

 data Operand = IntOp Int | IdentOp String

Wenn wir bereits wissen, wie Ganzzahlen und Bezeichner analysiert werden (z. B. wie in C), benötigen wir einen Parser für Operanden, die den einen oder anderen analysieren können. Dieser Parser ist eine Alternative zu den beiden anderen. Daher benötigen wir eine Funktion, mit der Parser kombiniert werden können, damit die Ergebnisse ihrer Arbeit kombiniert werden. Das Ergebnis des Parsers ist eine Liste, und das Kombinieren von Listen ist deren Verkettung. Wir implementieren die altP Funktion, die zwei Parser kombiniert:

 altP :: Parser a -> Parser a -> Parser a altP (Parser p1) (Parser p2) = Parser (\s -> p1 s ++ p2 s)

Dann kann der Operandenparser mit dieser Funktion implementiert werden (hier wird angenommen, dass parserInt und parserIdent bereits irgendwo beschrieben sind:

 parserOperand :: Parser Operand parserOperand = altP parserIntOp parserIdentOp where parserIntOp = IntOp <$> parserInt parserIdentOp = IdentOp <$> parserIdent

Natürlich haben wir für Alternativen bereits eine separate Klasse entwickelt, die Alternative heißt. Es gibt eine andere Methode, empty , die das neutrale Element für die alternative Operation beschreibt. In unserem Fall ist es ein Parser, der niemals etwas analysiert, d. H. Gibt immer eine leere Ergebnisliste zurück. Für den Parser sieht die Implementierung der Methoden der Alternative Klasse folgendermaßen aus:

 class Applicative f => Alternative f where empty :: fa (<|>) :: fa -> fa -> fa instance Alternative Parser where empty = Parser (const []) px <|> py = Parser (\s -> unParser px s ++ unParser py s)

Die Operation <|> ist die altP Funktion nur in Infix-Notation. altP ist bequemer, wenn mehrere Parser hintereinander kombiniert werden.

Für alle Typen in dieser Klasse sind zwei Funktionen implementiert, some und many Typ fa -> f [a] . Jeder von ihnen kann durch den anderen ausgedrückt werden:

 some v = (:) <$> v <*> many v many v = some v <|> pure []

In Bezug auf Parser können Sie mit diesen Funktionen Datensequenzen analysieren, wenn Sie wissen, wie ein einzelnes Datenelement analysiert wird. Wenn Sie some darf some Sequenz nicht leer sein.

Anwendungsbeispiel

Jetzt können wir Ihren eigenen Parser schreiben, zum Beispiel für einfache arithmetische Ausdrücke mit der folgenden Grammatik:

  expr ::= constExpr | binOpExpr | negExpr const ::= int int ::= digit{digit} digit ::= '0' | ... | '9' binOpExpr ::= '(' expr ' ' binOp ' ' expr ')' binOp ::= '+' | '*' negExpr ::= '-' expr

Der Ausdruck besteht aus ganzzahligen Konstanten, dem unären Minus und zwei binären Infix-Operationen: Addition und Multiplikation. Um einen Ausdruck mit einer binären Operation sind Klammern erforderlich. Das Operationssymbol ist durch genau ein Leerzeichen von den Operanden getrennt. Führende und hängende Leerzeichen sind nicht zulässig.

Beispiele für das Schreiben korrekter Ausdrücke:

 "123" "-(10 + 42)" "(1 + ((2 + 3) * (4 + 5)))"

Beispiele für falsche Einträge:

 " 666 " "2 + 3" "(10 * 10)"

Wir deklarieren die notwendigen Datentypen (den Ausdruck selbst und die binäre Operation):

 data Expr = ConstExpr Int | BinaryExpr Expr Operator Expr | NegateExpr Expr data Operator = Add | Mul

Sie können mit dem Parsen beginnen! Der Ausdruck selbst besteht aus drei Alternativen. Also schreiben wir:

 -- expr ::= constExpr | binOpExpr | negExpr exprParser :: Parser Expr exprParser = constParser <|> binParser <|> negParser

Eine Konstante ist eine positive ganze Zahl. In unserem Datentyp wird er im Konstruktor "umbrochen", sodass wir den Parser nicht direkt für eine Ganzzahl verwenden können, sondern fmap verwenden fmap , um den Wert des gewünschten Typs fmap .

 -- const ::= int constParser :: Parser Expr constParser = ConstExpr <$> intParser

Eine ganze Zahl wird gemäß der Grammatik als nicht leere Folge von Zahlen dargestellt. Um eine Ziffer zu analysieren, verwenden wir die Hilfsfunktion predP und das Prädikat isDigit aus dem Data.Char Modul. Um einen Parser zum Parsen einer Ziffernfolge zu erstellen, verwenden wir die Funktion some (nicht many , da mindestens eine Ziffer vorhanden sein muss). Das Ergebnis eines solchen Parsers gibt eine Liste aller möglichen Parsing-Optionen zurück, beginnend mit dem längsten Datensatz. Wenn die Eingabezeichenfolge beispielsweise "123ab" lautet, lautet die Liste der Ergebnisse wie folgt: [("ab", "123"), ("3ab", "12"), ("23ab", "1")] . Wir müssen die längste Folge von Ziffern analysieren und in den Typ Int konvertieren. Die gesamte Implementierung ist wie folgt:

 -- int ::= digit{digit} -- digit ::= '0' | ... | '9' intParser :: Parser Int intParser = Parser $ \s -> let res = unParser (some digitParser) s in case res of [] -> [] ((rest, i) : xs) -> [(rest, read i)] where digitParser = predP isDigit

Die nächste Möglichkeit, einen Ausdruck zu schreiben, besteht darin, eine binäre Operation zu verwenden. Gemäß der Grammatik muss die öffnende Klammer zuerst die öffnende Klammer, den ersten Operanden, das Leerzeichen, das Operationssymbol, ein anderes Leerzeichen, den zweiten Operanden und die schließende Klammer enthalten. Um einzelne Zeichen (Klammern und Leerzeichen) zu analysieren, verwenden wir die Funktion charP . Operanden sind Ausdrücke, und es gibt bereits einen Parser ( exprParser ), um sie zu analysieren. Um das Symbol für die binäre Operation zu analysieren, beschreiben wir den folgenden Hilfsparser. Es bleibt, diesen Satz von Parsern ordentlich zu kombinieren. Am Anfang und am Ende des Ausdrucks sollten Klammern stehen: Sie müssen dies überprüfen, aber das Ergebnis selbst verwerfen. Verwenden Sie dazu *> und <* :

 binParser :: Parser Expr binParser = charP '(' *> ??? <* charP ')'

Zwischen diesen Parsern für Klammern muss ein Ausdruck mit dem BinaryExpr Konstruktor und Parsern für den Ausdruck und die Operation erstellt werden. Vergessen Sie nicht die Leerzeichen um das Operationssymbol. Verwenden Sie dabei die gleiche Methode wie für die Klammern. Dieser Teil ist wie folgt:

 BinaryExpr <$> exprParser --   <*> (charP ' ' *> binOpParser <* charP ' ') -- ,   <*> exprParser --

Wir ersetzen diesen Ausdruck anstelle von Fragezeichen:

 -- binOpExpr ::= '(' expr ' ' binOp ' ' expr ')' binParser :: Parser Expr binParser = charP '(' *> (BinaryExpr <$> exprParser <*> (charP ' ' *> binOpParser <* charP ' ') <*> exprParser ) <* charP ')'

Eine binäre Operation ist entweder ein + Zeichen, das den Add Wert analysiert, oder * , das den Mul analysiert:

 -- binOp ::= '+' | '*' binOpParser :: Parser Operator binOpParser = plusParser <|> multParser where plusParser = charP '+' $> Add multParser = charP '*' $> Mul

Der einfachste Teil der Grammatik bleibt die Negation des Ausdrucks. Mit einem Symbol machen - dasselbe wie mit Klammern und Leerzeichen. NegateExpr Nächstes den NegateExpr Konstruktor auf das Ergebnis der rekursiven Analyse an:

 -- negExpr ::= '-' expr negParser = charP '-' *> (NegateExpr <$> exprParser)

Somit sind alle Teile des Parsers implementiert. Der Code ähnelt einer Grammatik und stimmt in seiner Struktur vollständig mit ihm überein.

Der Quellcode ist unter GitLab verfügbar: https://gitlab.com/fierce-katie/applicative-parsers-demo .

Dort ist es einfacher, das Volumen und den Grad der Ausdruckskraft zu bewerten, da es viel weniger Kommentare gibt. Sie können das Projekt mit dem Dienstprogramm Stack kompilieren und den primitiven Interpreter mit dem von uns geschriebenen Parser ausführen:

 $ stack build $ stack exec demo-parser

Für diejenigen, die alleine weiter üben möchten, kann ich Folgendes empfehlen:

Die Grammatik kann in jeder Hinsicht verbessert werden, um beispielsweise führende und hängende Leerzeichen zuzulassen, neue Operationen hinzuzufügen usw.
Der Parser übersetzt die Zeichenfolge in die interne Darstellung des Ausdrucks. Dieser Ausdruck kann berechnet und der Interpreter so konvertiert werden, dass nicht das Ergebnis der Analyse, sondern das Ergebnis der Berechnung gedruckt wird.
Entdecken Sie die Möglichkeiten der applicative-parsec attoparsec , attoparsec , optparse-applicative und optparse-applicative und versuchen Sie, sie zu verwenden.

Vielen Dank für Ihre Aufmerksamkeit!

Haskell Applicative Parsers