What data structures are used to represent source code by programs that do source-to-source transformations?

Question

For programs that read in source code, transform that source code, and then write back out the transformed source code so that it can be read and edited by humans, what sorts of data structures are typically used for representing source code with all its textual details? Is there a standard "textbook" data structure for this? (e.g. something analogous to the AST for more traditional parsing)

Some examples of the types of programs I have in mind are the many clang-based tools for transforming C and C++, the Python tools for translating Python 2 to Python 3, and the many tools for transforming Go.

I guess the answer could be as simple as an AST with extra-data (e.g. whitespace, parenthesis) on the non-leaf nodes but I'm not sure. It seems like it could be more complicated since the structure needs to negotiate the tension between maintaining textual details and allowing for high-level source code transformations.

Answer 1

I think you may be interested in Concrete Syntax Tree (aka Parse Tree) vs. Abstract Syntax Tree.

The concrete syntax tree captures minute detail of the parsers comprehension of the grammar as applied to the input source code. In particular, keywords, parenthesis, whitespace that are normally removed would be present in a Concrete Syntax Tree.

(If a scanner or tokenizer is used, capturing of whitespace may or may not be lost to the parser; a parser that works directly on text (e.g. without a scanner) will necessarily see very character.)

Parsers manifest the concrete syntax structure with internal state. Some parsers will output all those details, while others instead output only abstracted versions. Concrete syntnax trees are considerably larger than the abstract syntax trees for the same source.