Parsing token lists.

Write direct-style parsers with effects, and combine them with choice, repetition, and backtracking.

Parser builds parsers over a list of tokens of any type: characters, numbers, or the tokens your own lexer produces. A parser is an ordinary function that performs the Parse token effect, so sequencing is just calling one parser after another and binding the results. There’s no monadic plumbing.

API reference: Parser

A first parser.

import Parser

type Token = Number Int | Comma | Open | Close deriving (Eq, Show)

number _ =
    case Parser.peek() of
        Just (Number n) ->
            _ = Parser.any()
            n
        _ -> Parser.fail "expected a number"

symbol name wanted _ =
    _ = Parser.token name wanted
    ()

numbers _ = Parser.between (symbol "(" Open) (symbol ")" Close) {
    Parser.sepBy number (symbol "," Comma)
}

main() =
    print (Parser.runAll [Open, Number 1, Comma, Number 2, Close] numbers)
    print (Parser.runAll [Open, Number 1, Number 2, Close] numbers)

Ok [1, 2]
Err (Error { offset = 2, expected = [")"], reason = Unexpected (Just (Number 2)) })

peek() looks at the next token without consuming it, and any() consumes one. token name wanted consumes a token equal to wanted, and satisfy name predicate one that the predicate accepts; either reports name as what it expected when the token doesn’t match. between and sepBy take parsers as Unit callbacks and combine them.

runAll tokens parser runs a parser over the whole input and fails if tokens remain. run parses a prefix instead and also returns the rest. A failure is an Error with the token offset, the descriptions that were expected there, and a reason: an unexpected token, Nothing at the end of input, or your own message from Parser.fail.

Choice and backtracking.

orElse first second tries second only when first fails without consuming input. Once a branch has consumed a token, it has committed, and its failure is the result. That keeps error messages close to the problem.

When a branch needs to look further ahead before committing, wrap it in attempt, which rewinds the input on failure:

Parser.orElse { Parser.attempt keyValue } { bareWord }

Only the parser’s own position is rewound. Any other effects a failed branch performed, such as printing, stay done.

optional returns Nothing on a non-consuming failure. many repeats a parser until it fails without consuming, and some requires at least one success. A repeated parser that succeeds without consuming anything would loop forever, so it fails with NonProgress instead, a grammar error that no combinator recovers from. label name parser replaces the expected descriptions with a single name, so errors can say expected a value rather than listing every alternative.

Larger parsers.

Because parsers are functions, a grammar is a set of mutually recursive definitions, and each nested runner is independent. Tokens can carry source spans for your own error rendering; offsets count tokens, not characters.

The Lisp example uses Parser for its reader, together with an evaluator and a multiline REPL.