Standard

On the Transformation of LL(k)-linear to LL(1)-linear Grammars. / Ольховский, Илья Сергеевич; Охотин, Александр Сергеевич.

In: Theory of Computing Systems, Vol. 67, No. 2, 01.04.2023, p. 234-262.

Research output: Contribution to journal › Article › peer-review

Harvard

Ольховский, ИС & Охотин, АС 2023, 'On the Transformation of LL(k)-linear to LL(1)-linear Grammars', Theory of Computing Systems, vol. 67, no. 2, pp. 234-262. https://doi.org/10.1007/s00224-022-10108-6

APA

Ольховский, И. С., & Охотин, А. С. (2023). On the Transformation of LL(k)-linear to LL(1)-linear Grammars. Theory of Computing Systems, 67(2), 234-262. https://doi.org/10.1007/s00224-022-10108-6

Vancouver

Ольховский ИС, Охотин АС. On the Transformation of LL(k)-linear to LL(1)-linear Grammars. Theory of Computing Systems. 2023 Apr 1;67(2):234-262. https://doi.org/10.1007/s00224-022-10108-6

Author

Ольховский, Илья Сергеевич ; Охотин, Александр Сергеевич. / On the Transformation of LL(k)-linear to LL(1)-linear Grammars. In: Theory of Computing Systems. 2023 ; Vol. 67, No. 2. pp. 234-262.

BibTeX

@article{7c49fc12fdc74f4792fc30c3e08e0084,
title = "On the Transformation of LL(k)-linear to LL(1)-linear Grammars",
abstract = "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 m2k−O(1), 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 n⋅ (m− 1) 2k−O(logk) nonterminal symbols.",
keywords = "Descriptional complexity, LL grammars, Linear grammars, Parsing",
author = "Ольховский, {Илья Сергеевич} and Охотин, {Александр Сергеевич}",
year = "2023",
month = apr,
day = "1",
doi = "10.1007/s00224-022-10108-6",
language = "English",
volume = "67",
pages = "234--262",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer Nature",
number = "2",

}

RIS

TY - JOUR

T1 - On the Transformation of LL(k)-linear to LL(1)-linear Grammars

AU - Ольховский, Илья Сергеевич

AU - Охотин, Александр Сергеевич

PY - 2023/4/1

Y1 - 2023/4/1

N2 - 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 m2k−O(1), 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 n⋅ (m− 1) 2k−O(logk) nonterminal symbols.

AB - 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 m2k−O(1), 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 n⋅ (m− 1) 2k−O(logk) nonterminal symbols.

KW - Descriptional complexity

KW - LL grammars

KW - Linear grammars

KW - Parsing

UR - https://www.mendeley.com/catalogue/09467de5-5bb6-35c9-99ec-5b5cef619ac6/

U2 - 10.1007/s00224-022-10108-6

DO - 10.1007/s00224-022-10108-6

M3 - Article

VL - 67

SP - 234

EP - 262

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -

ID: 108695819