Advancing Combinator Parsing in Scala

LL(1) Parser with Compile Time Capabilities

Description

In my bachelor semester project (spring 2021) at the LARA lab at EPFL, I built a LL(1) parser generator with compile time capabilities based on the Scall1on parser. It allows the user to define a syntax based on combinators, and construct a parsing table mostly at compile time. Some work has to be done at runtime, as some datatype are not well supported by macro, so either the user has to handle each custom type, or it is not possible get them out of the macro context.

The advantages are:

• Shorter runtime setup time (only one traversal of the syntax definition)
• Efficient parsing algorithm
• An instant feedback of the possible LL(1) conflicts in the syntax definition.
• Possibly, a safer packaging of libraries as a flawed parser with LL(1) conflicts won't compile.

Usage

An example is provided in example/syntaxdef. More modular examples are provided here example/modular or also in the tests.

⚠️ The syntax definition and the macro call and implementation have to be in a single file to avoid compilation issues.

An easy way to get started is by using SBT (here v1.5.3), sbt new scala/scala3.g8 and adding the library jar file to a directory in the project lib/.

Also, please find the API documentation here.

Extras

• I used the Silex lexing library, which I had to upgrade to Scala 3 (here) through some minor changes.

Some Other work

• Tests : Compile-time reduction of ASTs using Metaprogramming

Some Readings

• Scall1on
• Zippy LL(1) Parsing with Derivatives
• Scala3 Metaprogramming