Practical Parsing of Parallel Multiple Context-Free Grammars
Peter Ljunglöf · Chalmers Publication Library (Chalmers University of Technology) · 2012
We discuss four previously published parsing algorithms for parallell multiple context-free grammar (PMCFG), and ar-gue that they are similar to each other, and implement an Earley-style top-down algo-rithm. Starting from one of these algo-rithms, we derive three modifications – one bottom-up and two variants using a left cor-ner filter. An evaluation shows that sub-stantial improvements can be made by us-ing the algorithm that performs best on a given grammar. The algorithms are imple-mented in Python and released under an open-source licence. We start by introducing the necessary concepts. Then we discuss four previously published PM-CFG algorithms, and argue that they are similar. We take Angelov (2009) as a starting point for introducing three new parsing strategies. Finally we discuss various optimizations of the parsing strategies and give a small evaluation.