CS 480

PA2: Decaf Lexer

Objective

The goal of our semester-long project is to gain experience in compiler implementation by constructing a simple compiler.

The goal of this part of the project is to gain experience specifying lexical analysis patterns by using regular expressions to implement the first pass of our Decaf compiler.

Introduction

The semester-long project for this course is to build a compiler for the Decaf language. In this project, you will implement a lexer for Decaf, which will be the first phase in our compiler. You will do this by creating regular expressions to describe various pieces of the Decaf language, and writing some Java code to repeatedly apply these regular expressions to an input character stream.

Thoroughly read the "Lexical Considerations" section of the reference document and look over the grammar in the next section. For this assignment, you will need to construct a lexer that will scan a Decaf program and produce a stream of tokens.

You should download the project starter files from the "Files" tab in Canvas. You may also be interested in the Eclipse setup tutorial.

Before you begin writing code, you should spend some time reading through all of the infrastructure files provided in the starter files. Our compiler this semester is a large project. Your solution will need to interface with several other classes, and you will need to thoroughly read through those classes to understand their interactions. Also, there are utility functions that you may find useful.

As you study the code, you may find it useful to generate Javadoc references for the existing project files. Assuming you have Javadoc set up properly, you can do this by running the following sequence of commands in the project folder:

mkdir doc
cd src/main/java
javadoc -d ../../../doc edu.jmu.decaf

This should generate Javadoc files in the doc folder; to read them, just open the index.html file in your web browser.

If you have questions about the existing code, please ask them on the Piazza forum (see the link on the sidebar in Canvas).

Assignment

WARNING: You should only proceed with actual development once you are SURE you understand exactly what your task is and how your code should interact with the rest of the system.

Implement the MyDecafLexer class by providing an implementation for the following function:

    public Queue<Token> lex(BufferedReader input, String filename)
            throws IOException, InvalidTokenException

This function takes as input a BufferedReader object that should be used to read in the Decaf source, and a filename that should be used to create source line information. The function should return a queue of scanned Token objects.

The Token objects should contain source code information, encoded in SourceInfo objects. The source info should contain filename, line, and column information for all tokens. For multi-character tokens, the reported column should be the column of the first character in the token.

For this particular project, you should pay special attention to the following classes:

• DecafCompiler - The overall driver for the compiler. Right now it only implements the lexer phase of compilation; it will gradually expand over the semester as we implement more phases of the compiler.
• DecafLexer - The base lexer class. You will implement a subclass of this class, and you may find some of the methods provided in the parent class useful in your solution.
• Token - Stores a single Decaf token. Your code should generate a stream of these objects, stored in a Queue.
• SourceInfo - Stores source file information (i.e., filename, line number, and column number). Your code should make sure this information is present in any Token object you return.
• InvalidTokenException - Special exception that your code should throw when you detect an invalid token.

The recommended solution for this project (as discussed in class) is to process the input one line at a time. Write one regex per token type in general (there may be one or two exceptions). Use the "^" operator to match only against the beginning of the string. Prioritize your regular expressions and try each of them in order. When you find a match, extract the matching text from the line (check out DecafLexer for a function that will do this for you!) and continue until either no regex matches the next input (i.e., an InvalidTokenException) or the entire input is consumed.

Sample Input

def int main()
{
	int a;
	a = 4 + 5;
	return a;
}

Sample Output

KEY	"def"	[pa02-sample.decaf:1:1]
KEY	"int"	[pa02-sample.decaf:1:5]
ID 	"main"	[pa02-sample.decaf:1:9]
SYM	"("	[pa02-sample.decaf:1:13]
SYM	")"	[pa02-sample.decaf:1:14]
SYM	"{"	[pa02-sample.decaf:2:1]
KEY	"int"	[pa02-sample.decaf:3:2]
ID 	"a"	[pa02-sample.decaf:3:6]
SYM	";"	[pa02-sample.decaf:3:7]
ID 	"a"	[pa02-sample.decaf:4:2]
SYM	"="	[pa02-sample.decaf:4:4]
DEC	"4"	[pa02-sample.decaf:4:6]
SYM	"+"	[pa02-sample.decaf:4:8]
DEC	"5"	[pa02-sample.decaf:4:10]
SYM	";"	[pa02-sample.decaf:4:11]
KEY	"return"	[pa02-sample.decaf:5:2]
ID 	"a"	[pa02-sample.decaf:5:9]
SYM	";"	[pa02-sample.decaf:5:10]
SYM	"}"	[pa02-sample.decaf:6:1]

Reflection

One of the goals of this course is to encourage introspection and thoughtful, deliberate development processes. For this project, you will compose a short (1-2 page) reflection paper, answering the following questions:

• How does this project fit into the overall picture of our semester-long compiler project? Why is it important?
• Describe your design and development process. Did you use a formal software development method?
• What aspects of this project proved to be the most rewarding?
• What aspects of this project proved to be the most challenging? How did you overcome these challenges?
• How do you know your submission is correct? Briefly describe your testing regimen.
• If you had to start the project again from scratch, what would you do differently?
• What concepts from our theoretical class material or techniques from our classroom activities did you apply in this project?
• Suppose you weren’t using any of the concepts or techniques we’ve covered in class this semester; how would your solution to this project be different?
• What other areas of computer science (or CS courses you’ve taken) impacted your solution to this project?
• Do you have any other feedback about this project?

Be sure to address all of the above questions in as much detail as you wish, but do not ramble. Concise answers are preferred over verbose ones.

Submission

DUE DATE: Friday, September 23, 23:59 EDT (11:59PM)

Please submit your .java file and your reflection paper to the appropriate assignments on Canvas.

Your reflection paper should be in a standard document format: plain text and PDF are preferred, but OpenDocument and MS Word files are also acceptable.

Code Reviews

One of the goals of this course is to encourage good software development practices, especially when building a large software system (such as a compiler). For this project, you will be assigned two other random students in the course. You must review their code and offer constructive feedback according to the given rubric.

More details and due date TBD.

Grading

Here is the grading breakdown for this project: