How is it possible to store the AST nodes location in the source code?

Question

I created a simple parser in Rust and defined the AST like this:

enum Expression {
 Number(i32),
 BinaryOperator(Box<Expression>, Operator, Box<Expression>),
 Identifier(String),
}
enum ProgramLine {
 SetIdentifier(String, Expression),
 Print(Expression),
}
struct Program {
 lines: Vec<ProgramLine>,
}

I would like to keep information about where these nodes come from, so when there is an error, I can also report the line number.

How is it solved in parsers? My first idea is to add something line linenumber to each type, like this:

enum Expression {
 Number(i32, i32),
 BinaryOperator(Box<Expression>, Operator, Box<Expression>, i32),
 Identifier(String, i32),
}

But it does not seem right, because the AST should only represent the syntax tree of the language. But where should I store a context like this?

• Jörg W Mittag: Good question! Writing parsers and compilers with helpful, readable, useful, goal-directed error messages that guide the user towards diagnosing and fixing the problem is unfortunately not something that any of the "classic" compiler courses and books care about, so there is almost no documentation about it. As a user of Rust, you are already in the lucky position of being a member of a community that cares deeply about this, so I guess you could check out how rustc does it or talk to its developers?
• Jörg W Mittag: BTW, another thing that is generally ignored by all the classic books and courses is how to make the parser useful for something like syntax highlighting in an editor or refactoring support in an IDE, where the code you are parsing is by definition invalid since the user is still in the process of writing it, and where you have to parse small pieces of code a lot of times while the user is typing instead of parsing large pieces of code a few times, which is what parser benchmarks often focus on.
• amon: This source code information is often called a "source span". Instead of tracking line numbers, I'd track byte offsets + lengths into the source file (similar to built-in &str). You can recalculate the line + column number from that later. If you have multiple source files, the span must contain a reference/name/ID for the file.

Answer 1

Yes, you have described the standard approach.

Creating a raw text node type which has a line number, and then having others inherit from that might be attractive.

Error messages will typically want three items:

• file path
• source line number
• offset within line

Your approach suggests the first may be easy to get from context.

---

the AST should only represent the syntax tree of the language.

Ok, that's a fair perspective.

We don't have to store such details in AST nodes. We could say that "diagnostics happen seldom", and commit to re-parsing the file when reporting a diagnostic. This races with a developer's editor, which might Save updated text.

A middle approach would consult a global boolean, and only inflate the size of nodes when line tracking is enabled.