Homework 4 Solution set
15-212, Spring 1998
Author: Adam Berger
(aberger@cs.cmu.edu)
Part 1
Not for credit
Part 2
Many of you didn't understand that sometimes, more than one
non-terminal can belong in a box of the chart. What this means is that
once you stick a non-terminal in a box, you're not done! You need to check for
all possible non-terminals which could go in that entry. For example, the
following rules appear in the expression grammar given in the assignment:
E -> idN2
T -> idN2
So if one can generate idN2 from some box, then you need to
stick both E and T in that box. Then, when filling in
subsequent boxes, consider both E and T as elements of the
box.
Anyway, here's the filled-in charts, with null entries left blank:
(id+id)*id):
|------|
| ( |
|------|------|
| | id |
|------|------|------|
| | | + |
|------|------|------|------|
| | E | N1 | id |
|------|------|------|------|------|
| E,F | N3 | | N3 | ) |
|------|------|------|------|------|------|
| | | | | | * |
|------|------|------|------|------|------|------|
| E,T | | | | | N2 | id |
|------|------|------|------|------|------|------|------|
| N3 | | | | | | N3 | ) |
|------|------|------|------|------|------|------|------|
As a sanity check, you can confirm that the non-terminal N3
can indeed generate the string (id + id)*id). From inspecting the
grammar, it's clear that the non-terminal N3 has the
"meaning" of an expression with a pending right parenthesis, which exactly fits
this expression.
(id)+(id*id):
|------|
| ( |
|------|------|
| | id |
|------|------|------|
| E,F | N3 | ) |
|------|------|------|------|
| | | | + |
|------|------|------|------|------|
| | | | | ( |
|------|------|------|------|------|------|
| | | | | | id |
|------|------|------|------|------|------|------|
| | | | | | | * |
|------|------|------|------|------|------|------|------|
| | | | | | E,T | N2 | id |
|------|------|------|------|------|------|------|------|------|
| E | | | N1 | E,F | N3 | | N3 | ) |
|------|------|------|------|------|------|------|------|------|
Notice that several boxes have multiple entries. In row 9, column 5, the entry
F is what makes the algorithm succeed---if you had stuck only an E in this box,
the algorithm would have failed.
Part 3
When recording a non-null entry in the table, link it to the two parent entries
that generated it. You can do this by storing "back pointers" from each entry
to its two parents entries. Upon successful completion, the parse tree is
rooted at the start symbol in the lower righthand corner. So you can just read
off the parse tree by starting at the S in the lower righthand corner, and
following the backpointers.
Many of you proposed a two-phase process: first, apply the regular CYK
algorithm; second, extract a parse tree from the filled-in chart. This works,
but isn't as elegant. Extracting a parse tree in the second phase requires
finding the parent entries for each entry in the chart by searching down and
across the appropriate row/column. But when you were filling in each entry in
the first phase, you already had to perform this search! In other words, you're
performing redundant computation.
End of Solutions