Project #3: SL Parser

15-212, Spring 1998

Overview of the Assignment:

• Decide whether G can generate T (i.e. "T is in the grammar G").
• Produce a parse tree of T, which shows how to rewrite the start symbol S in G to produce T.

We will grade your program in two ways. First, we will feed it certain SL programs--some valid, some not--and check that your program outputs a valid parse for syntactically valid programs, and a meaningful error message for invalid programs. Second, we will plug your parser code into a working SL interpreter, replacing our interpreter's existing (correct) parser with yours; we'll then run the new interpreter on some SL code to see if it still runs properly. To pass the second test, your code will have to adhere tightly to the specs below.

1. The Grammar for SL:

SIGMA = { PROGRAM, FUNCTION, PARAMLIST, PARAMREST, BLOCK, STATEMENT, BREAK, CALL, ARGLIST, ARGREST, IF, ELSE, LET, READ, RETURN, WHILE, WRITE, EXPR, BINOP, UNOP, number, identifier, function, break, call, if, else, let, read, return, while, write, (, ), {, }, ,, ;, =, +, -, *, /, %, <, >, <=, >=, ==, !=, &, |, ~, !}

V = { number, identifier, function, break, call, if, else, let, read, return, while, write, (, ), {, }, ,, ;, =, +, -, *, /, %, <, >, <=, >=, ==, !=, &, |, ~, !}

S = PROGRAM

R is given below:

• PROGRAM -> FUNCTION* BLOCK
• FUNCTION -> function identifier ( PARAMLIST ) BLOCK
• PARAMLIST -> identifier PARAMREST | e
• PARAMREST -> , identifier PARAMREST | e
• BLOCK -> { STATEMENT* }
• STATEMENT -> BREAK | CALL ; | IF | LET | READ | RETURN | WHILE | WRITE
• BREAK -> break ;
• CALL -> call identifier ( ARGLIST )
• ARGLIST -> EXPR ARGREST | e
• ARGREST -> , EXPR ARGREST | e
• IF -> if EXPR BLOCK ELSE
• ELSE -> else BLOCK | e
• LET -> let identifier = EXPR ; | let identifier = CALL ;
• READ -> read identifier ;
• RETURN -> return EXPR ;
• WHILE -> while EXPR BLOCK
• WRITE -> write EXPR ;
• EXPR -> number | identifier | ( EXPR ) | ( UNOP EXPR ) | ( BINOP EXPR EXPR )
• BINOP -> + | - | * | / | % | & | | | < | > | <= | >= | == | !=
• UNOP -> ~ | !

This description describes the syntax (how to write valid programs) of SL, but not the semantics (what a syntactically valid program actually does). We'll get to the semantics in the next assignment, but drawing on your knowledge of Java, the semantics of SL should be fairly obvious just from the grammar.

Your first task is to answer the following problems based on the grammar above. Put your answers in a text file called proj3-grammar.txt . Just one write-up per group is needed. See the note at the very end of this document concerning the header information you need at the top of this file.

1. Write the grammatically correct SL expressions for the following Java arithmetic expressions (watch your operator precedence for some of these!), and also give their final values. You may want to run it through Java to double-check. Assume that a==1, b==2, c==3, d==4, e==0.
   • 1+2+3+4+5
   • 1*(2+3)-4/5
   • -1+2+-3+4+-5
   • a && (!b || c) || !d && e
   • (a==1 && b==-2 || c!=-3) && !d!=!-e
   • a>=1 || b<=c || d>3 || e%5<4

2. Mr. Bar is confused about the difference between Java grammar and SL grammar. Locate everything that is wrong with his not-quite-SL program below, and for each: 1) indicate which SL grammar rule(s) it disobeys; and 2) rewrite it correctly in SL.
   {
   
   function A(a,b) {
   
   if (a < b)
   
   return B(a-1)
   else
   
   break;
   return 0;
   }
   main {
   
   if (B(5)) {
   
   write B(7);
   return;
   }
   }
   function B(a) {
   
   n = - A(a,3) + 2 * A(a,4);
   return n+6;
   }
   }

   Extra credit (1 pt): What is the final output of this program?

3. (Note: This question is actually a parser question, not a grammar question, so you may want to wait until you're writing the parser to answer this one.)
   • A) As we've noted before, a parser is really just a push-down automaton (DPDA). Briefly demonstrate this with regard to the top-down parser that you are now writing by answering these questions. In the parser:
     • What corresponds to the DPDA states?
     • What corresponds to the push-down store?
     • What corresponds to the input tape?
     • What is in each square of the input tape?
   • B) The one lexeme lookahead feature that we use in our parser may strike you as being bogus, because in DPDAs, you can't push an already read input back into the input stream. Explain briefly why this is actually acceptable; i.e., explain how you would simulate this lookahead feature using a DPDA.

2. Patching Up the Lexer

Things to do to the lexer (in addition to whatever else you might find necessary):

1. Remove declare as a keyword.
2. Add call and function, which will allow you to make function calls.
3. Add let, which will allow you to make variable assignments.
4. Add "&", which will be a logical and operator (like && in C).
5. Add "|", which will be a logical or operator (like || in C).
6. Add "!", which will be the logical not operator.
7. Add "~", which is the unary negation operator.
8. Add a method called void putBack(Token t), which puts the token t back into the stream, so to speak. Notice that this backing-up capability is only one token deep; in other words, if you do multiple putBack() calls, only the most recent one matters. For example:
   lex.putBack(t1);
   lex.putBack(t2);
   lex.getToken(); // == t2
   lex.getToken(); // != t1; it's the next unread token from the stream

3. Setting Up the Parser

First, you must create a Parser class, the main class for this assignment:

public class Parser {
public Parser(InputStream s) { /* to be filled in by you */ }
public void parse() { /* t.b.f.i.b.y. */ }
public void print() { /* t.b.f.i.b.y. */ }
public void interpret() { /* t.b.f.i.b.y. */ }
private ParseNode tree;
private SymbolTable symtbl;
/* add other stuff as you need them */
}

print() simply prints out the parse tree in a readable text format. The tree should be printed out using pre-order, depth-first traversal. (The criterion for readability is that someone who is familiar with this project -- e.g., a TA -- can stare at the output and deduce what your printout means without having to ask you for an explanation.) This method will also, without a doubt, be your friend in debugging.

interpret() begins executing the parse tree; it assumes that tree is fully parsed and symtbl is filled in properly. You will concern yourself with interpret() in the next assignment.

So far so good. The only tricky part seems to be parse(). Before we get into that, however, we need to look at this mysterious class called ParseNode. Notice that tree is of that type, so perhaps you have already guessed that ParseNode is what the parse tree is made of; they are in fact the nodes of the parse tree, each containing pointers to children nodes. Let's look at it a bit more closely:

public abstract class ParseNode implements GrammarTypes {
public ParseNode() {...}
public int numChildren() {...}
public ParseNode getChild(int i) {...}
public void addChild(ParseNode node) {...}
public abstract int getType();
public abstract ParseNode interpret(SymbolTable st) throws
InterpretException, BreakException, ReturnException;
public abstract void print(PrintStream ps);
/* define other stuff as you need them */
}

public interface GrammarTypes {
public final static int G_NOP = 0;
public final static int G_NUMBER = 1;
public final static int G_IDENT = 2;
public final static int G_PROGRAM = 3;
public final static int G_FUNCTION = 4;
public final static int G_BLOCK = 5;
public final static int G_BREAK = 6;
public final static int G_CALL = 7;
public final static int G_IF = 8;
public final static int G_LET = 9;
public final static int G_READ = 10;
public final static int G_RETURN = 11;
public final static int G_WHILE = 12;
public final static int G_WRITE = 13;
public final static int G_EXPR = 14;
// you may NOT modify this interface!!!
}

Notice that you'll need some data structure to store an ordered list of children. (Please note that it must be ordered; in other words, something like a Vector.) Once you have this, you can implement the necessary subclasses of ParseNode. There is a subclass of each node type defined in GrammarTypes, for a total of 15 subclasses (each in a separate file, of course):

• public class SL_NopNode extends ParseNode {...}
• public class SL_NumberNode extends ParseNode {...}
• public class SL_IdentNode extends ParseNode {...}
• public class SL_ProgramNode extends ParseNode {...}
• public class SL_FunctionNode extends ParseNode {...}
• public class SL_BlockNode extends ParseNode {...}
• public class SL_BreakNode extends ParseNode {...}
• public class SL_CallNode extends ParseNode {...}
• public class SL_IfNode extends ParseNode {...}
• public class SL_LetNode extends ParseNode {...}
• public class SL_ReadNode extends ParseNode {...}
• public class SL_ReturnNode extends ParseNode {...}
• public class SL_WhileNode extends ParseNode {...}
• public class SL_WriteNode extends ParseNode {...}
• public class SL_ExprNode extends ParseNode {...}

public class SL_NopNode extends ParseNode {

public int getType() { return G_NOP; }
public ParseNode interpret(SymbolTable st) throws
InterpretException, BreakException, ReturnException
{
return null; // to be implemented correctly in project #4
}
}

• To SL_NumberNode, add a constructor that allows you to set what number or value this node represents. Also add a getValue() method which returns the number. (Remember that the value is an arbitrary precision integer, which can be implemented using the BigInteger class in java.math.)
• To SL_IdentNode, add a constructor that allows you to initialize the node with a string name. Also add a String getName() method.
• To SL_FunctionNode, add several methods. int numArgs() should return the number of arguments this function accepts. String getArgName(i) should return the name of the ith parameter. ParseNode getBody() should return the body block of the function.
• To SL_ExprNode, add a constructor that allows you to initialize the node with any operator type (both binary and unary allowed). Also add an int getOperator() method.

Another example is SL_FunctionNode, which has 1+n+1 children. The first is of type SL_IdentNode and represents the name of the function; next are n SL_IdentNodes, each naming the parameters for the function, in order; finally, the last child is of type SL_BlockNode, and it represents the body of the function. You should work out such schematics for the 13 remaining node types. For the order of the children, keep it in the same order that you would write them in SL code. The above two examples should serve as good guides.

One last word about all these classes. As noted, you are allowed to add more stuff to all of them (except GrammarTypes). However, be sure that those things you add are all private, so that only the publicly published methods are used outside that class. Say, for example, that you add a method public int foo() to SL_WhileNode, then you make calls to foo() from inside your parser. Well, if someone else then takes your parser and tries to run it on his or her own version of SL_WhileNode, it won't work anymore, because that version of SL_WhileNode doesn't define foo(), which is not in the specs. This is precisely what we will be doing to code to grade it: after we take it for a quick spin to make sure your code all works together, we'll then replace your SL_*.java with our versions of them that implement all the interpreter functions. Then we'll run it again, and if you followed the specs correctly, it should actually not only parse but also execute SL programs.

4. From Grammar to Code

FOR -> for IDENT = EXPR to EXPR do BLOCK

parse_FOR() {

match_for();   // match the keyword "for"
parse_IDENT(); // match an identifier
match_assn();  // match the assignment symbol
parse_EXPR();  // match an expression
match_to();    // match the keyword "to"
parse_EXPR();  // match an expression
match_do();    // match the keyword "do"
parse_BLOCK(); // match a block
}

As written above, this parser won't be very useful. Why? Because it doesn't construct the parse tree as it goes along. So at the end of the parsing, the parser will be able to tell you whether your program is syntactically well-formed, but it won't be able to tell you which grammar rules it used to parse it. This is a lot like the CYK algorithm as demonstrated in section: as you discovered in Homework 4 part III, you have to modify the algorithm slightly to make it possible to keep track of your parse history. In this case, you'll want to build up a tree-like data structure (rooted at the Parser's tree object) as you parse the input.

You'll notice as you're constructing your parse tree that GrammarTypes doesn't define a node type for every possible nonterminal and terminal in the grammar. This is because not all of them are really needed. For example, STATEMENT nodes are not needed, because we can separately instantiate each of the possible types of statements: BREAK, CALL, IF, etc. You should be able to implement SL quite handily with just the 15 types of nodes defined above.

One issue of some concern is that of error detection. If you have a syntactically flawed program, you should output a message that includes the line number and actual line text, and as useful a diagnosis as possible. You should use exceptions wisely for this purpose (see below for more details on exceptions). Of course, a lexically flawed program should behave as before: the lexer should take care of lexical errors. You should halt execution after the first lexical or syntactic error.

One last note: consider a case where you have an arbitrarily long list of something, like an argument list or a parameter declaration list. Here's an example using a hypothetical grammar for a list of numbers:

LIST = ELEMENT $

ELEMENT = number ELEMENT | e

parse_LIST() {

while (lex.getToken() != '$') { // This is a bug!

parse_ELEMENT();
}
}
parse_ELEMENT() {

match_number();
}

The problem here is that we cannot detect the end of an arbitrarily long list of elements unless we can "peek" ahead one token. You've already seen this happen in your lexer, where you had to peek ahead one character to distinguish between the ">" and ">=" operators. Now you must look ahead by a single token, instead of a single character; but the idea is still the same. This is why we asked you to implement the pushBack() method in the lexer.

5. Loose Ends

However, you must write and use public class ParseException to handle parsing errors. Make sure that your parser handles parsing errors with grace and intelligence. At the very least tell the user where the parsing error occurred. After the parser detects a parsing error, it should halt execution immediately. Finally, you must not throw any exceptions at the main() level.

Next, as with the previous project, you will need to write a front-end main class to be able to test drive your parser. Call it public class Proj3. It should read in an SL source code file from standard input, parse it, and print out the final parse tree using pre-order, depth-first traversal. Nonexistent or inscrutable print output will be penalized.

Your final tally of files to hand in:

• proj3-grammar.txt
• all the *.java files needed for the parser
• all the *.java files needed for the revised lexer

Don't forget that all your files must begin with a header that contains:

• your names
• your group ID
• the project name (Project #3: SL Parser)
• your grader's name (same as your TA for most of you)
• the name of the file