Generalized LR parsing for grammars with contexts

Mikhail Barash, Alexander Okhotin

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференции

2 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Proceedings
РедакторыLev D. Beklemishev, Daniil V. Musatov, Daniil V. Musatov
ИздательSpringer Nature
Страницы67-79
Число страниц13
ISBN (печатное издание)9783319202969
DOI
СостояниеОпубликовано - 1 янв 2015
Событие10th International Computer Science Symposium in Russia, CSR 2015 - Listvyanka, Российская Федерация
Продолжительность: 13 июл 201517 июл 2015

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9139
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция10th International Computer Science Symposium in Russia, CSR 2015
СтранаРоссийская Федерация
ГородListvyanka
Период13/07/1517/07/15

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Generalized LR parsing for grammars with contexts». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать