This series presents the implementation of a parser combinator, step-by-step from scratch explaining how it works.
first, what is a parser combinator?
a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output.
the parser class
This class's object represents the simplest building block of the parser combinator.
class Parser {
constructor(fn) {
this.process = fn;
}
}
The constructor
function takes a function fn = fn(state) -> state
, where state
is the current state of the parser, and returns a new state.
chaining parsers
The core function is to "chain" parsers, so they can work in sequence, passing the state
to each other.
class Parser {
// ...
chain(parser) {
return new Parser(state => {
return parser.process(this.process(state));
});
}
}
The chain
method takes a parser as an argument, and return a new parser.
the #next
function
To be able to do further operations on the result of a parser, #next
method have been added to take the resulting state and operates on it.
class Parser {
// ...
#next(fn, onErr) {
return this.chain(
new Parser(state => {
return state.err ^ onErr ? state : fn(state);
})
);
}
}
It simply "chains" a new parser to the current one, which - depending on onErr
value - returns the state
that was passed to it as it is, or the state returned from fn
.
To simplify working with #next
, two method have been added.
operating on the state
The next
method works if there was no errors.
class Parser {
// ...
next(fn) {
return this.#next(fn, false);
}
}
catching errors
The error
method works if there was an error.
class Parser {
// ...
error(fn) {
return this.#next(fn, true);
}
}
running the parser
class Parser {
// ...
run(input) {
return this.process({ input, err: false });
}
}
Where input
is the input string to parse.
Well, that that doesn't look very useful right now, but in the next post, basic parsers will be implemented using the parser class, and finally they can be "combined" together to make larger parsers.
You can find the code on github on dev
branch
pari
A simple parser combinator.
usage
import { char, zeroOrMore } from 'pari';
// char takes a Regex that matches one character.
const charResult = char('[a-z]').run('s');
// parsers may take other parsers as arguments
const zomResult = zeroOrMore(char('[a-z]')).run('string');
available parsers
import {
char,
zeroOrMore,
sequence,
oneOrMore,
spaceArround,
separatedBy,
between,
zeroOrOne,
spaceBefore,
spaceAfter,
lazy
} from 'pari';
define your parser
import { Parser } from 'pari';
const myParser = new Parser(state => {
// do something with state
return newState;
});
// parser has three methods
someParser.chain(anotherParser); // chain another parser.
someParser.map(state => {
// do extra operations on the result.
…
Thanks for reading 😄.
Top comments (0)