TY - JOUR

T1 - Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts

AU - Barash, Mikhail

AU - Okhotin, Alexander

N1 - Publisher Copyright: © 2016, Springer Science+Business Media New York.

PY - 2017/8/1

Y1 - 2017/8/1

N2 - 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, if implemented efficiently), 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, along 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.

AB - 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, if implemented efficiently), 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, along 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.

KW - Conjunctive grammars

KW - Contexts

KW - Formal grammars

KW - GLR parsing

KW - LR parsing

UR - http://www.scopus.com/inward/record.url?scp=85023762798&partnerID=8YFLogxK

U2 - 10.1007/s00224-016-9683-3

DO - 10.1007/s00224-016-9683-3

M3 - Article

AN - SCOPUS:85023762798

VL - 61

SP - 581

EP - 605

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -