Implementation of a Chomsky-Schützenberger n-best parser for weighted multiple context-free grammars

Thomas Ruprecht, Tobias Denkinger


Abstract
Constituent parsing has been studied extensively in the last decades. Chomsky-Schützenberger parsing as an approach to constituent parsing has only been investigated theoretically, yet. It uses the decomposition of a language into a regular language, a homomorphism, and a bracket language to divide the parsing problem into simpler subproblems. We provide the first implementation of Chomsky-Schützenberger parsing. It employs multiple context-free grammars and incorporates many refinements to achieve feasibility. We compare its performance to state-of-the-art grammar-based parsers.
Anthology ID:
N19-1016
Volume:
Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)
Month:
June
Year:
2019
Address:
Minneapolis, Minnesota
Editors:
Jill Burstein, Christy Doran, Thamar Solorio
Venue:
NAACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
178–191
Language:
URL:
https://aclanthology.org/N19-1016
DOI:
10.18653/v1/N19-1016
Bibkey:
Cite (ACL):
Thomas Ruprecht and Tobias Denkinger. 2019. Implementation of a Chomsky-Schützenberger n-best parser for weighted multiple context-free grammars. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 178–191, Minneapolis, Minnesota. Association for Computational Linguistics.
Cite (Informal):
Implementation of a Chomsky-Schützenberger n-best parser for weighted multiple context-free grammars (Ruprecht & Denkinger, NAACL 2019)
Copy Citation:
PDF:
https://aclanthology.org/N19-1016.pdf
Video:
 https://vimeo.com/360467719