Abstract
Various improvements have been made to the Bottom Up Parser in Prolog (BUP for short), such as speed up of processing time, describability for Extraposition Grammars and idioms and so on.
In this paper, we present another speed up method without spoiling these assets. The original BUP has no particular mechanism to choose one production rule deterministically; however, in our method the parser can restrain the nondeterminism by means of an action table and a lookahead. The principle of our methods is based on the correspondence between BUP and the LC(1) parser. The LC(1) parser can deterministically parse sentences which belong to a class of context free language called LC(1). We apply the parsing method for LC(1) to general context free grammars. The nondeterminism caused by the extension can be managed through the backtracking in the same way as the original BUP. We also present an implementation and experimental results from a practical-sized grammar with 560 production rules.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Tanaka,H., Kamiwaki,T., Okumura,M. and Numazaki,H. A Software System LangLAB for Natural Language Processing, Proc. LPC'86, pp.5–12, 1986.
Matsumoto, Y., et al., BUP — A Bottom-Up Parser Embedded in Prolog, New Generation Computing, Vol.1, No.2, pp.145–158, 1983.
Konno, S. and Tanaka, H., Processing Left-extraposition in Bottom Up Parsing System, Computer Software, Vol.3, No.2, pp.19–29, 1986.
Kamiwaki,T. and Tanka,H., Idiom Handling by TRIE Structure Dictionary, Proc. of LPC'85, pp.329–340, 1985.
Tokunaga, T., Iwayama, M., Kamiwaki, T. and Tanaka, H., Lang LAB: A Natural Language Analysis System, Trans. Inf. Proc. Soc. Japan, Vol.29, No.7, pp.703–771, 1988.
Tomita, M., An Efficient Augmented-Context-Free Parsing Algorithm, Am.J.Comput. Linguist., Vol.13, No.1–2, pp.31–46, 1987.
Pereirra,F.C.N., Extraposition Grammars, Am.J.Comput. Linguist.
Aho,A.V. and Ullman,J.D., The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing, Prentice-Hall, pp.362–367, 1972.
Sugimura,R., et al., Comparison of Logic Programming based Natural Language Parsing Systems, Preprints Work. Gr.for NL, IPSJ, 57-2,1986.
Matsumoto, Y. and Sugimura, R., SAX: A Parsing System based on Logic Programming Languages, Computer Software, Vol.3, No.4, pp.4–11, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tamura, N., Numazaki, H., Tanaka, H. (1991). Table-driven Bottom Up Parser in Prolog. In: Furukawa, K., Tanaka, H., Fujisaki, T. (eds) Logic Programming '89. LP 1989. Lecture Notes in Computer Science, vol 485. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-53919-0_10
Download citation
DOI: https://doi.org/10.1007/3-540-53919-0_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53919-3
Online ISBN: 978-3-540-46398-6
eBook Packages: Springer Book Archive