Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
Don't both drawbacks pretty much exist without storing line and column numbers? I'm not understanding why they present a particular kind of problem. – psr Feb 26 '13 at 1:14

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.

share|improve this answer
I'm actually building a parser that doesn't have a separate tokenization phase! :) But either way, I don't understand how the location information is handled -- i.e. should the input token stream be pre-processed to add line/col to each? Or is it calculated as the parsing occurs, as a hidden state parameter (ala monad transformers)? Both seem to have drawbacks to me. – user39685 Feb 26 '13 at 0:03

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.

share|improve this answer
Hi DeadMG! Thanks for the response; however, I'm looking for information about parser combinators, and Bison seems to be something different. – user39685 Feb 26 '13 at 0:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.