We present a CYK and an Earley-style algorithm for parsing Range Concatenation Grammar (RCG), using the deductive parsing framework.
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).
The rules (clauses) of RCGs1 rewrite predicates ranging over parts of the input by other predicates.
In our directional CYK algorithm, we move a dot through the righthand side of a clause.
We now add top-down prediction to our algorithm.
We have presented a new CYK and Earley parsing algorithms for the full class of RCG.