Combinator parsing involves functions that take an input, consume some or none of the input, and then return inputs where the next parsing step can resume. These parser functions usually also return a value. Assuming the input is a string, this leads to the following signature:
type Parser<Value> = (String) -> Set<(Value, String)>
Usually, we require that the parser is unambiguous so that instead of a set we'd return an Option/Maybe type. To support meaningful parsing errors it would also be possible to return something like (Either<Value, Error>, String)
However, it is not necessary that the input is a string. Instead, the input could also be some richer data structure:
struct Input {
source: String,
offset: uint,
filename: String,
}
type Parser<Value> = (Input) -> Set<(Value, Input)>
For this particular example: when input is consumed, only the offset is changed, whereas the source string is left untouched. Alternatively but equivalently, all the parsing functions could just use the offset as input, and capture the source string as a closure.
Indeed, such a structure is used by many combinator parsing libraries such as Parsec by default. Instead of Input, terms such as Stream or Source might be used instead.
This has two consequences:
- We can provide an input that makes it possible to discover the line number and column of the current position. The input may track this explicitly, or only implicitly through the offset (lineno: count preceding newlines, col: count characters since the last newline). Of course, this information can be cached or pre-processed into a lookup table. If you only need location information in case there was an error, it can make sense to calculate line/col lazily.
- We can put location information into the values returned by the parsing function.
So the typical solution is more like your #1, but this does not lead to duplicated work. The location information isn't necessarily tracked as part of a monad, but it's threaded through the parsers represented by monads. However, Parsec in particular does treat this information as state that is tracked implicitly by the monad. The current input position can be accessed by methods that operate on this monad.
We do not pre-process tokens since combinator parsing is usually scannerless, so there are no tokens. We just naturally track location information as part of the input type. Of course, many combinator parsing libraries offer “primitive” parsers that return tokens of a particular type, and this type might also track source position by default.
You will also have to manually attach location information to the types your parser returns. Combinator parsing is agnostic to your data model, so you have to design a data model that retains sufficient information.