Programming Assignment: 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.

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 by:

• 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.

Setting Up the Parser

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. */ }
private ParseNode tree;
/* 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.

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 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'll need some data structure to store an ordered list of children. 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; }
}

• 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.

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 exactly like the CYK algorithm: it's a language recognizer, and nothing more. 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 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.

Loose Ends

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 Proj3.java. 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

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

• your names
• your group ID
• the project name (SL Parser)
• your grader's name
• the name of the file