CSE P 501 16wi Homework 2 - CFGs and LR Parsing

Due: Monday, Jan. 18 by 11 pm. Please use the dropbox linked from the CSE P 501 web page to submit your homework online. You should turn in a single pdf file named hw2_answers.pdf. Scanned copies of hand-written documents are fine if they are legible and easy to read when printed on ordinary size paper, and as long as the total file size is no more than 3 MB or so. Note that a picture of a hand-written solution taken with a phone is very likely to produce a file that is not legible when printed, and unreadable submissions will not be graded. We suggest you show your work to help us award partial credit if appropriate, and for TA sanity. You should do this assignment individually.

  1. (Aho, Sethi, Ullman) Consider the grammar:

    S ::= aSbS | bSaS | ε

    1. Show that this grammar is ambiguous by constructing two leftmost derivations for the sentence abab.
    2. Show that this grammar is ambiguous by constructing two rightmost derivations for the sentence abab.
    3. Construct the corresponding parse trees for your derivations.

  2. (Aho, Sethi, Ullman) Given the following grammar:

    S ::= ( L ) | x
    L ::= L , S | S

    1. Give a left-most derivation of (x, (x, x)) .
    2. Give a right-most derivation of (x, (x, x)) .
    3. 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.
    4. 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.)

  3. Postponed until hw3 (we did not get far enough in class to use this question).

  4. (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". (Hint: do not go overboard. This is not an exercise in computational linguistics or Natural Language Processing. If you've done "sentence diagrams" in grade school, that's the right level of complexity for the grammar here.)