Efficient Matrix-Encoded Grammars and Low Latency Parallelization Strategies for CYK

We present a matrix encoding of context-free grammars, motivated by hardware-level efficiency considerations. We find efficiency gains of 2.5--9x for exhaustive inference and approximately 2x for pruned inference, resulting in high-accuracy parsing at over 20 sentences per second. Our grammar encoding allows fine-grained parallelism during chart cell population; we present a controlled study of several methods of parallel parsing, and find near-optimal latency reductions as core-count increases.