Paper: Deterministic Left To Right Parsing Of Tree Adjoining Languages

ACL ID P90-1035
Title Deterministic Left To Right Parsing Of Tree Adjoining Languages
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1990
Authors

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-s...