Coursework 3: WHILE Language Parser
Coursework 3
This coursework is worth 10% and is due on 27 November at 16:00. You are asked to implement a parser for the WHILE language and also an interpreter. You can do the implementation in any programming language you like, but you need to submit the source code with which you answered the questions, otherwise a mark of 0% will be awarded. You should use the lexer from the previous coursework for the parser. Please submit your code to Github by the deadline.
Question 1
Design a grammar for the WHILE language and give the grammar rules. The main categories of non-terminals should be:
-
arithmetic expressions (with the operations from the previous course- work, that is +, -, *, / and %)
-
boolean expressions (with the operations ==, <, >, >=, <=, !=, &&, ||, true and false)
-
single statements (that is skip, assignments, ifs, while-loops, read and write)
-
compound statements separated by semicolons
-
blocks which are enclosed in curly parentheses Make sure the grammar is not left-recursive.
Question 2
You should implement a parser for the WHILE language using parser combina- tors. Be careful that the parser takes as input a stream, or list, of tokens generated by the tokenizer from the previous coursework. For this you might want to fil- ter out whitespaces and comments. Your parser should be able to handle the WHILE programs in Figures 3 – 6. In addition give the parse tree according to your grammar for the statement:
if (a < b) then skip else a := a * b + 1 1
The output of the parser is an abstract syntax tree (AST). A (possibly incom- plete) datatype for ASTs of the WHILE language is shown in Figure 1.
Question 3
Implement an interpreter for the WHILE language you designed and parsed in Question 1 and 2. This interpreter should take as input an AST. However be careful because, programs contain variables and variable assignments. This means you need to maintain a kind of memory, or environment, where you can look up a value of a variable and also store a new value if it is assigned. Therefore an evaluation function (interpreter) needs to look roughly as follows
eval_stmt(stmt, env)
where stmt corresponds to the parse tree of the program and env is an envi- ronment acting as a store for variable values. Consider the Fibonacci program in Figure 3. At the beginning of the program this store will be empty, but needs to be extended in line 3 and 4 where the variables minus1 and minus2 are as- signed values. These values need to be reassigned in lines 7 and 8. The pro- gram should be interpreted according to straightforward rules: for example an if-statement will “run” the if-branch if the boolean evaluates to true, otherwise the else-branch. Loops should be run as long as the boolean is true. Note also that some programs contain a read-statement, which means you need to read and integer from the commandline and store the value in the corresponding variable. Programs you should be able to run are shown in Figures 3 – 6. The output of the primes.while should look as follows:
Give some time measurements for your interpreter and the loop program in Figure 4. For example how long does your interpreter take when start is ini- tialised with 100, 500 and so on. How far can you scale this value if you are willing to wait, say 1 Minute?
2
|
abstract class Stmt |
|
abstract class AExp |
|
abstract class BExp |
|
type Block = List[Stmt] |
|
case object Skip extends Stmt |
case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
// for printing variables and strings
|
case class While(b: BExp, bl: Block) extends Stmt |
|
case class Assign(s: String, a: AExp) extends Stmt |
|
case class Read(s: String) extends Stmt |
|
case class WriteVar(s: String) extends Stmt |
|
case class WriteStr(s: String) extends Stmt |
|
case class Var(s: String) extends AExp |
|
case class Num(i: Int) extends AExp |
|
case class Aop(o: String, a1: AExp, a2: AExp) extends |
|
case object True extends BExp |
|
case object False extends BExp |
|
case class Bop(o: String, a1: AExp, a2: AExp) extends |
|
case class Lop(o: String, b1: BExp, b2: BExp) extends |
|
// logical operations: and, or |
Figure 1: The datatype for abstract syntax trees in Scala.
AExp
BExp BExp
3
|
2 |
|
3 |
|
5 |
|
7 |
|
11 |
|
13 |
|
17 |
|
19 |
|
23 |
|
29 |
|
31 |
|
37 |
|
41 |
|
43 |
|
47 |
|
53 |
|
59 |
|
61 |
|
67 |
|
71 |
|
73 |
|
79 |
|
83 |
|
89 |
|
97 |
|
Map(end -> 100, n -> 100, f -> 4, tmp -> 1) |
Figure 2: Sample output for the file primes.while.
4
|
write "Fib: "; |
|
read n; |
|
minus1 := 1; |
|
minus2 := 0; |
|
while n > 0 do { |
|
temp := minus2; |
|
minus2 := minus1 + minus2; |
|
minus1 := temp; |
|
n := n - 1 |
|
}; |
|
write "Result: "; |
|
write minus2 ; |
|
write "\n" |
Figure 3: Fibonacci program in the WHILE language.
5
|
start := 1000; |
|
x := start; |
|
y := start; |
|
z := start; |
|
while 0 < x do { |
|
while 0 < y do { |
|
while 0 < z do { z := z - 1 }; |
|
z := start; |
|
y := y - 1 |
|
}; |
|
y := start; |
|
x := x - 1 |
|
} |
Figure 4: The three-nested-loops program in the WHILE language. Usually used for timing measurements.
|
// prints out prime numbers from 2 to 100 |
|
end := 100; |
|
n := 2; |
|
while (n < end) do { |
|
f := 2; |
|
tmp := 0; |
|
while ((f < n / 2 + 1) && (tmp == 0)) do { |
if((n/f)*f==n)then {tmp:=1}else{skip}; if (tmp == 0) then { write(n); write("\n") } else { skip };
Figure 5: Prime number program.
6
|
f := f + 1 |
|
}; |
|
n :=n+1 |
|
} |
|
// Collatz series |
|
// |
|
// needs writing of strings and numbers; comments |
|
bnd := 1; |
|
while bnd < 101 do { |
|
write bnd; |
|
write ": "; |
|
n := bnd; |
|
cnt := 0; |
|
while n > 1 do { |
|
write n; |
|
write ","; |
|
if n % 2 == 0 |
|
then n := n / 2 |
|
else n := 3 * n+1; |
|
cnt := cnt + 1 |
|
}; |
|
write " => "; |
|
write cnt; |
|
write "\n"; |
|
bnd := bnd + 1 |
|
} |
Figure 6: Collatz series program.
7
Answers
Name:
Question 1 (Grammar):
8
Question 2 (Parse Tree):
Question 3 (Timings):
n 100 500 700 1000
secs
