Introduction to FootlessParser
This post is part of a series on FootlessParser, a parser combinator written in Swift.
The goal is to define parsers like this:
let parser = function1 <^> parser1 <*> parser2 <|> parser3
where parser will pass the input to parser1 followed by parser2, pass their results to function1 and return its result. If that fails it will pass the original input to parser3 and return its result.
Terms
- Parser
- a function which takes some input (a sequence of tokens) and returns either the output and the remaining unparsed part of the input, or an error description if it fails.
- Token
- a single item from the input. Like a character from a string, an element from an array or a string from a sequence of command line arguments.
- Parser Input
- most often text, but can also be an array or really any collection of anything, provided it conforms to CollectionType.
First version
Initially FootlessParser will be the simplest possible implementation of a parser combinator in Swift. It will:
- have at least rudimentary error reporting, because it makes writing parsers so much easier.
- not parse ambiguous grammars. Each parser will return at most one result, not a list of all possible results.
- not handle left recursion. Like most parser combinators.
- probably be slow. It’s going to be very interesting to see how slow.
Future improvements
- Memoization, should help with speed.
- Left recursion.
- Ambiguous grammars (maybe).
- SequenceType as input.
Comments