Compiler Construction – SMD163

Programming project

Instructions

• The project consists of a total of 4 steps.
• You can use the machine smd163.csee.ltu.se to develop your compiler. Please let us know if there is any problems or the machine becomes too slow.
• On the lab machine the module command is available to add modules. To get both JFlex and Jacc you can type:

  tau10:/home/leijon> module add jdk
  tau10:/home/leijon> module add Jacc
  tau10:/home/leijon> module add JFlex
  

• There are links to the jflex/jacc homepages from the main course homepage.

Step 1

• Implement a lexer for MiniJava using JFlex
  
  
• A short main method shall call the lexer repeatedly, and print ”Lexical analysis succeeded/failed”
  depending on whether lexical errors were found in the input.
  
  
• The lexer shall handle the MiniJava test suite correctly.
  
  See further the MiniJava project home page.
  
  
• The MiniJava lexical syntax is described in Appel, Appendix 1; we recapitulate it here for the
  benefit of those without access to the text book. However, we make one exception to the original
  description:
  
  Handling /* nested /* comments is not */ necessary! */
  
  We also add the clarification that white space consists of any sequence of the space, tab,
  newline, and the carriage return characters, and that white space may appear between any two
  tokens, or between a token and a comment.
  
  Quoting Andrew W. Appel, Modern compiler implementation in Java, 2nd edition:
  

  A.1    LEXICAL ISSUES
  

  Identifiers:  An identifier is a sequence if letters, digits, and underscores, starting with a letter.
     Uppercase letters are distinguished form lowercase. In this appendix the symbol id stands for
     an identifier.
  Integer literals:  A sequence of decimal digits is an integer constant that denotes the
     corresponding integer value. In this appendix the symbol INTEGER_LITERAL stands for an
     integer constant.
  Binary operators:  A binary operator is one of
          &&  <  +  -  *
     In this appendix the symbol op stands for a binary operator.
  Comments:  A comment may appear between any two tokens. There are two forms of
     comments: One starts with /*, ends with */, [and may be nested]; another begins with //
     and goes to the end of the line.
  

  A.2   GRAMMAR

  See the online definition.
  

Step 2

• Implement a parser for the MiniJava language according to the grammar in Appel, Appendix
  A.1. Generate a bottom-up parser with Jacc
  
  
• Apart from simply checking whether the input conforms to the MiniJava definition, the parser
  should also construct an abstract syntax representation of the parsed program. You are advised to make use of the predefined abstract syntax classes that come with the
  MiniJava project (available here as a gzipped tar-file).
  
  
• Input to the parser should be the token stream produced by the lexer implemented in step 1.
  
  
• To make it possible to observe the result of parsing, your program should print a textual
  representation of the abstract syntax tree once it is built. The MiniJava project provides ready-
  made classes using the visitor pattern for this purpose, see this link for a gzipped tar-file of the
  visitor package.
  
  
• Note: the grammar specification in Appel, A.2 cannot be used as is in any of the parser
  implementations listed above. The challenge is thus to rewrite the grammar so that it suits the
  parsing technique you have chosen. This particularly involves sorting out how nested
  expressions like !a.b(c)+d[e]*f.length<g.h().i() should be read, and how to
  express that grammatically.

Step 3

Step 4

• Be very economic: Write for your lecturer and informed colleagues, not for a reader
  unaware of the assignment.
  
  
• Start by describing the structure of your compiler, in terms of phases, passes, and
  class organization.
  
  
• Focus on your design choices; i.e., things that are important in order to understand
  your particular solution.
  
  
• Emphasize areas where you belive your solution has particular benefits, as well as parts
  where you think your compiler doesn't work as well as you would like.
  
  
• Your aim should be to help the reader see the big picture of your implementation.
  
  
• Do not repeat in plain text facts that are obvious in the source code, like the type of
  method arguments.
  
  
• Do not write less than two, and not more than six pages of text.