John went to the store.

• In the illusration, circle the part of the tree that applies the rule VP -> VP PP.

We can cover this 'corpus' completely with the following CFG:

• Using just the rules in this section, generate a sentence which is not already in our toy corpus and draw the parse tree.

What is parsing?

• What is the point of parsing sentences?

• What type of structure does parsing typically produce?

Start with an 'S' rule.

• Shown here is the first rule on the stack in a top-down parser. The sentence is '[0]Wow[1]', where [0] and [1] mark places between words in the sentence. What does the dot next to Excl mean?

• What does the 0 in the 'index' column mean?

Keep pushing rules that match the RHS of the item on top of the stack until you hit a word in your sentence.

• What does the [0]wow[1] in the 'members' column of entry A indicate?

• What does the 'OK' in the status column of entry A indicate?

• Where did entry A come from?

When you've found a match, keep the entry in a table (marked in red in the illustration) and pop.

• What does the 'A' in the members column of entry B indicate?

• What does the dot at the end of 'Excl' indicate?

The resulting links between successful table entries gives you your tree.

• Here is the parse tree resulting from a top-down parse. What do the circles 'A' and 'B' indicate?

What to do when you don't find a match.

• What do we do when we find that a rule we're hypothesizing during a top-down parse doesn't work out?

• To avoid infinite loops, what must we do before pushing a rule hypothesis on the stack?

• Why do we have to check the table before pushing new rule hypotheses onto the stack?

• Why is it important to keep track of what token-index we've tested a given rule for?

A trivial example: 'Wow.'

• Write a rule to accomodate 'doh'.

A less trivial example: 'Jesus wept.'

• In the illustration, what has the parser just finished doing?

• Why didn't we just skip over the rules in entries A and B without testing them?

• What does the dot next to VP in 'S -> NP [dot] VP' at the bottom of the stack indicate? What does the 'D' in the 'members' column indicate?

• What will be the parser do next?

Top-down parsing

• By convention, which category do you always start with when parsing top-down?

• Say we're using our 'John and Mary' toy grammar, and at the top of the stack is the rule S -> [dot]NP VP. Which rules are we going to be considering for a 'push'?

• Say we're parsing 'John thought Mary was green.'. Name a rule which would apply here which contains a terminal.

'Wow.', revisited.

• Illustrated is a bottom-up parse table for the sentence '[0]Wow[1]'.Why is there only one table entry (1 row & 1 column) in the illustration?

• Which of the two rules in the box did we write first? Why?

'Jesus wept.', revisited.

• Why does our bottom-up parse table here have two rows and two columns?

• How many rows and columns would be needed for a three-word sentence?

• Which range of indexes does the cell on top cover?

• Draw the parse tree that results from this table.

Bottom-up parsing

• What kinds of rules do we start with in 'bottom-up' parsing?

Remarks

• Fill in the blanks:Our parsing procedure is an automated ________ of the _________ defined by the rules of our grammar.

• What can add to the complexity of the parsing space?

• What can we do to increase the efficiency of the parsing procedure?

• What is the significance of the sentence:'The boat floated down the river sank?'. What is this kind of sentence evidence of?