On the transformation of ll(k)-linear grammars to ll(1)-linear

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

Аннотация

It is proved that every LL(k)-linear grammar can be transformed to an equivalent LL(1)-linear grammar. The transformation incurs a blow-up in the number of nonterminal symbols by a factor of (formula presented), where m is the size of the alphabet. A close lower bound is established: for certain LL(k)-linear grammars with n nonterminal symbols, every equivalent LL(1)-linear grammar must have at least (formula presented) nonterminal symbols.

Язык оригиналаанглийский
Название основной публикацииComputer Science – Theory and Applications - 15th International Computer Science Symposium in Russia, CSR 2020, Proceedings
РедакторыHenning Fernau
ИздательSpringer Nature
Страницы328-340
Число страниц13
ISBN (печатное издание)9783030500252
DOI
СостояниеОпубликовано - 1 июн 2020
Событие15th International Computer Science Symposium in Russia, CSR 2020 - Yekaterinburg, Российская Федерация
Продолжительность: 29 июн 20203 июл 2020

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

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

конференция

конференция15th International Computer Science Symposium in Russia, CSR 2020
СтранаРоссийская Федерация
ГородYekaterinburg
Период29/06/203/07/20

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

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

Fingerprint Подробные сведения о темах исследования «On the transformation of ll(k)-linear grammars to ll(1)-linear». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать