Spring 2018

Assignment 1 (due feb 20 @ 11:59pm)


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:6S081/cpp-skeleton. 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:6s081/sp17-$KERBEROS where $KERBEROS should be treated as a formal variable evaluating to the text string of your MIT kerberos id. If you are getting permission errors while cloning, try cloning the https link instead. If you are still getting permission errors, then make sure you have accepted the invites to both the organization and to your private repo.


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 20 @ 11:59pm) is what will count as your final submission, unless you notify the staff otherwise.

Running The Parser

We provide a class
virtual machine for you to test and compile your code on. You don't have to use it, but we strongly recommend it. This is the environment we will be using to grade your code, so please make sure it compiles in the VM. We also highly encourage using the VM for Windows users as it is typically more time consuming to get C++ building and running on Windows. To run the environment, you will need to download VMWare which could be found here. To build the project within the parser directory, run
 make parser 
and to run a specific test case run
 cat ../tests/parser/input/good1.mit | ./mitscript-parser 
after building. Finally there is a test.sh script in the tests/ directory included to help test on all of the test files at once and compare with the reference output.


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 (',' 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 | boolean_constant | none_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. Escaping any other character should result in error
  • None constant, equivalent to "NULL" in Java
  • Boolean constants '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
  • comments, which start with '//' and end at the next line break

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. We have included output files that demonstrate a valid possible output from your parser, though the output AST does not neet to match these output files character for character, they're more for reference. 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