Deterministic Left to Right Parsing of Tree Adjoining Languages

DETERMINISTIC LEFT TO RIGHT PARSING OF TREE ADJOINING LANGUAGES* Yves Schabes Dept. of Computer & Information Science University of Pennsylvania Philadelphia, PA 19104-6389, USA schabes@linc.cis.upenn.edu K. Vijay-Shanker Dept. of Computer & Information Science University of Delaware Newark, DE 19716, USA vijay@udel.edu Abstract We define a set of deterministic bottom-up left to right parsers which analyze a subset of Tree Adjoining Lan- guages. The LR parsing strategy for Context Free Grammars is extended to Tree Adjoining Grammars (TAGs). We use a machine, called Bottom-up Embed- tied Push Down Automaton (BEPDA), that recognizes in a bottom-up fashion the set of Tree Adjoining Lan- guages (and exactly this se0. Each parser consists of a finite state control that drives the moves of a Bottom-up Embedded Pushdown Automaton. The parsers handle deterministically some context-sensitive Tree Adjoining Languages. In this paper, we informally describe the BEPDA then given a parsing table, we explain the LR parsing algo- rithm. We then show how to construct an LR(0) parsing table (no lookahead). An example of a context-sensitive language recognized deterministically is given. Then, we explain informally the construction of SLR(1) pars- ing tables for BEPDA. We conclude with a discussion of our parsing method and current work. 1 Introduction LR(k) parsers for Context Free Grammars (Knuth, 1965) consist of a finite state control (constructed given a CFG) that drives deterministically with k lookahead symbols a push down stack, while scanning the input from left to right. It has been shown that they recognize exactly the set of languages recognized by deterministic push down automata. LR(k) parsers for CFGs have been proven useful for compilers as well as recently for nat- ural language processing. For natural language process- ing, although LR(k) parsers are not powerful enough, *The first author is partially supported by Darpa grant N0014-85- K0018, ARO grant DAAL03-89-C-003iPRI NSF grant-IRIS4-10413 A02. We are extremely grateful to Bernard Lang and David Weir for their valuable suggestions. 276 conflicts between multiple choices are solved by pseudo- parallelism (Lang, 1974, Tomita, 1987). This gives rise to a class of powerful yet efficient parsers for natural languages. It is in this context that we study determin- istic (LR(k)-style) parsing of TAGs. The set of Tree Adjoining Languages is a strict su- perset of the set of Context Free Languages (CFLs). For example, the cross serial dependency constmction in Dutch can be generated by a TAG. 1 Waiters (1970), R~v6sz (1971), Turnbull and Lee (1979) investigated deterministic parsing of the class of context-sensitive languages. However they used Turing machines which recognize languages much more powerful than Tree Ad- joining Languages. So far no deterministic bottom-up parser has been proposed for any member of the class of the so-called "mildly context sensitive" formalisms (Joshi, 1985) in which Tree Adjoining Grammars fall. 2 Since the set of Tree Adjoining Languages (TALs) is a strict superset of the set of Context Free Languages, in order to define LR-type parsers for TAGs, we need to use a more powerful configuration then a finite state au- …

Content truncated to 500 words