LR parsers for natural languages

Citations Over TimeTop 10% of 1984 papers

Abstract

MLR, an extended LR parser, is introduced, and its application to natural language parsing is discussed. An LR parser is a shift-reduce parser which is deterministically guided by a parsing table. A parsing table can be obtained automatically from a context-free phrase structure grammar. LR parsers cannot manage ambiguous grammars such as natural language grammars, because their parsing tables would have multiply-defined entries, which precludes deterministic parsing. MLR, however, can handle multiply-defined entries, using a dynamic programming method. When an input sentence is ambiguous, the MLR parser produces all possible parse trees without parsing any part of the input sentence more than once in the same way, despite the fact that the parser does not maintain a chart as in chart parsing. Our method also provides an elegant solution to the problem of multi-part-of-speech words such as "that". The MLR parser and its parsing table generator have been implemented at Carnegie-Mellon University.

Related Papers

• → Recursive ascent parsing: from Earley to Marcus(1992)16 cited
• An efficient augmented-context-free parsing algorithm(1987)
• → LR parsers for natural languages(1984)30 cited
• An abstract view of generalized LR parsing(2003)
• → A Kind of Syntax Parsing Algorithm Based on The Predictive Parsing Table(2022)