Abstract
We present a new formalism, partially ordered multiset context-free grammars (poms-CFG), along with an Earley-style parsing algorithm. The formalism, which can be thought of as a generalization of context-free grammars with partially ordered right-hand sides, is of interest in its own right, and also as infrastructure for obtaining tighter complexity bounds for more expressive context-free formalisms intended to express free or multiple word-order, such as ID/LP grammars. We reduce ID/LP grammars to poms-grammars, thereby getting finer-grained bounds on the parsing complexity of ID/LP grammars. We argue that in practice, the width of attested ID/LP grammars is small, yielding effectively polynomial time complexity for ID/LP grammar parsing.- Anthology ID:
- W03-3020
- Volume:
- Proceedings of the Eighth International Conference on Parsing Technologies
- Month:
- April
- Year:
- 2003
- Address:
- Nancy, France
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Note:
- Pages:
- 171–182
- Language:
- URL:
- https://aclanthology.org/W03-3020
- DOI:
- Cite (ACL):
- Mark-Jan Nederhof, Giorgio Satta, and Stuart Shieber. 2003. Partially Ordered Multiset Context-free Grammars and Free-word-order Parsing. In Proceedings of the Eighth International Conference on Parsing Technologies, pages 171–182, Nancy, France.
- Cite (Informal):
- Partially Ordered Multiset Context-free Grammars and Free-word-order Parsing (Nederhof et al., IWPT 2003)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-4/W03-3020.pdf