Graph-based Parsing Strategies for Categorial Grammars

Richard Moot (Utrecht University)

When designing a parser for categorial grammars it turns out that
tree-like data structures are suboptimal both from a conceptual and
from a computational point of view. I therefore propose to use
insights from the linear logic community and use graphs to represent
lexical entries and (partial) parses.

This design choice allows us to implement a simple three-step algorithm for parsing sentences; first, we look up the graphs corresponding to the lexical items, secondly, we combine these graphs into a single graph containing the information from the lexical items plus the way they relate to eachother, finally, we check if this graph satisfies some language-dependent wellformedness conditions.

I will discuss some natural improvements to this basic algorithm and compare it to other strategies for parsing categorial grammars.