CSCC24 2020 Winter – Assignment 3
Due: Wednesday, March 25, midnight
This assignment is worth 10% of the course grade.
In this assignment, you will implement in Haskell a parser for a toy language.
As usual, you should also aim for reasonably efficient algorithms and reasonably organized, comprehensible code.
Expression Syntax
We will have a “simple” (just you wait) expression syntax. Here is the EBNF grammar, together with the informal points afterwards for completion and disambiguation.
|
|
| “(”
Informal points:
• The start symbol is
•
• is for variable names: A letter followed by zero or more letters or digits. However, the following are reserved words and cannot be variable names: or, assert, while, do. (These are for constructs that will appear in the next assignment!)
• Ambiguity under
operator
association
||
&&
==
+, infix binary –
!, prefix unary – literal, var, parentheses
right
right
none, e.g., “x == y == z” is unexpected left
• Whitespaces around tokens are possible.
The abstract syntax tree is defined by these types:
1
data Expr = LitNat Integer | Var String
| Prim1 Op1 Expr
| Prim2 Op2 Expr Expr deriving (Eq, Show)
data Op1 = Not | Neg deriving (Eq, Show)
— typo fixed Mar 19
data Op2 = Add | Sub | EqNat | And | Or deriving (Eq, Show)
Basically Prim1 is for the unary operators, and Prim2 is for the binary operators.
Implement a parser for Orlang. A main parser mainParser is already provided, so you can
focus on the start symbol parser expr :: Parser Expr and downwards.
From the lectures, you already know how to implement infix operator precedence. The extra
challenges in this assignment are == and the prefix unary operators.
In the case of the prefix unary operators, take care that these inputs are legal and their
corresponding abstract syntax trees are:
input
AST
–5 —5 !-!5
Prim1 Neg (Prim1 Neg (LitNat 5))
Prim1 Neg (Prim1 Neg (Prim1 Neg (LitNat 5)))
Prim1 Not (Prim1 Neg (Prim1 Not (LitNat 5)))
How do you get this to work? End of questions.
(Typo fixed March 20)
2