Designing Domain Specific Languages with Parser Combinators

TL;DR — Parser combinators let you compose tiny, reusable parsers into a full‑featured DSL without writing a hand‑crafted lexer or grammar generator. By treating parsers as first‑class functions, you gain modularity, testability, and expressive power that scales from simple configurations to complex query languages.

Designing a domain‑specific language (DSL) often feels like walking a tightrope between expressive power and implementation complexity. Traditional approaches rely on lexer/parser generator tools such as ANTLR or Bison, which introduce separate grammar files, code generation steps, and often opaque error handling. Parser combinators flip that model on its head: they are ordinary functions that you combine with combinators like choice, many, and sepBy to describe the syntax directly in your host language. This article walks you through the theory behind parser combinators, shows step‑by‑step how to design a DSL, and demonstrates concrete implementations in Haskell (using Parsec) and Python (using parsy). By the end you’ll have a reusable toolkit for turning textual specifications into executable abstractions.

Understanding Parser Combinators

What Are Parser Combinators?

A parser combinator is a higher‑order function that takes one or more parsers as arguments and returns a new parser. In functional terms, a parser can be modeled as a function Parser a = String -> [(a, String)], where it consumes a portion of the input and produces a value of type a together with the remaining unparsed string. The combinator builds more complex parsers by sequencing, branching, or repeating these basic units.

Key advantages:

For a concise theoretical treatment, see the classic paper “Monadic Parser Combinators” by Hutton and Meijer (1997). The authors show how the monadic interface (>>=) enables backtracking and sequencing with minimal boilerplate.

Core Combinators

Below is a minimal set of combinators you’ll encounter in most libraries:

• char :: Char -> Parser Char – matches a single character.
• string :: String -> Parser String – matches a literal sequence.
• choice :: [Parser a] -> Parser a – tries each parser in order, returning the first success.
• many :: Parser a -> Parser [a] – parses zero or more repetitions.
• sepBy :: Parser a -> Parser sep -> Parser [a] – parses a list separated by a delimiter.
• try :: Parser a -> Parser a – allows backtracking even after consuming input.

A typical Haskell definition of sepBy looks like this:

sepBy :: Parser a -> Parser sep -> Parser [a]
sepBy p sep = (p `sepBy1` sep) <|> pure []
  where
    sepBy1 x s = liftA2 (:) x (many (s *> x))

The same idea appears in Python’s parsy library:

import parsy

def sep_by(p, sep):
    return p.sep_by(sep)

Understanding these building blocks is the foundation for designing a DSL that feels natural to both the language author and its users.

Designing a DSL: Step‑by‑Step

When you set out to create a DSL, treat the design process as a series of incremental refinements. Below is a practical workflow that can be applied regardless of the host language.

1. Define the Domain Vocabulary

Start by listing the concepts you need to express. For a hypothetical task‑automation DSL, you might have:

• Commands – run, copy, delete.
• Resources – file paths, URLs, environment variables.
• Control flow – if, else, repeat.
• Metadata – comments, annotations.

Write these as plain English sentences, then distill them into a concise grammar sketch. For example:

statement   ::= command arguments
command     ::= "run" | "copy" | "delete"
arguments   ::= path ( "->" path )?
path        ::= quotedString | identifier

2. Choose the Host Language and Library

Pick a language that already excels at functional composition. Haskell’s Parsec and Megaparsec are battle‑tested; Scala developers often reach for FastParse; Python users appreciate parsy or lark with a combinator façade. The choice influences syntax style but not the underlying combinator concepts.

3. Encode Primitive Parsers

Implement parsers for the smallest tokens: identifiers, literals, whitespace, and comments.

Haskell Example

import Text.Parsec
import Text.Parsec.String (Parser)
import qualified Text.Parsec.Char as C
import qualified Text.Parsec.Token as Tok

lexer :: Tok.TokenParser ()
lexer = Tok.makeTokenParser Tok.LanguageDef
  { Tok.commentLine = "#"
  , Tok.identStart = letter <|> char '_'
  , Tok.identLetter = alphaNum <|> oneOf "_'"
  , Tok.reservedNames = ["run","copy","delete","if","else","repeat"]
  , Tok.reservedOpNames = ["->"]
  , Tok.opLetter = oneOf ":!#$%&*+./<=>?@\\^|-~"
  , Tok.caseSensitive = True
  }

identifier :: Parser String
identifier = Tok.identifier lexer

quotedString :: Parser String
quotedString = Tok.stringLiteral lexer

reserved :: String -> Parser ()
reserved = Tok.reserved lexer

symbol :: String -> Parser String
symbol = Tok.symbol lexer

whitespace :: Parser ()
whitespace = Tok.whiteSpace lexer

Python Example

import parsy

whitespace = parsy.regex(r'\s*')
identifier = parsy.regex(r'[A-Za-z_][A-Za-z0-9_]*')
quoted_string = parsy.regex(r'"(?:\\.|[^"])*"').map(lambda s: s[1:-1])
comment = parsy.string('#') >> parsy.regex(r'.*')

4. Build Composite Parsers

Combine primitives using combinators to reflect the grammar sketch.

Haskell Composite

commandParser :: Parser String
commandParser = choice $ map reserved ["run","copy","delete"]

pathParser :: Parser String
pathParser = quotedString <|> identifier

arrow :: Parser ()
arrow = void $ symbol "->"

argumentsParser :: Parser (String, Maybe String)
argumentsParser = do
  src <- pathParser
  mDst <- optionMaybe (arrow *> pathParser)
  return (src, mDst)

statementParser :: Parser (String, (String, Maybe String))
statementParser = do
  cmd <- commandParser
  args <- argumentsParser
  return (cmd, args)

Python Composite

arrow = parsy.string('->').result('->')

path = quoted_string | identifier

arguments = (path << whitespace).bind(
    lambda src: (arrow >> whitespace >> path).optional().map(
        lambda dst: (src, dst)
    )
)

command = parsy.string('run') | parsy.string('copy') | parsy.string('delete')

statement = (command << whitespace).bind(
    lambda cmd: arguments.map(lambda args: (cmd, args))
)

5. Add Control Flow Constructs

For richer DSLs, introduce branching and loops. The key is to keep each construct isolated in its own parser, then use choice to assemble the top‑level language.

ifParser :: Parser AST
ifParser = do
  reserved "if"
  cond <- expressionParser
  thenBlock <- blockParser
  elseBlock <- optionMaybe (reserved "else" >> blockParser)
  return $ If cond thenBlock elseBlock

In Python the same idea looks like:

if_parser = (
    parsy.string('if') >> whitespace >> expression <<
    whitespace >> block
).combine_dict(lambda cond, then_block: {"type": "if", "cond": cond, "then": then_block})

6. Wire Up the Top‑Level Parser

Finally, expose a single entry point that consumes an entire script, handling whitespace and comments globally.

scriptParser :: Parser [Statement]
scriptParser = whitespace >> many (statementParser <* optional (char ';')) <* eof

script = whitespace >> (statement.sep_by(parsy.string(';') >> whitespace)).skip(parsy.eof)

7. Test Incrementally

Because each parser is a pure function, you can write unit tests with minimal scaffolding:

-- Using Hspec
it "parses a copy command with arrow" $ 
  parseTest statementParser "copy \"src.txt\" -> \"dst.txt\""

def test_copy():
    assert statement.parse('copy "src.txt" -> "dst.txt"') == ('copy', ('src.txt', 'dst.txt'))

Running these tests after each new construct guarantees that the DSL evolves without regressions.

Implementing with Popular Libraries

Below we compare three widely‑used parser combinator ecosystems, highlighting idiomatic patterns and performance considerations.

Haskell – Parsec / Megaparsec

• Strengths: Mature, excellent error messages, monadic and applicative interfaces, strong type inference.
• Typical Use‑Case: Compilers, static analysis tools, and any project where compile‑time guarantees matter.
• Performance: Megaparsec adds SIMD‑based optimizations and better error reporting; it can parse megabytes per second on modern hardware.

Sample Megaparsec snippet

import Text.Megaparsec
import Text.Megaparsec.Char

type Parser = Parsec Void Text

identifier :: Parser Text
identifier = takeWhile1P (Just "identifier") isAlphaNum

runCommand :: Parser Command
runCommand = do
  _ <- string "run"
  space1
  path <- quotedString <|> identifier
  pure $ Run path

Scala – FastParse

• Strengths: Zero‑allocation parsing, seamless integration with Scala’s implicits, macro‑based compile‑time checks.
• Typical Use‑Case: DSLs embedded in JVM applications, data‑pipeline configuration languages.
• Performance: Benchmarks show FastParse can surpass hand‑written recursive descent parsers for many grammars.

FastParse example

import fastparse._, NoWhitespace._

def identifier[_: P]: P[String] = P( CharIn("a-zA-Z_") ~~ CharIn("a-zA-Z0-9_").rep ).!
def quotedString[_: P]: P[String] = P( "\"" ~~ CharsWhile(_ != '"', min = 0).! ~~ "\"" )
def command[_: P]: P[String] = P( StringIn("run", "copy", "delete") )
def statement[_: P]: P[Stmt] = P( command ~ whitespace ~ (quotedString | identifier).rep(sep = "->".?) ).map {
  case (cmd, args) => Stmt(cmd, args)
}

Python – parsy

• Strengths: Very lightweight, pure Python, easy to read for newcomers, integrates with asyncio for streaming inputs.
• Typical Use‑Case: Configuration file parsers, prototyping DSLs, educational tools.
• Performance: Not as fast as compiled alternatives, but sufficient for scripts and moderate‑size inputs.

Full Python parser

import parsy

# Primitive tokens
ws = parsy.regex(r'\s*')
ident = parsy.regex(r'[A-Za-z_][A-Za-z0-9_]*')
quoted = parsy.regex(r'"(?:\\.|[^"])*"').map(lambda s: s[1:-1])
arrow = parsy.string('->').result('->')

# Composite
path = quoted | ident
args = (path << ws).bind(
    lambda src: (arrow >> ws >> path).optional().map(
        lambda dst: (src, dst)
    )
)

command = parsy.string('run') | parsy.string('copy') | parsy.string('delete')
statement = (command << ws).bind(lambda cmd: args.map(lambda a: (cmd, a)))

script = ws >> statement.sep_by(parsy.string(';') >> ws) << ws << parsy.eof

Testing and Debugging Strategies

Even though parser combinators are expressive, they can become opaque when a complex grammar fails. Here are proven tactics:

1. Layered Unit Tests – Test each primitive (identifier, quotedString) before the composites. Use property‑based testing (e.g., QuickCheck for Haskell, Hypothesis for Python) to generate random valid/invalid inputs.

2. Labelled Errors – Most libraries let you attach custom error messages with <?> (Parsec) or label (FastParse). Example:

   identifier = (letter <|> char '_') *> many alphaNumChar <?> "identifier"
   

3. Parse Tracing – Enable debug output. In Megaparsec:

   import Text.Megaparsec.Debug (dbg)
   debugParser = dbg "statement" statementParser
   

4. Visualise the Parse Tree – Convert the AST to a pretty‑printed JSON structure. This helps spot mismatched branches early.

5. Incremental Parsing – For large scripts, parse line‑by‑line or use a streaming combinator (manyTill) to keep memory usage low.

Key Takeaways

• Parser combinators treat parsers as first‑class functions, enabling modular, composable DSL definitions without external grammar files.
• Start with a clear domain vocabulary, then map each concept to a small primitive parser before building higher‑level constructs.
• Choose a library that matches your ecosystem: Parsec/Megaparsec for Haskell, FastParse for Scala, parsy for Python, each offering idiomatic combinators and good error handling.
• Write exhaustive unit tests for each parser layer; property‑based testing catches edge cases that hand‑crafted examples miss.
• Leverage library features for debugging—labelled errors, tracing, and AST visualisation dramatically reduce the time spent on malformed inputs.
• The same combinator patterns scale from simple configuration files to full‑blown query languages, making them a versatile tool in any language‑design toolbox.

Further Reading

• Parsec documentation (Hackage)
• FastParse – Scala combinator parsing library
• parsy – Simple parser combinators for Python
• “Monadic Parser Combinators” by Hutton & Meijer
• Megaparsec – A modern Haskell parsing library