Standard

Generalized LR parsing for grammars with contexts. / Barash, Mikhail; Okhotin, Alexander.

Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. ed. / Lev D. Beklemishev; Daniil V. Musatov; Daniil V. Musatov. Springer Nature, 2015. p. 67-79 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9139).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Barash, M & Okhotin, A 2015, Generalized LR parsing for grammars with contexts. in LD Beklemishev, DV Musatov & DV Musatov (eds), Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9139, Springer Nature, pp. 67-79, 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russian Federation, 13/07/15. https://doi.org/10.1007/978-3-319-20297-6_5

APA

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

Vancouver

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

Author

Barash, Mikhail ; Okhotin, Alexander. / Generalized LR parsing for grammars with contexts. Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings. editor / Lev D. Beklemishev ; Daniil V. Musatov ; Daniil V. Musatov. Springer Nature, 2015. pp. 67-79 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{ff1da7a9760c45fcbbcb1caec4c755b4,
title = "Generalized LR parsing for grammars with contexts",
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.",
author = "Mikhail Barash and Alexander Okhotin",
year = "2015",
month = jan,
day = "1",
doi = "10.1007/978-3-319-20297-6_5",
language = "English",
isbn = "9783319202969",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "67--79",
editor = "Beklemishev, {Lev D.} and Musatov, {Daniil V.} and Musatov, {Daniil V.}",
booktitle = "Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings",
address = "Germany",
note = "10th International Computer Science Symposium in Russia, CSR 2015 ; Conference date: 13-07-2015 Through 17-07-2015",

}

RIS

TY - GEN

T1 - Generalized LR parsing for grammars with contexts

AU - Barash, Mikhail

AU - Okhotin, Alexander

PY - 2015/1/1

Y1 - 2015/1/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), 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.

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), 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.

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

U2 - 10.1007/978-3-319-20297-6_5

DO - 10.1007/978-3-319-20297-6_5

M3 - Conference contribution

AN - SCOPUS:84943660307

SN - 9783319202969

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 67

EP - 79

BT - Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings

A2 - Beklemishev, Lev D.

A2 - Musatov, Daniil V.

A2 - Musatov, Daniil V.

PB - Springer Nature

T2 - 10th International Computer Science Symposium in Russia, CSR 2015

Y2 - 13 July 2015 through 17 July 2015

ER -

ID: 41143465