Parser Combinators, (Simply) Indexed Grammars, Natural Language Parsing

Parser combinators [4, 6] are higher order functions that transform parsers into parsers. Parsing with context free grammars can be handled by defining combinators for the key operations in context free grammar rules: recognizing epsilon, recognizing a terminal, choice between rewrite rules for a given nonterminal, and sequencing under a nonterminal. After explaining and illustrating this in some detail, we demonstrate how adding two extra combinators, push and pop, allows us to define stack parser combinators that can be used for the analysis of movement (or extraction) in natural language. Push and pop increase the expressive power of parser combinators to beyond CF. The corresponding grammar formalism turns out to be a slight variation on that of indexed grammars. Studying indexed grammars from the perspective of deductive parsing, we propose Earley style parsing algorithms for them, and for the variation on them (“simply indexed grammars”) that corresponds to the parser combinators with push and pop.