CSE 401 Wi09 Homework 2 -
Grammars and LR Parsers
Due: Friday, January 30 at the beginning of class. We suggest you show your
work to help us award partial credit if appropriate, and for TA sanity.
You should do this assignment individually.
- Give an unambiguous grammar for each of the following languages. (Hint:
One way of verifying that a grammar is unambiguous is to run it through a
LALR parser generator like Yacc, Bison, or CUP and get no conflicts. You
are not required to do this, however.)
- Statement blocks in Pascal or ML where the semicolons separate the
statements:
{ statement ; { statement ; statement } ; statement }
- Statement blocks in C or Java where the semicolons terminate the
statements:
{ expression ; { expression ; expression ; } expression ; }
- Balanced parentheses and square brackets. Example:
([[](()[()][])])[]
- Given the following grammar:
S ::= ( L ) | x
L ::= L , S | S
- Give a left-most derivation of (x, (x, x)) .
- Give a right-most derivation of (x, (x, x)) .
- Show the steps that a shift-reduce parser goes through when it parses
(x, x, x). That is, show the contents of the stack and remaining input
at each step.
- Suppose we replace the left-recursive production L::=L,S with a right-recursive
one L::=S,L. What general effect does this have on the depth of the
stack during
a shift-reduce parse? (You might work through the parse of (x, x, x)
again to see what changes.)
- The following is a grammar that generates epithets (E). An epithet is
a description (D). A description can be either a trait (T) or a simile
(S).
Similies are of the form "trait like animal" (A).
E ::= D
D ::= T | S
S ::= T like A
T ::= quick | strong
A ::= bunny | ox
- Construct the LR(0) state diagram and parse table for this grammar.
- Calculate FIRST, FOLLOW, and nullable for each non-terminal.
- Construct the SLR parse table.
- Is this grammar LR(0)? SLR?
- (Appel) Write a grammar for English sentences using the words
time arrow banana flies like a an the fruit
and the semicolon. Be sure to include all the senses (noun, verb, etc.) of
each word. Then show that this grammar is ambiguous by exhibiting more than
one parse tree for the sentence "time
flies like an arrow; fruit flies like a banana".)
- Strongly recommended, but not required, and not to be turned in. Very good
thought exercise before doing phase B of the project.
Consider the following MiniJava statement:
while (x < 3+4*5) {
System.out.println(x);
y = new C().test(a,b,c);
}
- Draw the concrete syntax tree for this statement. Use the MiniJava grammar
embedded in the
Parser/minijava.cup
file.
- Draw the abstract syntax tree for this statement, labelling each AST node
with the name of an AST node class from the MiniJava compiler and labelling
each child edge with the name of an instance variable of the parent node’s
class.