Article
On Theoretical and Practical Complexity of TAG Parsers
Carlos Gómez‐Rodríguez, Miguel Á. Alonso, Jesús Vilares
Abstract
We present a system allowing the automatic transformation of parsing schemata to efficient executable implementations of their corresponding algorithms. This system can be used to easily prototype, test and compare different parsing algorithms. In this work, it has been used to generate several different parsers for Context Free Grammars and Tree Adjoining Grammars. By comparing their performance on different sized, artificially generated grammars, we can measure their empirical computational complexity. This allows us to evaluate the overhead caused by using Tree Adjoining Grammars to parse context-free languages, and the influence of string and grammar size on Tree Adjoining Grammars parsing.
More by Miguel Alonso
- Public Sentiment Analysis and Topic Modeling Regarding COVID-19’s Three Waves of Total Lockdown: A Case Study on Movement Control Order in MalaysiaKSII Transactions on Internet and Information Systems · 2022 · Citations: 11
- Construction and Evaluation of Sentiment Datasets for Low-Resource Languages: The Case of UzbekLecture notes in computer science · 2022 · Citations: 42
- Sentiment Analysis for Fake News DetectionElectronics · 2021 · Citations: 270
- On the Use of Parsing for Named Entity RecognitionApplied Sciences · 2021 · Citations: 24
