Parser Combinator Cheatsheet

Until you're more comfortable using parser combinators and have a sense for how to piece things together, the sheer choice can be daunting. This page is designed to help bridge this gap by bringing attention to some of the more common and useful combinators, as well as a few common idioms for getting stuff done.

Quick Documentation

This section is designed to give a quick reference for some of the most common combinators, their types as well as their use.

Basic Combinators

These are the basic combinators for combining smaller parsers into bigger parsers, or adjusting their results. These combinators are sometimes lazy in their arguments, which is denoted here by the regular by-name (=>A) syntax. If an argument is strict, it means that it will be parsed immediately on entry to the combinator before any input can be consumed.

Character Combinators

These combinators, found in parsley.character are useful for dealing with actually consuming input.

Lifty Combinators

These combinators can all be implemented in terms of lift2 (see liftN above), but are considered useful enough to have their own syntax and name. These combinators are lazy in their arguments (but not receivers),denoted here by the regular by-name (=>A) syntax. As such, the receiver is parsed first and may consume input, which means the argument may contain a recursive position (and must therefore be lazy).

Composite Combinators

These combinators tackle more common complex tasks. In particular many and some are very important. They are all found in parsley.combinator. These combinators are sometimes lazy in their arguments, which is denoted here by the regular by-name (=>A) syntax. Care should be taken with the combinators with variadic arguments, as they are totally strict, even in normally lazy positions: LazyParsley.unary_~ can be used to restore laziness in these positions.

Building Values and ASTs

This section covers the common ways you might build a result value or Abstract Syntax Tree (AST) with your parsers.

The most primitive combinators for reading input all have a tendency to return the thing they parsed, be it a single character or a string. For the most part, this is not the useful output you'd like your parser to have.

Transforming a single value with map

The quickest way to change the result of a parser is by using .map or the #> combinator (see the above quick documentation). This is really useful for changing the result of a single parser, but provides no way of combining multiple.

import parsley.Parsley, Parsley.some
import parsley.character.digit

case class Num(n: Int)

// A preferred method is to use `digit.foldLeft1` to avoid creating a List.
val digits: Parsley[List[Char]] = some(digit)
// `map` here is using a function of type `List[Char] => Int`
val int: Parsley[Int] = digits.map(_.mkString.toInt) // equivalently `digits.map(_.mkString).map(_.toInt)
// `map` here is being used to wrap the `Int` in the `Num` class
val num: Parsley[Num] = int.map(Num)

But when you need to combine the results of two parsers more options open up.

Combining multiple results with lift, <::>, and friends

Let's suppose we want to rule out leading zeros in the above parser. We'll need to read one non-zero digit before we read zero or more digits. In this case, we want the first digit to be added to the list of remaining digits. This task is quite common, so the <::> combinator is designed specially for it:

import parsley.Parsley, Parsley.many
import parsley.character.{digit, oneOf, char}

case class Num(n: Int)

val nonzero = oneOf('1' to '9')

// <::> adds the leading non-zero char onto the other digits
val digits: Parsley[List[Char]] = nonzero <::> many(digit)
// Using #> here to handle the plain ol' zero case
val int: Parsley[Int] = char('0') #> 0 | digits.map(_.mkString.toInt)
val num: Parsley[Num] = int.map(Num)

But more generally, we could reach for the lift functions:

import parsley.Parsley, Parsley.many
import parsley.character.{digit, oneOf, char}
import parsley.lift.lift2

case class Num(n: Int)

val nonzero = oneOf('1' to '9')

val digits: Parsley[List[Char]] = lift2[Char, List[Char], List[Char]](_ :: _, nonzero, many(digit))
// Using #> here to handle the plain ol' zero case
val int: Parsley[Int] = char('0') #> 0 | digits.map(_.mkString.toInt)
val num: Parsley[Num] = int.map(Num)

Sadly, to do this, it's sometimes necessary to specify all the types, in particular for anonymous functions that can have many possible type-instantiations, like _ :: _. The reason is that Scala doesn't infer the types of arguments, only return values, so on its own _ :: _ has no known type. As such, the fix is to let other type-instantations help give the argument types (as above) or to specify the types in the function manually:

lift2((c: Char, cs: List[Char]) => c :: cs, nonzero, many(digit))

Notice that this didn't seem to be a problem with map. This is because the function is type-checked after the receiver of the method: it gets given the right argument type straight away. Parsley has a syntax for leveraging this property:

import parsley.syntax.zipped.zippedSyntax2

(nonzero, many(digit)).zipped(_ :: _)

Use this form of lifting when type-inference fails you. Otherwise, for clarity, use a regular liftN, or the syntactic sugar for it:

import parsley.syntax.lift.{liftSyntax1, liftSyntax2}

val charCons = (c: Char, cs: List[Char]) => c :: cs

charCons.lift(nonzero, many(digit))
Num.lift(int)

The lift functions work all the way up to 22 arguments (which is a JVM limit). The same goes for the zipped syntax and lift syntax. Don't forget about <::> as well as its friends <~>, <*>, and <**>! They all provide a concise way of combining things in (common) special cases.