Incremental Parser Generation for Tree Adjoining Grammars

Incremental Parser Generation for Tree Adjoining Grammars* Anoop Sarkar University of Pennsylvania Department of Computer and Information Science 200 S. 33rd St., Philadelphia PA 19104-6389, USA anoop©linc, cis. upenn, edu Abstract This paper describes the incremental generation of parse tables for the LR- type parsing of Tree Adjoining Languages (TALs). The algorithm presented han- dles modifications to the input grammar by updating the parser generated so far. In this paper, a lazy generation of LR- type parsers for TALs is defined in which parse tables are created by need while parsing. We then describe an incremental parser generator for TALs which responds to modification of the input grammar by updating parse tables built so far. 1 LR Parser Generation Tree Adjoining Grammars (TAGs) are tree rewrit- ing systems which combine trees with the sin- gle operation of adjoining. (Schabes and Vijay- Shanker, 1990) describes the construction of an LR parsing algorithm for TAGs 1. Parser generation here is taken to be the construction of LR(0) ta- bles (i.e., without any lookahead) for a particular TAG z. The moves made by the parser can be ex- plained by an automaton which is weakly equivalent to TAGs called Bottom-Up Embedded Pushdown Automata (BEPDA) (Schabes and Vijay-Shanker, 1990) 3. Storage in a BEPDA is a sequence of stacks, *This work is partially supported by NSF grant NSF- STC SBR 8920230 ARPA grant N00014-94 and ARO grant DAAH04-94-G0426. Thanks to Breck Baldwin, Dania Egedi, Jason Eisner, B. Srinivas and the three anonymous reviewers for their valuable comments. 1 Familiarity with TAGs and their parsing techniques is assumed throughout the paper, see (Schabes and Joshi, 1991) for an introduction. We assume that our definition of TAG does not have the substitution opera- tion. See (Aho et al., 1986) for details on LR parsing. 2The algorithm described here can be extended to use SLR(1) tables (Schabes and Vijay-Shanker, 1990). SNote that the LR(0) tables considered here are deter- ministic and hence correspond to a subset of the TALs. Techniques developed in (Tomita, 1986) can be used to resolve nondeterminism in the parser. where new stacks can be introduced above and be- low the top stack in the automaton. Recognition of adjunction is equivalent to the unwrap move shown in Fig. 1. of Figure 1: Recognition of adjunction in a BEPDA. The LR parser (of (Schabes and Vijay-Shanker, 1990)) uses a parsing table and a sequence of stacks (Fig. 1) to parse the input. The parsing table en- codes the actions taken by the parser as follows (us- ing two GOTO functions): • Shift to a new state, pushed onto a new stack which appears on top of the current sequence of stacks. The current input token is removed. • Resume Right when the parser has reached right and below a node (in a dotted tree, ex- plained below) on which an auxiliary tree has been adjoined. The GOTOIoo, function en- codes the proper state such that the string to the right of the footnode can be …

Content truncated to 500 words