Parsing (continued)

• In practice, top down and bottom up strategies are combined.
  • Notice one danger in top down parsing; you might keep generating rules with nonterminals, going deeper and deeper, never getting to rules that handle any of the words. This is called recursion. Here's an example: suppose we have this (very sensible) rule in our grammar:
    NP ® NP PP
    We might use it in top down parsing like this:
    
    
    
    and if we keep trying this rule, we'll never get around to the rules that account for the words in the sentence!
  • Clearly, we want to have some smarter strategies in our parser about what rules to apply. One way we can combine top down and bottom up strategies is to examine the "left corner" of the tree--really the "bottom left corner", where the sentence begins. Then use only grammar rules that handle the left corner of the constituent you're trying to parse, which could also fit in with the top constituent. This "left-corner" parsing strategy alternates top down and bottom up. It isn't described in Jurafsky and Martin, but they do illustrate the notion of a constituent's left corner
    
    
    
    
  • Many other methods have been developed for increasing the efficiency of parsing: the Earley algorithm, which is one variety of "chart parsing", the Tomita algorithm, and algorithms that use various modifications of CFGs,