Parsing as Tree Traversal

PARSING AS TREE TRAVERSAL Dale Gerdemann* Seminar ffir Sprachwissenschaft, Universiti t T bingen t ABSTRACT 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. 1 INTRODUCTION In this paper, I present a unified ap- proach to parsing, in which top-down, bottom-up and left-corner parsers are related to preorder, postorder and in- order tree traversals. To some extent, this connection is already clear since for each parsing strategy the nodes of the parse tree are constructed accord- ing to the corresponding tree traversal. It is somewhat trickier though, to ac- tually use a tree traversa.l program as a parser since the resulting pa.rser may be left recursive. This left recursion can *The research presented in this paper was partially sponsored by Teilprojekt Bd "Con- straints on Grammar for Efficient Generation" of the Sonderforschungsbereich 340 of the Deutsche Forschungsgemeinschaft. I wouhl also like to thank Guido Minnen and Dieter Martini for helpflfl comments. All mistakes are of course my own. ?KI. Wilhelmstr. 113, D-72074 T(ibingen, Germany, dg@sfs.nphil.uni-tuebingen.de. be eliminated, however, by employing a version of Greibach Normal Form which is extended to handle argument instan- tiations in definite clause grammars. The resulting parsers resemble the standard Prolog versions of versions of such parsers. One can then go one step further and partially execute the parser with respect to a particular grammar--- as is normally done with definite clause gra,,nn~a,'s (Per(,ir~ ~ Warren [JO]). a surprising result of this partial execu- tion is l.ha.t the bottom-up and left- corner parsers become identical when they are 1)oth partially executed. This may explain why the BUP parser of ~/lil.tSllll]OtO eta]. [6] [71 was ,'eferre.d tO as a bottona-u I) parser even though it clearly follows a left-corner strategy. TREE TRAVERSAL PRO G RAM S Following O'Keefe [8], we can imple- ment i)reorder, postorder and inorder tree tra.versals as I)CCs, which will then 1)e converted directly into top-down ])otl.om-u 1) and heft-corner l)arsers, re- spectively. The general schema is: x ._o r d e r(']'t'ee) --* (x_ordered node labels in Tree). Note tha.t in this case, since we are most likely to call x_order with the Tree va.riable instantiated, we are us- ing the DCG in generation mode rather tha.n as a parser. When used as a parser 396 on the stringlS , the procedure will re- turn all trees whose x_order traw~rsal produces S. The three, instantiations of this procedure are as ['ollows: Z preorder traversal pre(empty) --> []. pre(node(Mother,Left,Right)) --> [Mother], pre(Left), pre(Right). postorder traversal post(empty) --> []. post(node(Mother,Left,Right)) --> post(Left), post(Right), [Mother]. inorder traversal in(empty) --> []. in(node(Mother,Left,Right)) --> in(Left), [Mother], in(Right). 2.1 DIRECT ENCODING OF PARSING STRATEGIES Analogous to these three …

Content truncated to 500 words