Article · January 1, 2006
A New Approach to the Construction of Generalized LR Parsing Algorithms
Miguel Á. Alonso, David Cabrero, Jesús Vilares
Abstract
LR parsing strategies can analyze LR grammars, which are deterministic. If we consider LR parsing tables in which each entry can contain several actions, we obtain non-deterministic LR parsing, often known as generalized LR parsing, which can analyze non-deterministic context-free grammars. It this context, some mechanism is needed in order to represent the non-deterministic evolution of the stack. Tomita (Tomita 86) have proposed an algorithm based on a graph-structured stack but it has problems with cyclic and hidden left recursive constructions. Rekers (Rekers 92) has modified the original algorithm to overcome its limitations, but maintaining its original complexity O(np+1), where p is the length of the longer right-hand side of a rule. Space and time bounds can be reduced transforming the form of the grammar (Sheil 76). Some approaches also use transformations in the construction of the LR automaton and in these the treatment of cyclicity is even more complex and so is often avoided (Nederhof & Sarbo 93). We propose a generalized LR(1) and LALR(1) parsing algorithm for arbitrary context-free grammars which is derived, in a natural way, from the well known Earley’s algorithm (Earley 70), preserving cubic time complexity in the worst case.
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
