Dependency-to-constituency transformation
Keywords:
formal linguistics
dependency grammar
constituency grammar
syntax parsing
dependency tree
natural language syntax
natural language processing
Abstract
Dependency and constituency analyses are the two most widely used formalisms for representing natural-language syntax. Dependency grammar originates in traditional approaches to syntactic analysis and is now implemented in numerous computational systems. At the same time, theoretical linguists and linguistic typologists often favour constituency grammar because it is well suited to representing hierarchical phrase structure. Although the two formalisms have comparable descriptive power, dependency representations can be converted into constituency representations. This study proposes and implements an algorithm for dependency-to-constituency conversion. The algorithm identifies heads in a dependency representation and subsequently selects and linearizes the words belonging to the corresponding constituents. It is implemented as a Python library and has undergone initial testing.
Section
Methods and algorithms of computational mathematics and their applications
References
- Ya. G. Testelets, Introduction to General Syntax(Russian State University for the Humanities, Moscow, 2001) [in Russian].
- D. Jurafsky and J. H. Martin, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition with Language Models, 3rd ed. Online manuscript (2026).
https://web.stanford.edu/ jurafsky/slp3/ Cited November 15, 2026.
- L. Tesnière, Éléments de syntaxe structurale(Klincksieck, Paris, 1959).
- I. A. Mel’čuk, Dependency Syntax: Theory and Practice(State University of New York Press, Albany, NY, 1988).
- N. Chomsky, Syntactic Structures(Mouton, The Hague, 1957).
- N. Chomsky, Lectures on Government and Binding(Foris Publications, Dordrecht, 1981).
- N. Chomsky, “Minimalist Inquiries: The Framework,” in Step by Step: Essays on Minimalist Syntax in Honor of Howard Lasnik(MIT Press, Cambridge, MA, 2000), pp. 89–155.
- E. P. Stabler, “Derivational Minimalism,” in Logical Aspects of Computational Linguistics: First International Conference, LACL’96, Nancy, France, September 23–25, 1996, Lecture Notes in Computer Science, Vol. 1328. (Springer, Berlin, 1997), pp. 68–95.
doi 10.1007/BFb0052152
- N. Chomsky, “Three Models for the Description of Language,” IRE Trans. Inf. Theory 2 (3), 113–124 (1956).
doi 10.1109/TIT.1956.1056813
- N. Chomsky, “On Certain Formal Properties of Grammars,” Inf. Control 2 (2), 137–167 (1959).
doi 10.1016/S0019-9958(59)90362-6
- H. Gaifman, “Dependency Systems and Phrase-Structure Systems,” Inf. Control 8 (3), 304–337 (1965).
doi 10.1016/S0019-9958(65)90232-9
- D. D. K. Sleator and D. Temperley, “Parsing English with a Link Grammar,” in Proc. Third International Workshop on Parsing Technologies, Tilburg, Netherlands and Durbuy, Belgium, August 10–13, 1993(Association for Computational Linguistics, 1993), pp. 277–292.
- M. Collins, “Three Generative, Lexicalised Models for Statistical Parsing,” in Proc. 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics(Madrid, Spain, 1997), pp. 16–23.
doi 10.3115/976909.979620
- M. Collins, J. Hajič, L. Ramshaw, and C. Tillmann, “A Statistical Parser for Czech,” in Proc. 37th Annual Meeting of the Association for Computational Linguistics on Computational Linguistics, College Park, Maryland, USA, 1999(Association for Computational Linguistics, 1999), pp. 505–512.
doi 10.3115/1034678.1034754
- P. Qi, Y. Zhang, Y. Zhang, et al., “Stanza: A Python Natural Language Processing Toolkit for Many Human Languages,” in Proc. 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, 2020, pp. 101–108.
doi 10.18653/v1/2020.acl-demos.14
- F. Xia and M. Palmer, “Converting Dependency Structures to Phrase Structures,” in Proc. First International Conference on Human Language Technology Research, San Diego, March 18–21, 2001, (Association for Computational Linguistics, Stroudsburg, USA, 2001), pp. 1–5.
https://doi.org/10.3115/1072133.1072147 Cited November 15, 2026.
- D. Fernández-González and A. F. T. Martins, “Parsing as Reduction,” in Proc. 53rd Annual Meeting of the Association for Computational Linguistics and 7th International Joint Conference on Natural Language Processing, Beijing, China, July 26–31, 2015, Vol. 1. (Association for Computational Linguistics, 2015), pp. 1523–1533.
doi 10.3115/v1/P15-1147
- L. Kong, A. M. Rush, and N. A. Smith, “Transforming Dependencies into Phrase Structures,” 2015 Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Denver, Colorado, May 31–June 5, 2015. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics, 2015, pp. 788–798.
doi 10.3115/v1/N15-1080
- A. Luu, S. A. Malamud, and N. Xue, “Converting SynTagRus Dependency Treebank into Penn Treebank Style,” in Proc. 10th Linguistic Annotation Workshop held in conjunction with ACL 2016 (LAW-X 2016), Berlin, Germany, August 11, 2016(Association for Computational Linguistics, 2016), pp. 16–21.
doi 10.18653/v1/W16-1703
- A. Yu. Poletaev, I. V. Paramonov, and E. I. Boychuk, “Algorithm of Constituency Tree from Dependency Tree Construction for a Russian-Language Sentence,” Informatics and Automation 22 (6), 1323–1353 (2023).
https://doi.org/10.15622/ia.22.6.3 Cited November 15, 2026.
- M.-C. de Marneffe, C. D. Manning, J. Nivre, and D. Zeman, “Universal Dependencies,” Comput. Linguist. 47 (2), 255–308 (2021).
doi 10.1162/coli_a_00402
- M. Ermolaeva, “Learning Syntax via Decomposition,” Ph.D. thesis (University of Chicago, Chicago, IL, 2021).
doi 10.6082/uchicago.3015
- N. Chomsky, The Minimalist Program(MIT Press, Cambridge, MA, London, 1995).
- S. Kahane, B. Caron, E. Strickland, and K. Gerdes, “Annotation Guidelines of UD and SUD Treebanks for Spoken Corpora: A Proposal,” in Proc. 20th International Workshop on Treebanks and Linguistic Theories (TLT, SyntaxFest 2021), Sofia, Bulgaria, 2021(Association for Computational Linguistics, 2021), pp. 35–47.
doi 10.18653/v1/2021.tlt-1.4
- H. M. Eckhoff and A. Berdicevskis, “Linguistics vs. Digital Editions: The Tromsø Old Russian and OCS Treebank,” Scripta & e-Scripta textbf14–15, 9–25 (2015).
- Ye. S. Inshakova, L. L. Iomdin, L. G. Mityushin, et al., “The SynTagRus Today,” Proceedings of the V. V. Vinogradov Russian Language Institute 3 (21), 14–41 (2019). [in Russian].
doi 10.31912/pvrli-2019.3.1
- S. Bird, E. Loper, and E. Klein, Natural Language Processing with Python: analyzing text with the natural language toolkit(O’Reilly Media, Inc., Sebastopol, CA, 2009).
- C. Alzetta, A. Miaschi, F. Dell’Orletta, et al., “Parallel Trees: A Novel Resource with Aligned Dependency and Constituency Syntactic Representations,” Lang. Resour. Eval. 59 (4), 3445–3485 (2025).
doi 10.1007/s10579-025-09826-3
- Free eBooks | Project Gutenberg.
https://www.gutenberg.org/ Cited November 15, 2026.