Left-corner parsing algorithm for unification grammars
Noriko Tomuro, Steve Lytinen · 1999
Parsing with unification grammars is inefficient due to the expressive power of the grammars. Most unification-based parsing algorithms are extensions of context-free (CF) parsing algorithms, and few have been specially designed for unification-style grammars. We have developed an efficient parsing algorithm for unification grammars which takes full advantage of the expressiveness of the grammar. Our algorithm (called LC) is a variation of Left-corner parsing, and it exhibits significantly improved average-case performance as compared with previous unification-based parsers. Efficiency of our LC algorithm comes from two factors. First is the representation and architecture of LINK. LINK is a syntax-semantics integrated unification-based system which dynamically combines syntax (grammar) and semantics (domain knowledge). And LINK utilizes all available information at any given point during parsing. Second is the expectation-based Left-corner parsing strategy. By utilizing expectations, ...