Compilers: Program 3

Due: Friday, April 10 at 5pm

Abstract syntax trees for Jest

Before starting: Read this assignment in its entirety.

The goal of this programming assignment is to implement a conversion from concrete Jest parse trees to abstract syntax trees (that includes the construction of a symbol table and some additional information).

Part I

Download the starter project, try compiling and running it. Out of the box, it can handle a fair amount of examples.

Familiarize yourself with the files associated with this project:

src/Ast.hs              new
src/AstUnparse.hs       new (but similar to Unparse for parse trees)
src/BuildAst.hs         new - where you will do your work
src/Parse.hs            effectively solution for last assignment
src/ParseTree.hs        as before
src/Region.hs           separated from Tag from before
src/Scan.x              as before (but for one small change)
src/SemTy.hs            new
src/Tag.hs              separated, generalized from Region from before
src/Token.hs            as before
app/Main.hs             similar, but now invokes buildAst
  1. Complete the conversion of expressions:

    1. parenthesized expressions - can just pass the recursion on to the expression insider the parentheses. So, for example, the following should now work:

      let yes = !(!false);

      Explain (in README) why ParseTree has Parenthesized but Ast does not. (This is somewhat subjective.)

    2. function calls - they are just like procedure-call statements which already work! So, for example, now you should be able to handle:

      /*< (Int): Int >*/
      function negate(m) {
          let n = -m;
          return n;
      let minus3 = negate(3);
    3. binary-operator expressions - follow the model of unary-operator expressions; the actual operator conversion (opTranslate) has already been implemented for you. You should now be able to handle all valid syntactic (even if type-incorrect!) Jest expressions, for example:

      let wrong = true * 'hello' - 33;
    4. examine the readExact function (defined at the bottom of BuildAst.hs). You may find it helpful to read about Haskell’s standard-library function reads. Explain (in the README) the role of the function, in general, and specifically as it relates to conversion of literals.

  2. Complete the conversion of statements:

    1. Modify while and do statements so break and continue are handled correctly. In particular, the starter code does not allow for breaks and continues even when used “legally” as in:

      while (true) { break; }
      Program parsed successfully.
      break outside of loop at line 1 cols 16-21

      Note: you need not change anything with the break and continue cases, just the while and the do-while cases.

    2. Implement if statements; follow the model of while. Explain (in README) the distinction between the structure of else branches in ParseTreev. Ast.

    3. Implement increment (++) and decrement (--) transformations. As with assignment operators, your transformation should be desugaring. Explain (in README): give at least one pro and one con as to desugaring these kinds of statements.

    4. Modify the way return statements are handled so that errors are generated if a return statement occurs outside of a function body. (Follow the model of break and continue to make the errors recoverable - so that the error is recorded, but the transformation continues.)

  3. Implement uninitialized variable declaration lists. Explain (in README) why, in general, the type of declaration builders return lists of statements (tagged statements, but that’s a nitpick), but, in the case of uninitialized variables, no new Ast nodes are generated.


Part II: Choose your own adventure.

For this assignment, in addition to numbered exercises above, choose one of the tasks below.

Looking for more to do? Choose more than one of the above!


Submitting your work

Submit your entire project as a zipped archive (so attach the one .zip file), but run

stack purge

before zipping it up. Name the zip file something that indicates it is yours, so something like It is essential that you modify (found in the main project folder) as part of the assignment. It should include at least, your name, which aspect of part II of the assignment you chose to do and answers to any of the parts of the assignment that ask you to “explain” something. You should also include the status of the assignment as submitted: how much did you complete, known bugs, etc. The .md extension implies markdown format, but you can just use plain text in the file.

The body of your email should be left blank. Any specifics about your assignment you think I should require (for example, known bugs or what you did not have time to complete) should be included in proofread comments near the top of your file.