Hacker News Reader

Comment by mrkeen | Hacker News Reader

> You could almost build an entire parser combinator library from scratch from memory, because none of the individual components are complicated.

I do this every now and then. Usually in the days leading up to advent of code.

"A parser is a function from an input to either failure or a (remaining input, result) pair" is all you need to remember to build the rest.

View on HN

I do this from time to time as well, although I tend to get hung up on error handling. I would say that it's a simple enough exercise if you don't care too much about reporting parse errors in a meaningful way, although I'd be happy for someone to point out an implementation of error handling that fits into one's head.

Here's the most basic error handling to implement, which I learned from studying FParsec:

1. Keep a collection of errors in the stream. It represents errors at the current position.

2. Clear all errors when input is consumed.

3. When a token-like parser fails without consuming input, push an "expected '<literal>'" error.

4. When a labeled parser fails without consuming input, restore the error set as it was before running it, and push an "expected <label>" error instead.

This will naturally accumulate errors from choice and repetition combinators, as long as you don't have needless backtracking before the choice points.

So this already gives you reasonable errors like "foo:17:4: expected one of expression, assignment or 'end'". And it's easy to extend to nested errors, backtracking information or recoverable nodes.

Reply on news.ycombinator.com