Paper: LR Parsers For Natural Languages

ACL ID P84-1073
Title LR Parsers For Natural Languages
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1984

MLR, an extended LR parser, is introduced, and its application to natural language parsing is discussed. An LR parser is a ~;hift-reduce parser which is doterministically guided by a parsing table. A parsing table can be obtained automatically from a context- free phrase structure grammar. LR parsers cannot manage antl)iguous grammars such as natural language grammars, because their I)arsing tables would have multiply-defined entries, which precludes deterministic parsing. MLR, however, can handle mulliply-defined entries, using a dynamic programnting method. When an input sentence is ambiguous, the MI.R parser produces all possible parse trees witftoul parsing any part of the input sentenc:e more than once in the same way, despite the fact that the parser does not maintain a chart as in c...