LR Parsers For Natural Languages

LR Pa rse rs 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 ~;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 chart par~ing. Our method also prnvkles 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[I, 2] have been developed originally for programming language of compilers. An LR parser is a shift- reduce parser which is detenninistically guided by a par.~it~g 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 UIIman [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 ambi~juous 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 context.free 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. 2 LR parsers and Ambiguous Grammars If a given grammar is ambiguous? we cannot have a parsing table in which ~ve~y entry is uniquely defined; at lea~t one entry of it~ parsing table is inulliply defined. It has been thought that, for LR pa~sers, nndtiple entries are fatal because they make deterministic parsing no longer po~$ible. Aho et. al. [3] and Shieber[121 coped with this ambiguity problem by statically 3 selecting one desired action out of multiple actions, and thus converting n=ulliply-defined entries into uniquely-defined ones.With this approach, every input sentence has no more than one parse tree. This fact is desirable for progralnming languages. For natural languages, however, it is …

Content truncated to 500 words