Publications
Article
Construction of Efficient Generalized LR Parsers
Miguel Á. Alonso, David Cabrero, Jesús Vilares, Facultad De Inform'atica
Abstract
Abstract. We show how LR parsers for the analysis of arbitrary contextfree grammars can be derived from classical Earley’s parsing algorithm. The result is a Generalized LR parsing algorithm working at complexity O(n 3) in the worst case, which is achieved by the use of dynamic programming to represent the non-deterministic evolution of the stack instead of graph-structured stack representations, as has often been the case in previous approaches. The algorithm behaves better in practical cases, achieving linear complexity on LR grammars. Experimental results show the performance of our proposal. 1
semigroups and automata theoryNatural Language Processing TechniquesAlgorithms and Data Compressiongeneralized LR parsingEarley's algorithmcontext-free grammars
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
