A parser can convert a string to some data type. The first guess of the type of a parser would be:
type Parser<T> = (source: string) => T;
Since we will also use a parser to parse a part of the source. For instance, when parsing a factorial, we first parse the operand (which hopefully has one character remaining, the exclamation mark) and then parse the exclamation mark. Thus, a parser should return the resulting data and the remaining source:
type Parser<T> = (source: string) => [T, string];
A constant (such as 5.2) and a variable (5:2) both start with a number. Because of that, a parser should return an array with all options:
type Parser<T> = (source: string) => [T, string][];
To demonstrate how this works, imagine that there are two parsers: one that parses A
, one that parses AA
and one that parses AB
. The string AAA
could be parsed with a sequence of these parsers in three different ways: A-A-A
, A-AA
, and AA-A
. Now imagine...