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(process) {
this.process = process;
}
}
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 provided that the status of the parser matches the given status, next
method have been added to take the resulting state and operates on it.
class Parser {
// ...
next(fn, status) {
return this.chain(
new Parser(state => {
return state.status & status ? fn(state) : state;
})
);
}
}
It simply "chains" a new parser to the current one, which - depending on status
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 ok
method works if the status
is OK
.
class Parser {
// ...
ok(fn) {
return this.next(fn, State.OK);
}
}
catching errors
The error
method works if there was an error.
class Parser {
// ...
error(fn) {
return this.next(fn, State.ERROR);
}
}
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 full code on github on main
branch
pari
More than a simple parser combinator.
install with npm
.
npm i pari
usage and basic parsers
you can read the source in src/
. it's self documenting and easy to read.
here is a simple overview.
import {
char,
firstOf,
sequence,
zeroOrOne,
oneOrMore,
zeroOrMore
} from 'pari';
// the `char` parser matches one char.
// it take a `regex` that matches exactly one char.
const digit = char('[0-9]');
// `firstOf` parser returns the first match in a list of parsers.
const lowerCase = char('[a-z]');
const digitOrLwcase = firstOf([digit, lowerCase]);
// `sequence` parser matches a list of parsers in sequence.
const hex = char('[0-9a-fA-F]');
const byteHex = sequence([char('0'), char('x'), hex, hex]
…
Thanks for reading 😄.
Top comments (0)