tailieunhanh - Báo cáo khoa học: "LR Parsers For Natural Languages"

The recent literature[8] shows that the belief "natural languages are not context-free" is not necessarily true, and there is no reason for us to give up the context-freedom of natural languages. We (to not discuss on this matter further, considering the fact that even if natural languages are not context-free, a fairly comprehensive grammar for a subset of natural language suflicient for practical systems can be written in phrase structure. lhtJ.% our main concern is how to cope with the ambiguity of natural languages, and this concern is addressed in the fallowing section. . | LR Parsers For Natural Languages Masaru Tomita Computer Science Department Carnegie-Mellon University Pittsburgh PA 15213 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. 1 Introduction LR parsers 1 2 have been developed originally for programming language of compilers. An LR parser is a shift-reduce parser which is deterministically guided by a parsing table indicating what action should be taken next. The parsing table can be obtained automatically from a context-free phrase structure grammar using an algorithm first developed by DeRemer 5 6 . We do not describe the algorithm here reffering the render to Chapter 6 in Aho and Ullman 4 The LR parsers have seldom been used for Natural Language Processing probably because 1. It has been thought that natural languages are not context-free whereas LR parsers can deal only with context-free languages. 2. Natural languages are ambiguous while standard LR parsers can not handle ambiguous languages. The recent literature 8 shows that the belief natural languages are not .