Top-Down Recognizers for MCFGs and MGs
Edward P. Stabler · 2011
This paper defines a normal form for MCFGs that includes strongly equivalent representations of many MG variants, and presents an incremental priority-queue-based TD recognizer for these MCFGs. After introducing MGs with overt phrasal movement, head movement and simple adjunction are added without change in the recognizer. The MG representation can be used directly, so that even rather sophisticated analyses of properly non-CF languages can be defined very succinctly. As with the similar stack-based CFmethods, finite memory suffices for the recognition of infinite languages, and a fully connected left context for probabilistic analysis is available at every point. 1