Project #1 Notes, Spring 2010

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

  1. Various Changes from the Original Handouts and Skeletons
  2. Debugging a grammar
  3. Assorted Questions and Answers

Various Changes from the Original Handouts and Skeletons

  1. We added syntax for concatenation of string literals (which we had previously overlooked), replacing the syntax for stringliteral with: 
    stringliteralpiece ::=
              [stringprefix](shortstring | longstring) 
              | rawstringprefix(shortrawstring | longrawstring)
   
stringliteral ::=
             stringliteralpiece
             | stringliteral stringliteralpiece
  2. Added clarification: The print and println AST operators translate the print command with and without a trailing comma, respectively. The optional first expression operand denotes the file written to (denoted in Python with >>file).

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

We have set up apyc command in the skeleton to allow a -dp switch, which will cause the parser to output information about the parse it is performing. This information includes the shifts and reductions it performs and the tokens it gets from the lexer.

It's also possible to test the lexer alone. Adding the declaration 

    %option debug
for flex before the first "%%" will cause the lexer to output each rule that it matches and value that it returns. Unfortunately, the returned syntactic categories are integers, which are, perhaps, not the most useful things to look at, and the information returned does not include the accompanying lexemes themselves.

So a better a approach to testing the lexer is to set up a dummy version of the parser, containing %term declarations for all tokens you expect from the lexer (the lexer needs the parser's values for these anyway): 

   %term IDENT STRING_LITERAL INDENT ...
   %term "and" "or" "if" ...
   %term "==" "!=" ...
and a dummy grammar that uses all of them: 
   prog : /* EMPTY */
        | prog token      { System.out.printf ("Token value: %s%n", $2); }
        ;

   token : IDENT | STRING_LITERAL | INDENT | ...
        ;

Is the welter of resulting output hard to read? Consider writing a tiny program to format it better!

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
is equivalent to 
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.

Q: The Python syntax for subscription allows a list as the subscript, but the AST description says it must be a (single) expression. Does that mean we reject lists as subscripts?

A: No. There are, in fact, a number of places in which the AST calls for an Expr and the concrete grammar allows a list. For example, 

      x = 1, 2, 3
      return 1, 2, 3
      for x in 1, 2, 3:
      x = 1,
If you examine the Python manual, you'll see that in all these cases, the lists actually denote tuples. So the three statements above are equivalent to 
      x = (1, 2, 3)
      return (1, 2, 3)
      for x in (1, 2, 3):
      x = (1,)
and therefore you should generate ASTs in which the expression is a tuple.

[CS164 Homework]    [CS164 Home Page]

Page was last modified on Fri Feb 26 19:00:04 2010.
Address comments and questions to cs164@eecs.berkeley.edu