Skip to content

Latest commit

 

History

History
124 lines (92 loc) · 5.04 KB

5.md

File metadata and controls

124 lines (92 loc) · 5.04 KB
Raw

PA5: Optional assignment

This assignment is purely optional. There are three parts. You can choose to do Part 1 or Part 2 or both. If you do both, you can choose to complete Part 3 as well.

Part 1 (40%)

Extend your Grumpy language implementation to support 'while' loops, a 'print' expression for printing values to stdout, and a 'size' instruction for reading the size of an array.

e ::= ...                 // Everything from before.
      (while econd ebody) // While loop with guard condition econd and body ebody.
      (print e)           // Print the value of e followed by a newline.
      (size e)            // Get size of array (as i32).

This extension will touch many components of the Grumpy system. Concretely, it includes extending:

  • the ir::Exp type with constructors for the new expression forms.
  • the bound_vars method to support the new Exp constructors.
  • the GrumpyIR parser to support parsing the new expression forms.
  • the compiler to generate code for the new Exp constructors.
  • the Grumpy assembly language and VM to support:
    • a 'print' instruction that pops the top value on the stack and prints it to stdout.
    • a 'size' instruction that pops the array address from the top of the stack and pushes the size of the array at that address to the stack.

Note that the VM is already capable of supporting 'while' loops via conditional branching.

When compiling 'print' expressions, don't forget about the compilation invariant (hint: the type of a 'print' expression is unit).

Your executable should implement the entire pipeline from reading in the .gpy program to printing out the final result (by internally compiling the program to assembly, assembling it to bytecode, and running it in the vm).

Part 2 (40%)

Use a lexer/parser generator tool to implement a parser for the Grumpy source language syntax given by the following specification:

<num> := [0-9]+
<name> := [a-zA-Z]+[a-zA-Z0-9]*

// Values
<val> ::=
  | <num>   // i32
  | true    // boolean true
  | false   // boolean false
  | tt      // unit value

// Unary Operators
<unop> ::=
  | !  // unary negation
  | -  // unary minus (desugar to binary subtraction from 0)

// Binary Operators
<binop> ::= + | * | - | / | < | ==

Precedence levels (higher number binds tighter):
1) <, == (no associativity)
2) +, -  (left associative)
3) *, /  (left associative)
4) !

// Expressions 
<expr> ::=
  | <val>                              // value
  | <name>                             // variable
  | <unop> <expr>                      // unary operation
  | <expr> <binop> <expr>              // binary operation
  | let x = <expr> in <expr>           // let-binding
  | <expr> ; <expr>                    // sequencing
  | alloc ( <expr> , <expr> )          // allocate array
  | set ( <expr> , <expr> , <expr> )   // set array element
  | get ( <expr> , <expr> )            // get array element
  | if <expr> then <expr> else <expr>  // conditional
  | @<name>                            // function pointer
  | f ( <expr>* )                      // function call
  | ( <expr> )                         // parenthesized expression

Conditionals bind tighter than sequencing. E.g., the expression
`if true then 5 else tt; 6`
should parse as
`(if true then 5 else tt); 6`
rather than
`if true then 5 else (tt; 6)`.

// Types 
<type> ::=
  | i32
  | bool
  | unit
  | array ( <type> )
  
// Function parameters
<param> ::= <name> : <type>

// Functions
<function> ::= fn <name> ( <param>* ) -> <type> { <expr> }

// Programs
<prog> ::= <function>* <expr>

You'll have to design a grammar to meet the above specification and pass the test cases.

There are multiple parser generators in the Rust ecosystem that you can choose from, e.g., LALRPOP and pest. I (Alex) can confirm that LALRPOP is suitable for this assignment, but beware that it doesn't support declarative specification of precedence/associativity rules, so you must encode those in the grammar yourself if you choose to use LALRPOP.

Alternatively, you may use a parser generator tool with a language other than Rust and integrate it with the Grumpy pipeline by serializing IR to s-expression format and piping it through to the Rust backend (since our Grumpy crate already knows how to parse IR in s-expression format).

Just as in option 1, your executable should implement the entire pipeline from reading in the .gpy program to printing out the final result.

Part 3 (20%)

Implement both part2 1 and 2 and include concrete syntax for the extra forms:

<expr> ::= ...
  | while <expr> { <expr> }  // while loop
  | print ( <expr> )         // print expression
  | size ( <expr> )          // size of array

Submission

You can accept the assignment here. Email the TA and copy the instructors before the final exam session.

The template contains only test cases -- you should use your implementation of PA4 as the starting point. If your PA4 solution isn't complete then you may need to make some corrections before you can begin.