Paper: Parsing Schemata For Grammars With Variable Number And Order Of Constituents

ACL ID C00-2106
Title Parsing Schemata For Grammars With Variable Number And Order Of Constituents
Venue International Conference on Computational Linguistics
Session Main Conference
Year 2000
Authors

We define state transition grammars (STG) as an intermediate tbrmalism between grammars and parsing algorithms which is intended to separate the description of a parsing strategy from the grammar tbrmalism. This allows to de- fine more general parsing algorithms for larger classes of grammars, including gramnmrs where the nunfl)er and order of subconstituents de- tined by a production may not be tlxed. Various grammar formalisms are characterized in terms of prol)erties of STG's. We define an Earley parsing schema tbr S'rC's and characterize the wflid l)arse items. We also discuss the usabil- ity of STG's tbr head-(:orner parsing and direct 1)arsing of sets of tree constraints.