Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

2 Answers 2

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. –  Matt Fenwick 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. –  Matt Fenwick Feb 26 '13 at 0:00

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.