[Onward!'25] Semantics-preserving Transformation of Context-free Grammars into LL(1) Form

Описание: Semantics-Preserving Transformation of Context-Free Grammars into LL(1) Form (Video, Onward! 2025)
Vladyslav Bilyk
(Unaffiliated, Lviv, Ukraine)

Abstract: Transformation of context-free grammars into LL(1) form enables construction of simple and efficient parsers.
However, if semantics are overlooked, the transformation is likely to result in a complex grammar that needs to be manually
aligned with the original semantics.
This work presents a method of semantics-preserving grammar transformation into LL(1) form using a representation based on trees.
Grammar rules and their semantics are modelled as typed tree nodes, which enables elimination of LL(1) conflicts while retaining the original semantics.
Transformed grammars can be used to construct continuation-passing style parsers that produce parse
trees matching the original grammar.
It is shown how this approach can be applied to the design of domain-specific languages in Java,
resulting in size and type complexity linear in the size of the transformed grammar.

Article: https://doi.org/10.1145/3759429.3762618

ORCID: https://orcid.org/0009-0002-0173-0120

Video Tags: formal languages, grammarware, grammars, parsing, semantics, Java, onward25papers-p8-p, doi:10.1145/3759429.3762618, orcid:0009-0002-0173-0120

Presentation at the Onward! 2025 conference, October 12–18, 2025, https://2025.splashcon.org/track/spla...
Sponsored by ACM SIGPLAN, ACM SIGAda,