Masaru Tomita
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.
- Aho, A. V. and Ullman, J. D. The Theory of Parsing, Translation and Compiling. Prentice-Hall, Englewood Cliffs, N. J., 1972. Google Scholar
Digital Library
- Aho, A. V. and Johnson, S. C. LR parsing. Computing Surveys 6: 2: 99--124, 1974. Google ScholarDigital Library
- Aho, A. V., Johnson, S. C. and Ullman, J. D. Deterministic parsing of ambiguous grammars. Comm. ACM 18: 8: 441--452, 1975. Google ScholarDigital Library
- Aho, A. V. and Ullman, J. D. Principles of Compiler Design. Addison Wesley, 1977. Google ScholarDigital Library
- Deremer, F. L. Practical Translators for LR(k) Languages. PhD thesis, MIT, 1969.Google Scholar
- DeRemer, F. L. Simple LR(k) grammars. Comm. ACM 14:7: 453--460, 1971. Google ScholarDigital Library
- Gazdar, G. Phrase Structure Grammar. D. Reidel, 1982, pages 131--186.Google ScholarCross Ref
- Gazdar, G. Phrase Structure Grammars and Natural Language. Proceedings of the Eighth International Joint Conference on Artificial Intelligence v. 1, August, 1983.Google ScholarDigital Library
- Inoue, K. and Fujiwara, F. On LLC(k) Parsing Method of LR(k) Grammars. Journal of Information Processing vol. 6(no. 4): pp. 206--217, 1983.Google Scholar
- Kaplan, R. M. A general syntactic processor. Algorithmics Press, New York, 1973, pages 193--241.Google Scholar
- Kay, M. The MIND system. Algorithmics Press, New York, 1973, pages 155--188.Google Scholar
- Shieber, S. M. Sentence Disambiguation by a Shift-Reduce Parsing Technique. Proceedings of the Eighth International Joint Conference on Artificial Intelligence v. 2, August, 1983.Google ScholarDigital Library
- LR parsers for natural languages
Recommendations
On different LL and LR parsers used in LLLR parsing
The LLLR parser can be constructed for any LR grammar.The LLLR parser produces the left parse of the input string without backtracking.The canonical LL or the LALL parser can be used as the backbone parser.Small canonical or LALR parsers are used for LL ...
LR(0) grammars generated by LR(0) parsers
Let be an LR (0) parser of a given LR (0) grammar G. Generally, does not only parse the words generated by G but also the words of some other LR (0) grammars different from G . In this paper we shall define a class of LR (0) parsers and ...
Comments