1. Homepage
  2. Programming
  3. Coursework 3: WHILE Language Parser

Coursework 3: WHILE Language Parser

Engage in a Conversation
KCLWHILE LanguageParserASTScala

Coursework 3 CourseNana.COM

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. CourseNana.COM

Question 1 CourseNana.COM

Design a grammar for the WHILE language and give the grammar rules. The main categories of non-terminals should be: CourseNana.COM

  • arithmetic expressions (with the operations from the previous course- work, that is +, -, *, / and %) CourseNana.COM

  • boolean expressions (with the operations ==, <, >, >=, <=, !=, &&, ||, true and false) CourseNana.COM

  • single statements (that is skip, assignments, ifs, while-loops, read and write) CourseNana.COM

  • compound statements separated by semicolons CourseNana.COM

  • blocks which are enclosed in curly parentheses Make sure the grammar is not left-recursive. CourseNana.COM

    Question 2 CourseNana.COM

    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: CourseNana.COM

    if (a < b) then skip else a := a * b + 1 1 CourseNana.COM

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. CourseNana.COM

Question 3 CourseNana.COM

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 CourseNana.COM

eval_stmt(stmt, env) CourseNana.COM

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: CourseNana.COM

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? CourseNana.COM

abstract class Stmt CourseNana.COM

abstract class AExp CourseNana.COM

abstract class BExp CourseNana.COM

type Block = List[Stmt] CourseNana.COM

case object Skip extends Stmt CourseNana.COM

case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt CourseNana.COM

// for printing variables and strings CourseNana.COM

case class While(b: BExp, bl: Block) extends Stmt CourseNana.COM

case class Assign(s: String, a: AExp) extends Stmt CourseNana.COM

case class Read(s: String) extends Stmt CourseNana.COM

case class WriteVar(s: String) extends Stmt CourseNana.COM

case class WriteStr(s: String) extends Stmt CourseNana.COM

case class Var(s: String) extends AExp CourseNana.COM

case class Num(i: Int) extends AExp CourseNana.COM

case class Aop(o: String, a1: AExp, a2: AExp) extends CourseNana.COM

case object True extends BExp CourseNana.COM

case object False extends BExp CourseNana.COM

case class Bop(o: String, a1: AExp, a2: AExp) extends CourseNana.COM

case class Lop(o: String, b1: BExp, b2: BExp) extends CourseNana.COM

// logical operations: and, or CourseNana.COM

Figure 1: The datatype for abstract syntax trees in Scala. CourseNana.COM

write "Fib: "; CourseNana.COM

read n; CourseNana.COM

minus1 := 1; CourseNana.COM

minus2 := 0; CourseNana.COM

while n > 0 do { CourseNana.COM

temp := minus2; CourseNana.COM

minus2 := minus1 + minus2; CourseNana.COM

minus1 := temp; CourseNana.COM

n := n - 1 CourseNana.COM

write "Result: "; CourseNana.COM

write minus2 ; CourseNana.COM

write "\n" CourseNana.COM

Figure 3: Fibonacci program in the WHILE language. CourseNana.COM

start := 1000; CourseNana.COM

x := start; CourseNana.COM

y := start; CourseNana.COM

z := start; CourseNana.COM

while 0 < x do { CourseNana.COM

while 0 < y do { CourseNana.COM

while 0 < z do { z := z - 1 }; CourseNana.COM

z := start; CourseNana.COM

y := y - 1 CourseNana.COM

y := start; CourseNana.COM

x := x - 1 CourseNana.COM

Figure 4: The three-nested-loops program in the WHILE language. Usually used for timing measurements. CourseNana.COM

// prints out prime numbers from 2 to 100 CourseNana.COM

end := 100; CourseNana.COM

n := 2; CourseNana.COM

while (n < end) do { CourseNana.COM

f := 2; CourseNana.COM

tmp := 0; CourseNana.COM

while ((f < n / 2 + 1) && (tmp == 0)) do { CourseNana.COM

if((n/f)*f==n)then {tmp:=1}else{skip}; if (tmp == 0) then { write(n); write("\n") } else { skip }; CourseNana.COM

Figure 5: Prime number program. CourseNana.COM

6 CourseNana.COM

f := f + 1 CourseNana.COM

n :=n+1 CourseNana.COM

// Collatz series CourseNana.COM

// needs writing of strings and numbers; comments CourseNana.COM

bnd := 1; CourseNana.COM

while bnd < 101 do { CourseNana.COM

write bnd; CourseNana.COM

write ": "; CourseNana.COM

n := bnd; CourseNana.COM

cnt := 0; CourseNana.COM

while n > 1 do { CourseNana.COM

write n; CourseNana.COM

write ","; CourseNana.COM

if n % 2 == 0 CourseNana.COM

then n := n / 2 CourseNana.COM

else n := 3 * n+1; CourseNana.COM

cnt := cnt + 1 CourseNana.COM

write " => "; CourseNana.COM

write cnt; CourseNana.COM

write "\n"; CourseNana.COM

bnd := bnd + 1 CourseNana.COM

Figure 6: Collatz series program. CourseNana.COM

Answers CourseNana.COM

Question 1 (Grammar):


Question 2 (Parse Tree): CourseNana.COM

Question 3 (Timings): CourseNana.COM

n 100 500 700 1000 CourseNana.COM

Get in Touch with Our Experts

Wechat WeChat
Whatsapp Whatsapp
KCL代写,WHILE Language代写,Parser代写,AST代写,Scala代写,KCL代编,WHILE Language代编,Parser代编,AST代编,Scala代编,KCL代考,WHILE Language代考,Parser代考,AST代考,Scala代考,KCLhelp,WHILE Languagehelp,Parserhelp,ASThelp,Scalahelp,KCL作业代写,WHILE Language作业代写,Parser作业代写,AST作业代写,Scala作业代写,KCL编程代写,WHILE Language编程代写,Parser编程代写,AST编程代写,Scala编程代写,KCLprogramming help,WHILE Languageprogramming help,Parserprogramming help,ASTprogramming help,Scalaprogramming help,KCLassignment help,WHILE Languageassignment help,Parserassignment help,ASTassignment help,Scalaassignment help,KCLsolution,WHILE Languagesolution,Parsersolution,ASTsolution,Scalasolution,