Parsing schemata for grammars with variable number and order of constituents

We define state transition grammars (STG) as an intermediate formalism between grammars and parsing algorithms which is intended to separate the description of a parsing strategy from the grammar formalism. This allows to define more general parsing algorithms for larger classes of grammars, including grammars where the number and order of subconstituents defined by a production may not be fixed. Various grammar formalisms are characterized in terms of properties of STG's. We define an Earley parsing schema for STG's and characterize the valid parse items. We also discuss the usability of STG's for head-corner parsing and direct parsing of sets of tree constraints.