Parsec.ipynb

{
 "metadata": {
  "language": "haskell",
  "name": "",
  "signature": "sha256:fb4066c80626fcba86f37248c01c7c51cb25e06700d9972b7912eef2446b64bc"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "University of Zagreb<br/>\n",
      "Faculty of Electrical Engineering and Computing\n",
      "\n",
      "Programming in Haskell\n",
      "\n",
      "http://www.fer.unizg.hr/predmet/puh\n",
      "\n",
      "Academic Year 2014/2015\n",
      "\n",
      "# Introduction to Parsec\n",
      "\n",
      "&copy; 2014 Luka Skukan\n",
      "\n",
      "*Version 1.1*\n",
      "\n",
      "**Changelog**\n",
      "\n",
      "* 1.1 - Added `do` notation examples\n",
      "\n",
      "---\n",
      "\n",
      "Parsec is a *parser combinator* library. What does that mean?\n",
      "\n",
      "Parsers are constructed from simple buildings blocks that are combined in various ways.\n",
      "Let us begin by constructing a simple parser that parses a single digit."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Text.Parsec.String (Parser)\n",
      "import Text.Parsec.Char (digit)\n",
      "import Text.Parsec (parse, ParseError)\n",
      "import Control.Applicative ((<$>), (<$), (<*>), (<*), (*>), Applicative)\n",
      "import Data.Char (digitToInt)\n",
      "\n",
      "err = \"An error has occurred\"\n",
      "\n",
      "simpleParse :: Parser a -> String -> Either ParseError a\n",
      "simpleParse p = parse p err\n",
      "\n",
      "parseDigit :: Parser Int\n",
      "parseDigit = digitToInt <$> digit\n",
      "\n",
      "simpleParse parseDigit \"2\"\n",
      "\n",
      "simpleParse parseDigit \"9\"\n",
      "\n",
      "simpleParse parseDigit \"a\"\n",
      "\n",
      "simpleParse parseDigit \"99\""
     ],
     "language": "python",
     "metadata": {
      "hidden": false
     },
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 2"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 9"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Left \"An error has occurred\" (line 1, column 1):\n",
        "unexpected \"a\"\n",
        "expecting digit"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 9"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "There are a few things we can note from that example:\n",
      "\n",
      "* A parser is a wrapper around its return type. A `Parser` that parses a `String` will be a `Parser String`.\n",
      "* We need to use a special parse function for parsing. It takes a `Parser`, a default error message and a `String` to parse.\n",
      "* We can get either a `Left ParseError` (like the in the third example) or `Right Int`, the thing we got out of the parser, if the thing goes right.\n",
      "* The function `digitToInt` is **pure**. Parsers are **not**! We need to \"lift\" the function to an impure level. I used the Applicative style, simply due to personal preference. However, we could also use the monadic style you use in `IO` or (in this particular case) `fmap`. In fact, it turns out that `<$>` **is** fmap.\n",
      "* The parser works for a digit, but not for a letter. This is what we want. However, it cannot parse \"99\"!\n",
      "\n",
      "Monadic style:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Control.Monad (liftM)\n",
      "\n",
      "parseDigit' :: Parser Int\n",
      "parseDigit' = do\n",
      "    d <- digit\n",
      "    return . digitToInt $ d\n",
      "    \n",
      "-- Alternatively (we didn't do this yet I think?)\n",
      "parseDigit'' :: Parser Int\n",
      "parseDigit'' = liftM digitToInt digit\n",
      "\n",
      "simpleParse parseDigit' \"8\"\n",
      "\n",
      "simpleParse parseDigit'' \"8\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 8"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 8"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "So, getting a single digit is simple enough. But what if we want more than one digit?\n",
      "\n",
      "This is where the *combinator* part comes into play. We will use a quantifier - `many1` (think of it as Kleene's + operator in regular expressions. Or don't if that doesn't help). There is also a `many` quantifier that works like Kleene's \\* operator.\n",
      "\n",
      "Let us implement a parser for positive integers in general."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Text.Parsec.Combinator (many1)\n",
      "import Control.Applicative (many)\n",
      "\n",
      "number :: Parser Int\n",
      "number = read <$> many1 digit\n",
      "\n",
      "simpleParse number \"100\"\n",
      "simpleParse number \"92\"\n",
      "simpleParse number \"-10\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 100"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 92"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Left \"An error has occurred\" (line 1, column 1):\n",
        "unexpected \"-\"\n",
        "expecting digit"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "Okay! That works for positive integers! But what about negative integers? That doesn't quite work with this - our parser makes no mention of minuses. Let's give it a go."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Text.Parsec.Char (char)\n",
      "\n",
      "infixr 5 <:>\n",
      "(<:>) :: Applicative f => f a -> f [a] -> f [a] \n",
      "a <:> b = (:) <$> a <*> b\n",
      "\n",
      "negative :: Parser Int\n",
      "negative = read <$> char '-' <:> many1 digit\n",
      "\n",
      "simpleParse negative \"-10\"\n",
      "simpleParse negative \"-9999\"\n",
      "simpleParse negative \"-0\"\n",
      "simpleParse negative \"20\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (-10)"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (-9999)"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 0"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Left \"An error has occurred\" (line 1, column 1):\n",
        "unexpected \"2\"\n",
        "expecting \"-\""
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "Note the `<*>` operator. The rule is more or less like this - for the first argument of a function you are lifting you use `<$>`. For other arguments, you use `<*>`.\n",
      "\n",
      "So, we now have two separate parsers - one that can parse positive integers and one that can parse negative integers. This is fine, but we would prefer a parser than can parse **both** and properly evaluate their value.\n",
      "\n",
      "We can use the choice combinator `<|>`!"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Control.Applicative ((<|>))\n",
      "\n",
      "integer :: Parser Int\n",
      "integer = number <|> negative\n",
      "-- alternatively Text.Parsec.Combinator.choice [number, negative]\n",
      "\n",
      "simpleParse integer \"100\"\n",
      "simpleParse integer \"-100\"\n",
      "simpleParse integer \"20\"\n",
      "simpleParse integer \" 10\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 100"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (-100)"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 20"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Left \"An error has occurred\" (line 1, column 1):\n",
        "unexpected \" \"\n",
        "expecting digit or \"-\""
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "The choice combinator tries out the parser on the left. If it fails, instead of giving an error, it tries the next one, and so on (we can chain many parsers). If none of the parsers succeed, only then is an error thrown.\n",
      "\n",
      "The last one failed - this is to be expected. We never really specified any spaces. However, in real world applications of Parsec, we are usually interested in tokens in a parsed text. These tokens are quite often surrounded by whitespace we are not interested in at all! Well, unless we're parsing Python or something.\n",
      "\n",
      "There is a simple workaround, however. We just need to ignore the spaces.\n",
      "\n",
      "We do this in two steps:\n",
      "1. Strip the leading spaces with the parser\n",
      "2. Strip the trailing spaces by defining a token parser"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Text.Parsec.Char (spaces)\n",
      "\n",
      "token :: Parser a -> Parser a\n",
      "token = (<* spaces)\n",
      "\n",
      "betterParse :: Parser a -> String -> Either ParseError a\n",
      "betterParse p = parse (spaces *> p) err\n",
      "\n",
      "integer' = token integer\n",
      "\n",
      "betterParse integer' \" 200\"\n",
      "betterParse integer' \" -50   \"\n",
      "betterParse (many1 integer') \"20 30 40 -18 2 -1\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right 200"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (-50)"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right [20,30,40,-18,2,-1]"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "There is one problem with the choice combinator `<|>`, however. If the left side of the expression consumes input before it evaluates to an error and hands the string off to the right side, that part of the string will remain consumed. \n",
      "\n",
      "Let us implement a simple parser that parses two expressions - word lists and integer lists.\n",
      "Let these lists be formed like:\n",
      "\n",
      "[dog, cat, hamster]\n",
      "\n",
      "[3, 1, 2]\n",
      "\n",
      "We will define a helper data type to hold such disparate types."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Text.Parsec.Combinator (sepBy1)\n",
      "import Text.Parsec.Char (letter)\n",
      "\n",
      "symbol :: Char -> Parser Char\n",
      "symbol = token . char\n",
      "\n",
      "data MyList = WordList { text :: [String] }\n",
      "            | IntList  { ints :: [Int] } deriving (Eq, Show)\n",
      "\n",
      "\n",
      "-- Some helper functions\n",
      "brackets :: Parser a -> Parser a\n",
      "brackets = (<* symbol ']') . (symbol '[' *>)\n",
      "\n",
      "elements :: Parser a -> Parser [a]\n",
      "elements = flip sepBy1 (symbol ',')\n",
      "\n",
      "listOf :: Parser a -> Parser [a]\n",
      "listOf = brackets . elements . token\n",
      "\n",
      "list :: Parser MyList\n",
      "list = intlist <|> strlist\n",
      "    where intlist  = IntList  <$> listOf integer'\n",
      "          strlist  = WordList <$> listOf (many1 letter)\n",
      "          \n",
      "betterParse list \"[1, 2, 3, 6, 8]\"\n",
      "betterParse list \"[dogcat, monkeypig]\" -- WHY?!"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (IntList {ints = [1,2,3,6,8]})"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Left \"An error has occurred\" (line 1, column 2):\n",
        "unexpected \"d\"\n",
        "expecting white space, digit or \"-\""
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "Well, because.\n",
      "We already consumed the `'['` symbol before we realised the first parser cannot match the expression, so the second parser doesn't match either. We have to \"unconsume\" the first symbol. Luckily, people who made Parsec thought of this and created the `try` function. Basically, if it succeeds in consuming the input, it behaves normally. If it breaks something, however, it claims it never even touched it and passes the entire input onwards.\n",
      "\n",
      "Let's use that!"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Text.Parsec (try)\n",
      "\n",
      "list' :: Parser MyList\n",
      "list' = try intlist <|> strlist\n",
      "    where intlist  = IntList  <$> listOf integer'\n",
      "          strlist  = WordList <$> listOf (many1 letter)\n",
      "          \n",
      "betterParse list' \"[1, 2]\"\n",
      "betterParse list' \"[manbearpig, unladenswallow]\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (IntList {ints = [1,2]})"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (WordList {text = [\"manbearpig\",\"unladenswallow\"]})"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "The `try` function is especially useful when dealing with variables and keywords. In many languages `if` is a keyword, but `iff` is a valid identified. Of course, you notice it's not a valid character halfway through parsing it, so backtracking is a must.\n",
      "\n",
      "\n",
      "## A small computing language\n",
      "\n",
      "Now that we know some of the basics of Parsec, let us apply them to a particular problem. We want to define a simple language that uses variables and integers to perform simple computations. An example of such a program would be:\n",
      "\n",
      "```\n",
      "a = 3 + 5\n",
      "b = a - 2 + 7\n",
      "a = 1\n",
      "```\n",
      "\n",
      "Each expressions is an assignment expression consisting of two parts:\n",
      "* A left hand side variable to which a value is being assigned\n",
      "* A right hand side expression consisting of values, variables, and the `+` and `-` operators.\n",
      "\n",
      "Let us start out by defining the structures of such a language and their evaluation."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import qualified Data.Map as M\n",
      "import Control.Monad (join)\n",
      "\n",
      "data Expression = Val   Int\n",
      "                | Var   String\n",
      "                | Plus  Expression Expression\n",
      "                | Minus Expression Expression\n",
      "                  deriving Show\n",
      "\n",
      "data Assignment = Assignment String Expression deriving Show\n",
      "\n",
      "type Program = [Assignment]\n",
      "                             \n",
      "type VarTable = M.Map String Int\n",
      "\n",
      "eval :: VarTable -> Expression -> Maybe Int\n",
      "eval vt e = case e of (Val   v)   -> Just v\n",
      "                      (Var   v)   -> M.lookup v vt\n",
      "                      (Plus  a b) -> (+) <$> eval vt a <*> eval vt b\n",
      "                      (Minus a b) -> (-) <$> eval vt a <*> eval vt b\n",
      "                      \n",
      "assign :: Assignment -> VarTable -> Maybe VarTable\n",
      "assign (Assignment v e) vt = insert v vt <$> eval vt e\n",
      "    where insert k = flip (M.insert k)\n",
      "    \n",
      "run :: Program -> Maybe VarTable\n",
      "run = run' (Just M.empty)\n",
      "    where run' vt []     = vt\n",
      "          run' vt (a:as) = run' (join $ assign a <$> vt) as\n",
      "\n",
      "-- a = 7 + -3\n",
      "-- b = a - 1\n",
      "-- a = -2\n",
      "-- c = a + b\n",
      "program = [ Assignment \"a\" (Plus (Val 7) (Val (-3)))\n",
      "          , Assignment \"b\" (Minus (Var \"a\") (Val 1))\n",
      "          , Assignment \"a\" (Val (-2))\n",
      "          , Assignment \"c\" (Plus (Var \"a\") (Var \"b\"))\n",
      "          ]\n",
      "          \n",
      "run program"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Just (fromList [(\"a\",-2),(\"b\",3),(\"c\",1)])"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "We now have an evaluator for our small language. However, writing it in Haskell is both tedious and impractical. We want to write it as text and then parse it and run it, like a proper programming language.\n",
      "\n",
      "We already have a definition for integers, but we need one for variables. Let us say the first character of a variable name has to be a letter and the rest can be alphanumeric."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Text.Parsec.Char (alphaNum)\n",
      "\n",
      "variable :: Parser String\n",
      "variable = token $ letter <:> many alphaNum\n",
      "\n",
      "betterParse variable \"var\"\n",
      "betterParse variable \" x12\"\n",
      "betterParse variable \"1x\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right \"var\""
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right \"x12\""
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Left \"An error has occurred\" (line 1, column 1):\n",
        "unexpected \"1\"\n",
        "expecting white space or letter"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "Implementing the `Expression` parser will sadly not be so trivial. In implementing this operation (and other similar operations) we encounter a problem - left recursion. The `Plus` and `Minus` instances use infix operators. This complicates things. There are two ways to solve this problem - manually and using operator tables. We will go through both.\n",
      "\n",
      "First, let us implement an Expression parser manually, using `chainl1`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Text.Parsec.Combinator (chainl1)\n",
      "\n",
      "operator :: Parser (Expression -> Expression -> Expression)\n",
      "operator = plus <|> minus\n",
      "    where plus  = symbol '+' *> return Plus\n",
      "          minus = symbol '-' *> return Minus\n",
      "\n",
      "expression :: Parser Expression\n",
      "expression = term `chainl1` operator\n",
      "    where term = val <|> var\n",
      "          var  = Var <$> variable\n",
      "          val  = Val <$> integer'\n",
      "\n",
      "betterParse expression \" 9\"\n",
      "betterParse expression \"-9\"\n",
      "betterParse expression \"1 + 9\"\n",
      "betterParse expression \"1 - 9\"\n",
      "betterParse expression \"a + 3 - b + c\"\n",
      "betterParse expression \"1--3\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Val 9)"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Val (-9))"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Plus (Val 1) (Val 9))"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Minus (Val 1) (Val 9))"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Plus (Minus (Plus (Var \"a\") (Val 3)) (Var \"b\")) (Var \"c\"))"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Minus (Val 1) (Val (-3)))"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "This is trivial for such a simple use case, but sometimes we are also concerned with operator priority, have a multitude of possible subexpressions and so on. For that reason, Parsec enables us to quickly build parsers for infix (and prefix) operations using operator tables.\n",
      "\n",
      "We define a list of lists of operators. Each sublist contains a set of operators. The order does matter - the operators in the first list have the highest priority, the operators in the second second highest and so on.\n",
      "\n",
      "Let us create a parser for the same example:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Text.Parsec.Expr\n",
      "\n",
      "-- Both of our operators have the same priority\n",
      "table = [[binary '+' Plus, binary '-' Minus]]\n",
      "        where binary name f = Infix (f <$ (symbol name)) AssocLeft\n",
      "        \n",
      "expression' :: Parser Expression\n",
      "expression' = buildExpressionParser table other\n",
      "    where other = var <|> val\n",
      "          var   = Var <$> variable\n",
      "          val   = Val <$> integer'\n",
      "          \n",
      "betterParse expression' \"9\"\n",
      "betterParse expression' \"-9\"\n",
      "betterParse expression' \"1 + 9\"\n",
      "betterParse expression' \"1 - 9\"\n",
      "betterParse expression' \"a + 3 - b + c\"\n",
      "betterParse expression' \"1--3\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Val 9)"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Val (-9))"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Plus (Val 1) (Val 9))"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Minus (Val 1) (Val 9))"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Plus (Minus (Plus (Var \"a\") (Val 3)) (Var \"b\")) (Var \"c\"))"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Right (Minus (Val 1) (Val (-3)))"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "Which one you use is a matter of preference, but the second one is certainly preferable in more complex cass.\n",
      "\n",
      "Note the variable named `other` in the example. The table lists various combinator function, while the `other` argument lists parsers that are not constructed by applying unary or binary functions to instances of `Expression`.\n",
      "\n",
      "Let us conclude this example by creating the parser for `Assignment` and a program as a whole, as well as a simple program interpreter."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "assignment :: Parser Assignment\n",
      "assignment = Assignment <$> variable <*> (symbol '=' *> expression)\n",
      "\n",
      "program :: Parser Program\n",
      "program = many1 assignment\n",
      "\n",
      "interpret :: String -> Maybe VarTable\n",
      "interpret s = case prog of Left  e -> Nothing\n",
      "                           Right p -> run   p\n",
      "    where prog = betterParse program s\n",
      "    \n",
      "example = \"a = 7 - 9 + 3 + 15\\nb = a - 9\\nc = a + a + b\\na = c + b\"\n",
      "\n",
      "interpret example"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Just (fromList [(\"a\",46),(\"b\",7),(\"c\",39)])"
       ]
      }
     ],
     "prompt_number": 37
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "As you can see, Parsec is quite good at building complex parsers from simple building blocks. This, of course, does not show the full power of Parsec, but the majority of its functionalities were covered here.\n",
      "\n",
      "For some other useful functions look at the Parsec documentation, especially the `Text.Parsec.Char` and `Text.Parsec.Combinator` libraries, as well as the `Text.Parsec.Expression` entry if you have need for Prefix operators and other associativites (Right or None).\n",
      "\n",
      "\n",
      "## Monadic (`do`) style parsers\n",
      "\n",
      "Parsers are not only Applicatives, they are also monads (as we saw at the beginning). That means we can use `do` notation, which we are more familiar with. I originally chose Applicative notation due to style preferences.\n",
      "\n",
      "Let us rewrite the same set of parsers using `do` notation instead of the `Applicative` style. Some may find this easier to understand and implement. We will define each parsing as an \"action\" of some sort."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import Control.Monad (void)\n",
      "-- Void discards an action -> it turns an m a  to an m ()\n",
      "-- where m is some monad (IO for example, so int this case IO a -> IO ())\n",
      "\n",
      "mToken :: Parser a -> Parser a\n",
      "mToken p = do\n",
      "    x <- p\n",
      "    void $ spaces -- Spaces are read, but they are not stored. We just \"skip\" them.\n",
      "    return x\n",
      "    \n",
      "mSymbol :: Char -> Parser Char\n",
      "mSymbol = mToken . char\n",
      "\n",
      "mNumber :: Parser Int\n",
      "mNumber = do\n",
      "    num <- many1 digit\n",
      "    return . read $ num\n",
      "    \n",
      "mNegative :: Parser Int\n",
      "mNegative = do\n",
      "    pref <- char '-'\n",
      "    num  <- many1 digit\n",
      "    return . read $ pref : num\n",
      "\n",
      "mInteger :: Parser Int\n",
      "mInteger = mToken p\n",
      "    where p = mNumber <|> mNegative\n",
      "\n",
      "mVariable :: Parser String\n",
      "mVariable = do\n",
      "    h <- letter\n",
      "    t <- many alphaNum\n",
      "    mToken . return $ h : t\n",
      "    \n",
      "mTable = [[binary '+' Plus, binary '-' Minus]]\n",
      "    where binary sym f = Infix (mkParser sym f) AssocLeft\n",
      "          mkParser s f = do\n",
      "              void $ mSymbol s -- read +/-, but discard it. It HAS to be there but is not used.\n",
      "              return f\n",
      "\n",
      "mExpression :: Parser Expression\n",
      "mExpression = buildExpressionParser mTable other\n",
      "    where other = var <|> val\n",
      "          var   = do\n",
      "              v <- mVariable\n",
      "              return $ Var v\n",
      "          val   = do\n",
      "              v <- mInteger\n",
      "              return $ Val v\n",
      "              \n",
      "mAssignment :: Parser Assignment\n",
      "mAssignment = do\n",
      "    name <- mVariable\n",
      "    void $ mSymbol '='\n",
      "    expr <- mExpression\n",
      "    return $ Assignment name expr\n",
      "    \n",
      "mProgram :: Parser Program\n",
      "mProgram = many1 mAssignment\n",
      "\n",
      "mInterpret :: String -> Maybe VarTable\n",
      "mInterpret s = case prog of Right p -> run p\n",
      "                            _       -> Nothing\n",
      "            where prog = betterParse mProgram s\n",
      "            \n",
      "mInterpret example"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "Just (fromList [(\"a\",46),(\"b\",7),(\"c\",39)])"
       ]
      }
     ],
     "prompt_number": 40
    }
   ],
   "metadata": {}
  }
 ]
}