Generalized LR parsing for grammars with contexts

Mikhail Barash, Alexander Okhotin

Research output

2 Citations (Scopus)

Abstract

The Generalized LR parsing algorithm for context-free grammars is notable for having a decent worst-case running time (cubic in the length of the input string), as well as much better performance on “good” grammars. This paper extends the Generalized LR algorithm to the case of “grammars with left contexts” (M. Barash, A. Okhotin, “An extension of context-free grammars with one-sided context specifications”, Inform. Comput., 2014), which augment the context-free grammars with special operators for referring to the left context of the current substring, as well as with a conjunction operator (as in conjunctive grammars) for combining syntactical conditions. All usual components of the LR algorithm, such as the parsing table, shift and reduce actions, etc., are extended to handle the context operators. The resulting algorithm is applicable to any grammar with left contexts and has the same worst-case cubic-time performance as in the case of context-free grammars.

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings
EditorsLev D. Beklemishev, Daniil V. Musatov, Daniil V. Musatov
PublisherSpringer Nature
Pages67-79
Number of pages13
ISBN (Print)9783319202969
DOIs
Publication statusPublished - 1 Jan 2015
Event10th International Computer Science Symposium in Russia, CSR 2015 - Listvyanka
Duration: 13 Jul 201517 Jul 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9139
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Computer Science Symposium in Russia, CSR 2015
CountryRussian Federation
CityListvyanka
Period13/07/1517/07/15

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Generalized LR parsing for grammars with contexts'. Together they form a unique fingerprint.

  • Cite this

    Barash, M., & Okhotin, A. (2015). Generalized LR parsing for grammars with contexts. In L. D. Beklemishev, D. V. Musatov, & D. V. Musatov (Eds.), Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings (pp. 67-79). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9139). Springer Nature. https://doi.org/10.1007/978-3-319-20297-6_5