Parsley

What is Parsley?

Parsley is a very fast parser combinator library for Scala based on a Haskell-style Parsec API.

How do I use it?

Parsley is distributed on Maven Central, and can be added to your project via:

libraryDependencies += "com.github.j-mie6" %% "parsley" % PARSLEY_VER

Documentation can be found here

Examples

import parsley.Parsley, Parsley._
import parsley.character.{char, string, digit}
import parsley.implicits.{charLift, stringLift}

val hello: Parsley[Unit] = void('h' *> ("ello" <|> "i") *> " world!")
hello.parse("hello world!") // returns Success(())
hello.parse("hi world!") // returns Success(())
hello.parse("hey world!") // returns a Failure

val natural: Parsley[Int] = digit.foldLeft1(0)((n, d) => n * 10 + d.asDigit)
natural.parse("0") // returns Success(0)
natural.parse("123") // returns Success(123)

For more see the Wiki!

What are the differences to Haskell's Parsec?

Mostly, this library is quite similar. However, due to Scala's differences in operator characters a few operators are changed:

• (<$>) is known as <#> or map
• try is known as attempt
• (<$) and ($>) are <# and #> respectively.

In addition, lift2 and lift3 are uncurried in this library: this is to provide better performance and easier usage with Scala's traditionally uncurried functions. There are also a few new operators in general to be found here!

How does it work?

Parsley represents parsers as an abstract-syntax tree AST, which is constructed lazily. As a result, Parsley is able to perform analysis and optimisations on your parsers, which helps reduce the burden on you, the programmer. This representation is then compiled into a light-weight stack-based instruction set designed to run fast on the JVM. This is what offers Parsley its competitive performance, but for best effect a parser should be compiled once and used many times (so-called hot execution).

To make recursive parsers work in this AST format, you must ensure that recursion is done by knot-tying: you should define all recursive parsers with val and introduce lazy val where necessary for the compiler to accept the definition.

Bug Reports

If you encounter a bug when using Parsley, try and minimise the example of the parser (and the input) that triggers the bug. If possible, make a self contained example: this will help me to identify the issue without too much issue.

References

• This work is based on my Master's Thesis (2018) which can be found here
• This work spawned a paper at the Scala Symposium at ICFP 2018: Garnishing Parsec with Parsley