A Prefix-Correct Earley Recognizer for Multiple Context-Free Grammars
Makoto Kanazawa · 2008
We present a method for deriving an Earley recognizer for multiple context-free grammars with the correct prefix property. This is done by representing an MCFG by a Datalog program and applying generalized supplementary magic-sets rewriting. To secure the correct prefix property, a simple extra rewriting must be performed before the magic-sets rewriting. The correctness of the method is easy to see, and a straightforward application of the method to tree-adjoining grammars yields a recognizer whose running time is O(n 6). 1 Deriving an Earley-style recognizer by magic-sets rewriting We use the following 2-MCFG generating RESP+ = { am 1 am 2 bn 1bn 2am 3 am 4 bn 3bn 4 | m, n ≥ 1} as our running example: 1 (1) S (x1y1x2y2): − P(x1, x2), Q(y1, y2). P(a1a2, a3a4).