Left Corner Parsers

Left corner parsing improves upon both the recursive descent and the shift reduce parsers as it combines elements of both. Essentially it is still a bottom up, and hence data-driven, approach to parsing, but it also adds an element of top down prediction.

In order to add this top-down prediction, the term ``left-corner'' is introduced. A nonterminal is a left-corner of another nonterminal if:

• (reflexive case)
• there exists a rule (immediate case)
• there exists such that is left-corner of and is the left-corner of (transitive case)

A left corner parser uses top down look ahead in order to only consider rules whose first nonterminal in the right hand side is a left corner of the phrase being recognised (compared to a shift reduce parser which finds complete right hand sides of rules before reducing the stack using that rule).

This reduces the number of choices the parser has at each point in the operation, and hence implicitly prunes the search space. However, although more efficient than both basic top-down and bottom-up parsing, it still has exponential complexity in the number of words of the sentence.