---------------------------------------------------------------- Assignment 3c. CFG formalisms and parsing algorithms ---------------------------------------------------------------- In this part of the assignment, you will work with the context-free formalisms we discussed in class, including running parsing algorithms by hand, and you'll also answer a few questions. A main goal of this assignment is for you to understand and be able to show the behavior of the algorithms on inputs -- by the end of this assignment you should be able to do that BY MEMORY for recursive-descent and shift-reduce parsing, and for converting from a CFG to an equivalent RTN. (Don't worry too much about memorizing how to convert an RTN to a CFG.) By the end of the assignment you should also be comfortable running the CKY algorithm by hand with the algorithm in front of you (but not from memory). Problem 3.c.1 a-c. Do Allen, Ch 3, Problem 10, parts a, b, and c. Problem 3.c.2 Let G be the following grammar: S -> NP VP NP -> NP PP NP -> DET N VP -> V NP VP -> V PP -> P NP DET -> a | the N -> man | dog | house | telescope | spoon VP -> saw | fed | barked P -> with Show a shift-reduce parse of "the man fed the dog". Don't worry about nondeterminism: just show the configurations along the way to the correct parse. Here are the first few steps to show you the format you should use: 1 2 3 4 5 6 the man fed the dog Operation Stack Input-location start () 1 shift (the) 2 reduce (DET) 2 ...continue! Remember that the top of the stack is on the left of the list. Problem 3.c.3 (i) Show a recursive-descent (top-down) parse of the same sentence. Here are the first few steps to show you the format you should use: Operation Stack Input-location start (S) 1 expand (NP VP) 1 ...continue! (ii) If you've got multiple rules that a nonterminal can expand to, which rule you try first can matter in a top-down parse. Suppose that the parser always chose to try the rule that appeared first in the grammar. What would happen when it went to continue in (i), above? What is the general description of rules that cause this problem? (iii) Why is this not a problem for bottom-up parsers? Problem 3.c.4 Let G be the following grammar: S -> AB S -> AS A -> BB A -> BA B -> AA B -> b A -> a Run the CKY algorithm on the input string "abbaba", showing the resulting table. (Drawing the chart is optional, but might help you keep track.) Is the string in L(G)?

Return to the course home page.