An Earley Parsing Algorithm for Range Concatenation Grammars
Kallmeyer, Laura and Maier, Wolfgang and Parmentier, Yannick

Article Structure

Abstract

We present a CYK and an Earley-style algorithm for parsing Range Concatenation Grammar (RCG), using the deductive parsing framework.

Introduction

RCGs (Boullier, 2000) have recently received a growing interest in natural language processing (S¬Ęgaard, 2008; Sagot, 2005; Kallmeyer et al., 2008; Maier and Sszsgaard, 2008).

Preliminaries

The rules (clauses) of RCGs1 rewrite predicates ranging over parts of the input by other predicates.

Directional Bottom-Up Chart Parsing

In our directional CYK algorithm, we move a dot through the righthand side of a clause.

The Earley Algorithm

We now add top-down prediction to our algorithm.

Conclusion and future work

We have presented a new CYK and Earley parsing algorithms for the full class of RCG.

Topics