Comment by mrkeen
16 hours ago
Not a good starting type:
type Parser<T> = (input: string) => [T, string]
This implies that it accepts a string and will return a T. Parsers might return a T.
The article also starts with the concept of a 'partial parser', from which other (non-partial?) parsers can be constructed?
Or, and this is where the real power of partial parsers comes in: we wrap the chain up as a new parser of its own.
Nope, there's no distinction. If you combine partial parsers, you end up with a partial parser. If you combine full parsers (whatever that means) you end up with full parsers.
(Ironically there is a fitting definition of 'partial' here: the function isn't well defined on all inputs. For some inputs, T is returned, on other inputs, maybe an error is thrown, who knows..)
Good input. Since we're working in typescript a partial parser can always throw an exception (It's what the parsimmon library does aswell I believe). I decided not to get into those technicalities too much!
> If you combine partial parsers, you end up with a partial parser.
If by partial we mean the parser can fail, not necessarily. optional(elem) and repeat(elem) are total if elem doesn't consume input on error, at least for a reasonable semantics of parser combinators (although we usually consider it a programmer error if elem matches the empty string in repeat(elem)).
No, that was my ironically landed upon definition of partial.
The article used it as in a sub-parser, which is the other thing I objected to. If you add two Integers, you get back an Integer, not a Sum. Same principle here, two parsers make a parser. You don't need to write new code to combine a partial parser with a parser, or vice versa.
Combinators are functional—they always return something. But if you want to return nothing, fine; T is any type. Just return something like unit (ie, the singleton type that has nothing as a value).
There are three return states that a parser (or partial parser) can return:
1. an item (`T`) for a successful parse;
2. an error (`ParseError`) for an unrecoverable parse error;
3. a partial item (`T with ParseError`) for a recoverable parse error or warning (known statically).
You may also want to differentiate between:
1. leaf nodes (numbers, identifiers, string literals, etc.);
2. composite/nested nodes (addition, multiplication, variable assignment, etc.).
You don’t need 2 and 3. You can express them just with with T. For example, you could use an Either type for “good, here’s your value/bad, here’s your error.” If you want to get more sophisticated, you can add a type with extra error cases. In my own combinator libraries, I also include extra failure information to make diagnosing failed parses easy (and to generate pretty output). This does not change the fact that T is sufficient.
2 replies →
T is not any type, T is a type defined at compile time, and usually checked against the parser’s implementation.
If you always define T as some useful stuff or unit, your experience with parser combinators and their composition is going to be miserable.
> T is not any type, T is a type defined at compile time,
This is a distinction without a difference. In a static, type-safe language, T always has to be instantiated with a type. But that does not change the fact that, from the perspective of the function definition, T is any type. T must be a specific type for the function call.
3 replies →
If you use an Either instead of a List, then you can write an or combinator, which accepts two parsers and tries the second if the first fails. It branches on the Left/Right of the Either.
If it's a List, wouldn't you be forced to write the Cartesian product of two parsers instead?
1 reply →
[dead]