Extended context-free grammars parsing with generalized LL

Artem Gorokhov, Semyon Grigorev

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

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

Аннотация

Parsing plays an important role in static program analysis: during this step a structural representation of code is created upon which further analysis is performed. Parser generator tools, being provided with syntax specification, automate parser development. Language documentation often acts as such specification. Documentation usually takes form of ambiguous grammar in Extended Backus-Naur Form which most parser generators fail to process. Automatic grammar transformation generally leads to parsing performance decrease. Some approaches support EBNF grammars natively, but they all fail to handle ambiguous grammars. On the other hand, Generalized LL parsing algorithm admits arbitrary context-free grammars and achieves good performance, but cannot handle EBNF grammars. The main contribution of this paper is a modification of GLL algorithm which can process grammars in a form which is closely related to EBNF (Extended Context-Free Grammar). We also show that the modification improves parsing performance as compared to grammar transformation-based approach.

Язык оригиналаанглийский
Название основной публикацииTools and Methods of Program Analysis - 4th International Conference, TMPA 2017, Revised Selected Papers
РедакторыVictor Zakharov, Vladimir Itsykson, Andre Scedrov
ИздательSpringer Nature
Страницы24-37
Число страниц14
ISBN (печатное издание)9783319717333
DOI
СостояниеОпубликовано - 1 янв 2018
Событие4th International Conference on Tools and Methods of Program Analysis, TMPA 2017 - Moscow, Российская Федерация
Продолжительность: 3 мар 20174 мар 2017

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

НазваниеCommunications in Computer and Information Science
Том779
ISSN (печатное издание)1865-0929

конференция

конференция4th International Conference on Tools and Methods of Program Analysis, TMPA 2017
СтранаРоссийская Федерация
ГородMoscow
Период3/03/174/03/17

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

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

Fingerprint Подробные сведения о темах исследования «Extended context-free grammars parsing with generalized LL». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать