Spring 2017

Assignment 1 (due feb 23 @ 7pm)


Formal Grammars and Notation

You will need to be familiar with the notion of a formal grammar, and in particular need to be able to work with a specification of a new language detailed in this document. If the assignment is difficult to read, we suggest reviewing the foundational concepts.

Git Repository

You will also need to be familiar with git, as the scaffolding for assignment one is hosted at git@github.com:6035/sp17-master. In this repository you will find this description as well as helper code assisting with the implementation of this assigment. Furthermore, all assigment submissions for the semester will be pushed to your own designated git repository hosted at git@github.com:6035/sp17-$KERBEROS where $KERBEROS should be treated as a formal variable evaluating to the text string of your MIT kerberos id.


Submission of your assigment should be accomplished by pushing your code to a branch with the name a1-submission . The last assignment pushed to this branch before the assignment due date (february 23 @ 7pm) is what will count as your final submission, unless you notify the staff otherwise.


Parsing MITScript

Your goal for this assignment is to create a parser for the MITScript language. The grammar for the language is shown below. Program ::= Statement* ;; Statement ::= Assignment | CallStatement | Global | IfStatement | WhileLoop | Return;; Global ::= 'global' name ';' ;; Assignment ::= LHS '=' Expression ';' ;; CallStatement ::= Call ';' ;; Block ::= '{' Statement* '}';; IfStatement ::= 'if' '(' Expression ')' Block ( 'else' Block )? ;; WhileLoop ::= 'while' '(' Expression ')' Block ;; Return ::= 'return' Expression ';' ;; ;; Expression ::= Function | Boolean | Record ;; Function ::= 'fun' '(' Name* ')' Block ;; Boolean ::= Conjunction ( '|' Conjunction )* ;; Conjunction ::= BoolUnit ('&' BoolUnit)* ;; BoolUnit ::= '!'? Predicate ;; Predicate ::= Arithmetic ( ('<' | '>' | '<=' | '>='| '==') Arithmetic)?;; Arithmetic ::= Product ( ('+' | '-') Product)* ;; Product ::= Unit ( ('*' | '/') Unit)* ;; Unit ::= '-'? (LHS | Constant | Call | '(' Boolean ')' );; LHS ::= Name ('.' Name | '[' Expression ']' )* ;; Call ::= LHS '(' (Expression (',' Expression)*)? ')' ;; Record ::= '{' (Name ':' Expression ';')* '}' ;; Constant ::= integer_constant | string_constant

Implementation: lexing and scanning

You will create a lexer and a scanner for the language above using the
flex and Bison scanner and parser generators. If you are using the course provided VM, both programs are already installed. There are a number of tutorials on the web, in addition to the instruction manuals linked above.

Starter Code

The starter code for the lexer sits in a file named "lexer.lex", and the starter code for the parser sits in a file called "parser.yy".

The Lexer

Your lexer must be able to recognize the following kinds of tokens in addition to all the keywords and operators listed above:
  • integer constants consisting of one or more digits
  • string constants wrapped in double quotes and supporting the following escaped characters: \\ \" \n \t
  • None constant, equivalent to "NULL" in Java
  • 'true' and 'false'
  • Name identifiers that start with a letter or underscore, followed by sequence of letters, underscores and numbers. so x0 is a valid variable name, but 0x is not

You need to make sure that all arithmetic operators are left associative, so (w+x+y+z) should be parsed as (((w+x)+y)+z)


Your parser must produce an AST with nodes for the following program constructs: Block ::= [Statement] ;; Global ::= name ;; Assignment ::= LHS Expression ;; ExpressionStatement ::= Expression ';' ;; IfStatement ::= Condition ThenPart ElsePart ;; WhileLoop ::= Condition Body ;; Return ::= Expression ;; ;; FunctionDeclaration ::= [Arguments] Body ;; BinaryExpression ::= LeftOperand Operator RightOperand ;; UnaryExpression ::= Operand Operator ;; FieldDereference ::= BaseExpression Field ;; IndexExpression ::= BaseExpression Index ;; Call ::= TargetExpression [Arguments] ;; Record ::= Map[String, Expression] ;; IntegerConstant ;; StringConstant ;; NoneConstant ;;


Your parser should read a program from stdin, parse it into an AST and pretty print the AST to stdout. Specifically, you must:
  • Write the parser and lexer
  • Define all the types for your AST nodes
  • Define a visitor interface
  • Define a PrettyPrinter class that extends the visitor interface and pretty prints the AST
We don't care that much about how well your output is formatted. One strict requirement is that your pretty printer should wrap all binary and unary expressions in parenthesis. For unary expressions, the operator should be outside the parenthesis, so for example !x should be pretty printed to !(x). You should provide 3 tests named test1.mit, test2.mit and test3.mit that your parser can parse correctly. Your tests should provide good coverage of the constructs in the language.

Implementation notes

For this assignment, you do not have to worry about reclaiming memory (we will implement garbage collection in a later assignment).

Questions or comments regarding 6.035? Send e-mail to the TAs at 6.035-staff@mit.edu.

Top // 6.035 home // Last updated