How are line/column position data dealt with in parser combinator libraries?

Question

I'm building a parser using a parser combinator library. I need to keep track of where AST nodes started and ended in the textual input -- line and column numbers.

How is this problem approached and/or what are strategies for dealing with it?

Clarification: I'm asking about how/when/where the line and column data is calculated. Two possible alternatives are 1) as an extra piece of state ala monads and monad transformers, that is updated whenever a token (character) is consumed, and 2) preprocessing the token stream to add the line/column to each one.

Drawbacks: 1) would result in the same work being done multiple times if there's backtracking. 2) would increase memory usage a lot if the entire input stream were done up-front.

Answer 1

The component that has the information about the textual location is usually the lexer, not the parser. Typically, you might attach the location (line/column) to the token itself, so that the parser can access the source location information when dealing with input tokens.

Answer 2

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.

Answer 3

I have constructed parsers with Bison. Typically, position data is dealt with by Bison providing a location type, where when providing a token you also fill this type out with location information. Then you may access this location value when a rule is reduced.

IOW: you give it to Bison per-token and then it gives it back to you per-rule.