CIAA2003

START ConferenceManager

LR Parsing for Global Index Grammars

Jose M. Castano

Presented at Eighth International Conference on Implementation and Application of Automata (CIAA 2003), July 16-18, 2003 Santa Barbara, CA, USA

Abstract

We present here Global Index Grammars (GIGs) and the characterizing 2 Stack automaton model (LR-2PDA). We present the techniques to construct an LR parsing table for deterministic Global Index Grammars. GILs include languages which are beyond the power of Linear Indexed Grammars/Tree Adjoining Grammars. GILs generalize properties of CF Languages in a straightforward way and their descriptive power is relevant at least for natural language and molecular biology phenomena.