Parsing as Tree Traversal

1994/07/29 by Dale Gerdemann, Gerdemann, Dale
Computer Science · #Natural Language Processing Techniques #cmp-lg #cs.CL

paper · pdf · doi:10.48550/arxiv.cmp-lg/9407027

COLING 94 paper, Postscript, compressed and uuencoded

arxiv created 1994/07/29 · arxiv updated 2009/11/30

Abstract

This paper presents a unified approach to parsing, in which top-down, bottom-up and left-corner parsers are related to preorder, postorder and inorder tree traversals. It is shown that the simplest bottom-up and left-corner parsers are left recursive and must be converted using an extended Greibach normal form. With further partial execution, the bottom-up and left-corner parsers collapse together as in the BUP parser of Matsumoto.

Related

• Tabular Parsing
• Tree compression using string grammars
• Efficient probabilistic top-down and left-corner parsing
• A Unifying Theory of Transition-based and Sequence Labeling Parsing
• Parsing as Reduction