tailieunhanh - Báo cáo khoa học: "Generalized Left-Corner Parsing"

We show how techniques known from generMized LR parsing can be applied to leftcorner parsing. The ~esulting parsing algorithm for context-free grammars has some advantages over generalized LR parsing: the sizes and generation times of the parsers are smaller, the produced output is more compact, and the basic parsing technique can more easily be adapted to arbitrary context-free grammars. The algorithm can be seen as an optimization of algorithms known from existing literature. | Generalized Left-Corner Parsing Mark-Jan Nederhof University of Nijmegen Department of Computer Science Toemooiveld 6525 ED Nijmegen The Netherlands markjan@ Abstract We show how techniques known from generalized LR parsing can be applied to leftcorner parsing. The resulting parsing algorithm for context-free grammars has some advantages over generalized LR parsing the sizes and generation times of the parsers are smaller the produced output is more compact and the basic parsing technique can more easily be adapted to arbitrary context-free grammars. The algorithm can be seen as an optimization of algorithms known from existing literature. A strong advantage of our presentation is that it makes explicit the role of left-corner parsing in these algorithms. Keywords Generalized LR parsing leftcorner parsing chart parsing hidden left recursion. 1 Introduction Generalized LR parsing was first described by Tomita Tomita 1986 Tomita 1987 . It has been regarded as the most efficient parsing technique for context-free grammars. The technique has been adapted to other formalisms than context-free grammars in ỊTomita 1988 . A useful property of generalized LR parsing henceforth abbreviated to GLR parsing is that input is parsed in polynomial time. To be exact if the length of the right side of the longest rule is p and if the length of the input is n then the time complexity is ơ np 1 . Theoretically this may be worse Supported by the Dutch Organization for Scientific Research NWO under grant 00-62-518 than the time complexity of Earley s algorithm Earley 1970 which is ơ n3 . For practical cases in natural language processing however GLR parsing seems to give the best results. The polynomial time complexity is established by using a graph-structured stack which is a generalization of the notion of parse stack in which pointers are used to connect stack elements. If nondeterminism occurs then the search paths are investigated simultaneously where the initial part of