tailieunhanh - Báo cáo khoa học: "Polynomial Time and Space Shift-Reduce Parsing of Arbitrary Context-free Grammars.*"

We introduce an algorithm for designing a predictive left to right shift-reduce non-deterministic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. The performance of the resulting parser is formally proven to be superior to Earley's parser (1970). The technique employed consists in constructing before run-time a parsing table that encodes a nondeterministic machine in the which the predictive behavior has been compiled out. . | Polynomial Time and space Shift-Reduce Parsing of Arbitrary Context-free Grammars. Yves Schabes Dept of Computer Information Science University of Pennsylvania Philadelphia PA 19104-6389 USA e-mail schabes@ Abstract We introduce an algorithm for designing a predictive left to right shift-reduce non-deterministic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. The performance of the resulting parser is formally proven to be superior to Earley s parser 1970 . The technique employed consists in constructing before run-time a parsing table that encodes a non-deterministic machine in the which the predictive behavior has been compiled out. At run time the machine is driven in pseudo-parallel with the help of a chart. The recognizer behaves in the worst case in ớ G 2n3 -time and ỡ ƠỊn2 -space. However in practice it is always superior to Earley s parser since the prediction steps have been compiled before runtime. Finally we explain how other more efficient variants of the basic parser can be obtained by deter-minizing portions of the basic non-deterministic pushdown machine while still using the same pseudoparallel driver. 1 Introduction Predictive bottom-up parsers Earley 1968 Earley 1970 Graham et al. 1980 are often used for natural language processing because of thefr superior average performance compared to purely bottom-up parsers We are extremely indebted to Fernando Pereừa and Stuart Shieber for providing valuable technical comments during dis cussions about earlier versions of tins algorithm. We are also grateful to Aravind Joshi for his support of this research. We also thank Robert Frank. AU remaining errors are the author s responsibility alone. This research was partially funded by ARO grant DAAL03-89-C0031PRI and DARPA grant N00014-9O-J-1863. such as CKY-style parsers Kasami 1965 Younger 1967 . Their practical superiority is mainly .