Project #3 Notes, Fall 2006

This page is an accumulation of (we hope) helpful notes, hints, etc., that might be useful to you in doing Project #3.

1. Various Corrections and Clarifications
2. Postponed error checks
3. Debugging a grammar
4. Assorted Tips
5. Assorted Questions and Answers

Various Corrections and Clarifications

1. A plain expression is an expression list with one element. If it is followed by a comma, it denotes a tuple whose one element is the value of that expression. Any expression list may be used as a a simple statement. It must be parenthesized if empty (although such a statement is useless, it is possible).
2. The power operator (**) should have strictly higher precedence than the unary operators, so that -x**y is interpreted as -(x**y).

Postponed error checks

There are several erroneous cases that could be handled either in the parser or in static semantics. To allow us to use test cases properly, we have to decide how to handle them. Detection of the following errors can wait until static semantic analysis. You are free to check for them during parsing, but be warned: we are postponing them because they present various difficulties for our grammar tools and yet are easy to handle during static semantics.

1. Misplaced break, continue, and return: These statements may occur only in certain contexts (the first two in loops, the last in functions). However, enforcing this in the parser requires either duplicating a bunch of grammar rules or using various kludges involving global variables or the like. So for our purposes, just allow these three statements anywhere that a simple statement is allowed.
2. Class method definitions: Likewise, class methods may occur only immediately within classes, but let's allow them anywhere, and catch the error in the static semantics phase. On the other hand, just to be inconsistent, classes may only appear at the outer level of the program. This is easy to enforce in the parser, so do forbid class definitions except at the outer level.
3. Left-hand sides of assignments: Allow any expression as the left side of an assignment. It will be easy enough to filter out the bad ones in semantic analysis, and it is difficult to get things right in the parser.

Debugging a Grammar

Be sure that your finished parser does not report unresolved shift/reduce or reduce/reduce errors. These generally mean you've done something wrong.

With the -v switch, bison and jbison produce a table (in a file with suffix .output) showing the LALR(1) machine that they produce. You can use this as shown in lecture to help find some problems.

If you include the command %debug in your .y file (as it is in the Java skeleton), then you can induce your parser to show the derivation it performs for your program by setting the yydebug variable in your parser to 1 (this is a static variable in C++ and an instance variable of the parser in Java). I'd suggest setting it in the main program. The classiest way is to provide a parser method to do so, and to call it from ParseTest in response to an appropriate command-line switch, but frankly, I often just run the parser under the debugger and set it from there.

Assorted Tips

1. If you attempt to use list-of-expression as the thing that goes to the left of in in a for statement, you'll find that you get conflicts. To fix them, make the construct after "for" be a list of higher-precedence expressions—a list of primaries (variables, bracketed constructs, selections, indexing, etc.) works, for example, and allows everything that needs to be allowed.

Assorted Questions and Answers

Q: How should we treat "elif"? It isn't in the spec.

A: There is no construct for it, because elif is the same as else if:

if FOO:
   S1
elif BAR:
   S2
else:
   S3

if FOO:
   S1
else:
   if BAR:
      S2
   else:
      S3

Q: Are we free to allow (or disallow) statements such as:

 x *= y *= 2

A: Augmented assignments are STATEMENTS, not expressions, and may not be used as expressions. Thus the statement above is illegal.

Q: In dictionaries can keys and values only be expressions? If not what syntactic categories can they be?

A: They may only be expressions.

[CS164 Homework]    [CS164 Home Page]