Semantics-Preserving Transformation of Context-Free Grammars into LL(1) Form

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.