Assignment Task
Part 1
By the end of this section, we will have a parser for lambda calculus expressions.
Exercise 1: Construct a BNF Grammar for lambda calculus expressions
Deliverables
At the end of this exercise, we should have the following:
A BNF grammar to demonstrate the structure of the lambda expression parser, representing both short and long form in one grammar (as your parser should also handle both short and long form).
Recommended steps
Construct parsers for lambda calculus expression components (“λ”, “.”, “(“, “)”, “x”, “y”, “z”, etc.) Use the component parsers to create parsers for simple combinators to get familiar with parsing lambda expressions and their structure Construct a BNF grammar for short form and long form lambda expressions
Exercise 2: Construct a parser for long form lambda calculus expressions
Deliverables
At the end of this exercise, we should have at least the following parser:
longLambdaP :: Parser Lambda
Parses a long form lambda calculus expression
Your BNF grammar must match your parsers. It is highly recommended to use the same name for your parsers and non-terminals (i.e. a non-terminal like should correspond to a lambdaChar parser) so your marker can easily validate the grammar.
Recommended steps
Build a general-purpose lambda calculus parser combinator which:
Parses general multi variable lambda expressions/function bodies Note default associativity, e.g. λxy.xxy = λxy.(xx)y Parses general multivariable lambda expressions/function bodies with brackets
E.g λxy.x(xy)
Parses any valid lambda calculus expression using long-form syntax
E.g. (λb.(λt.(λf.b t f)))
Exercise 3: Construct a parser for short form lambda calculus expressions
Deliverables
At the end of this exercise, we should have at least the following parsers:
short LambdaP :: Parser Lambda
Parses a short form lambda calculus expression
lambdaP :: Parser Lambda
Parses both long form and short form lambda calculus expressions Similar to Exercise 2, your parser must match your BNF grammar. Recommended steps Build a general purpose lambda calculus parser combinator which: Parses any valid lambda expression using short-form syntax E.g. λbtf.b t f
Part 2
By the end of this section, we should be able to parse arithmetic and logical expressions into their equivalent lambda calculus expressions.
Exercise 1: Construct a parser for logical statements
Deliverables
At the end of this exercise, you should have the following parsers:
logicP :: Parser Lambda
Parse simple to complex logical clauses
Recommended steps
Construct a parser for logical literals (“true”, “false”) and operators (“and”, “or”, “not”, “if”) into their church encoding Use the logical component parsers to build a general logical parser combinator into the equivalent church encoding, which:
Correctly negates a given expression
E.g. not not True
Parses complex clauses with nested expressions
E.g. not True and False or True
Parses expressions with the correct order of operations (“()” -> “not” -> “and” -> “or”)
Exercise 2: Construct a parser for arithmetic expressions
Requirements
At the end of this exercise, you should have the following parsers:
basicArithmeticP :: Parser Lambda
Parses simple arithmetic expressions (+, -)
arithmeticP :: Parser Lambda
Parses complex arithmetic expressions (+, -, *, **, ()) with correct order of operations
Recommended steps
Construct a parser for natural numbers into their church encoding (“1”, “2”, …) Construct a parser for simple arithmetic operators with natural numbers into equivalent lambda expressions. (“+”, “-”) See the Parser combinators section of the notes for some examples Construct a parser for complex mathematical expressions with natural numbers into their equivalent lambda expressions. (“*”, “**”, “()”) It may be useful to write a BNF for this Using the component parsers built previously to build a parser combinator for complex arithmetic expressions.
Note: the correct order of operations, e.g. 5 + 2 * 3 – 1 = 5 + (2 * 3) – 1
Exercise 3: Construct a parser for comparison expressions
Requirements
At the end of this exercise, you should have the following parsers:
complexCalcP :: Parser Lambda
Parses expressions with logical connectives, arithmetic and in/equality operations
Recommended steps
Construct a parser for complex conditional expressions into their equivalent church encoding (>, <, <=, >=, ==, !=) Using the parsers from the previous exercises, create a parser which parses arithmetic expressions separated by logical connectives and in/equality operations
E.g. (1 + 3 < 5 xss=removed>
Part 3
This section of the assignment will include a sequence of exercises that may build to parse basic Haskell functionality, which can be used to build more complex Haskell expressions or structures.
Exercise 1: Construct a parser for basic Haskell constructs
Requirements
At the end of this exercise, you should have the following parsers:
listP :: Parser Lambda
Parses a haskell list of arbitrary length into its equivalent church encoding
listOpP :: Parser Lambda
Parse simple list operations into their church encoding
Recommended steps
Construct a parser for Haskell lists (empty lists, lists of n elements, arbitrary sized lists) Construct parsers for simple list operations (null, isNull, head, tail, cons)
Exercise 2: Construct a parser for more advanced concepts
Requirements At the end of this exercise you should have parsers that: Parse some complex language features (of your choice) that bring you closer to defining your own language.