Mathematical expression interpreter

Your task is to:

1. Write monadic parsing combinators
2. Define a structure to represent a parsed mathematical expression in Haskell
3. Write a parser, which parses a string into the structure
4. Write an interpreter for the structure, which performs the calculation and returns the result.

NOTE: the parser and interpreter should be independent.

You will have to handle division by zero errors.

The basic expression

Formal Definition

Note that the expressions can be nested arbitrarily deeply.

Also note, that a number can only be an integer.

The / operator is integer division truncated towards negative infinity (div in Haskell).

<expression> ::= <number> | <operation>

<number> ::= "-" <digits> | <digits>

<digits> ::= <digit> | <digit> <digits>
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

<operation> ::= "(" <spaces> <expression> <spaces> <operator> <spaces> <expression> <spaces> ")"

<operator> ::= "+" | "-" | "*" | "/"

<spaces> ::= "" | " " <spaces>

Exmaples

These all represent valid expressions:

• ((1 + 2) * 3)
• 1
• (((1 + 2) *3) +(1 + 1) )

The proposed approach

The proposed approach is to use the following monad for parsing

type Parser a = StateT String [] a

StateT String -- the state contains the String being currently parsed.

[] -- the base monad should be a list. This will provide us with the context of trying different combinations of alternatives, and will also provide a failure context (the empty list).

The result of the parser would be a (possible infinity) list of possible parsed values. You should take the first one.

You can provide a different definition of the Parser monad, but you can not use a monad, which was intended for parsing.

Minimal required combinators

This combinator should read and return exactly one character from the input. If there are no characters to read from the input, then it should fail.

anyToken :: Parser Char

This combinator should read and return exactly one character from the input. If the character does not match the given character, then it should fail.

token :: Char -> Parser ()

This combinator should read a string of charracters. If the string does not match the given string then fail.

tokens :: String -> Parser ()

This character reads any number of consecutive characters, which stisfy the predicate. So this can never fail.

tokensWhile :: (Char -> Bool) -> Parser String

This character reads any number (but at least one) of consecutive characters, which stisfy the predicate. This can only fail if the first character does not satisfy the predicate.

tokensWhile1 :: (Char -> Bool) -> Parser String

Simple example

A sample parser might look something like this

number :: Parser Int
number = do
  sign <- signParser
  digits <- digitsParser
  return (read (sign <> digits))

Control

The proposed approach of handling control is using the Alternative typeclass.

The instance for [] already provides the following behavior:

empty represents a failure (no values).

<|> represents parsing alternative. For example an expression can be either an operation or a number.

Complex expressions

This is a slightly more complex version of expressions -- it includes conditional expressions

This represents the new parts:

<expression> ::= <number> | <operation> | <conditional>

<conditional> ::= "if " <spaces> <bool_expression> <spaces> " then " <spaces> <expression> <spaces> " else " <spaces> <expression>

<bool_expression> ::= "(" <spaces> <expression> <spaces> <bool_operator> <spaces> <expression> <spaces> ")"

<bool_operator> = "=" | "<" | ">" | "<=" | ">="

Examples

These all represent valid expressions:

• if ( 1 = 2 ) then (2 + 4) else 2
• (((1 + 2) *3) +( if ( 1 = 2 ) then (2 + 4) else 2 + 1) )

Artifacts

You should export the calculate function, which should parse the given string and return the computed result. If any of the steps involved fail (couldn't parse the string or there was a divide by zero error), you should return Nothing.

calculate :: String -> Maybe Int

Libraries you can use

You can use these two libraries:

• base
• mtl

Grading

Requirement	Score
Definition of the structure, representing the expression	1
Definition of the minimal monadic parser combinators	2
Definition of the expression parser	2
Definition of the expression interpreter	2
All of the above for complex expressions	2
Proper decomposition of functionality and coding style	1