7.1.1 Going Wrong with Top-down Parsing

Problems with top-down parsing.

Assume that we have the following grammar fragment

and that we want to use it to top-down recognize the string ``vincent died''. Proceeding in a top-down manner, we would first expand to . Next we would check what we can do with the and find the rule . We would therefore expand to . Then we have to find a phrase structure rule to expand or to find a lexical rule to relate vincent to the category . Neither is possible, so we would backtrack checking whether there are any alternative decisions somewhere.

Ignoring the Given Data

So, when recognizing in a top-down manner, we totally ignore what the actual input string looks like. We start from some non-terminal symbol and then use rules to rewrite that symbol. Only when we can't apply any rules anymore, we check whether what we have produced matches with the input string.

Here is part of the trace that we will get when trying to recognize vincent died with the top-down recognizer of the previous section. You can see how Prolog first tries to use the first rule to expand the noun phrase. And only when Prolog realizes that leads into a dead-end does it try the next rule .

   Call: (7) recognize_topdown(s, [vincent, died], []) ?  
   Call: (8) matches([np, vp], [vincent, died], []) ?  
   Call: (9) recognize_topdown(np, [vincent, died], _G579) ?  
   Call: (11) recognize_topdown(det, [vincent, died], _G585) ?  
   Fail: (11) recognize_topdown(det, [vincent, died], _G585) ?  
   Call: (11) recognize_topdown(pn, [vincent, died], _G582) ?  
   Exit: (11) recognize_topdown(pn, [vincent, died], [died]) ?  
   Exit: (9) recognize_topdown(np, [vincent, died], [died]) ?  
   Call: (10) recognize_topdown(vp, [died], _G582) ?  
   .
   .
   .