Paper: Parsing As Tree Traversal

ACL ID C94-1064
Title Parsing As Tree Traversal
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1994

This paper presents a unified approach to parsing, in which top-down, bottom- up and left-corner parsers m:e related to preorder, postorder and inorder tree traversals. It is shown that the sim- plest bottom-up and left-corner parsers are left recursive and must be con- verted using an extended Greibach nor- mal form. With further partial exe- cution, the bottom-up and left-corner parsers collapse togethe~ as in the I]IJP parser of Matsumoto.