Does compiler AST include functions and classes?

Question

In most of the examples for Abstract Syntax Trees (AST), I see no function or classes.

I am wondering, if the functions and classes are represented in the AST? If no, where should the functions, classes and templates be stored? What is the possible data structure representation for the code?

I was thinking about

struct SourceModule
{
    AST ast;
}

or

struct SourceModule
{
    std::vector<AST> ast;
}

or

struct SourceModule
{
    std::vector<AST> ast;
    std::vector<Class> classe_list;
    std::vector<Function> function_list;
}

By AST example, I mean something like this:

Answer 1

I am wondering, if the functions and classes are represented in the AST?

Certainly!

What is the possible data structure representation for the code?

It depends on the language you're parsing, so look at its grammar.

Some languages have a single, well-defined top-level construct, like "program" — you might find this in some version of Pascal, for example.  For those you only need a single program-type node to represent the whole source unit.

Otherwise, you will need a collection oriented construct at the top level — it will look similar to what you would do for compound statements (e.g. { ... } as a group of statements collected into a single statement).  Perhaps, a single node that holds a list of declarations (e.g. types, data, or functions).

In other languages, sequential constructs are wrapped in a sequence node that only has two children (e.g. a left and a right), so to collect multiple statements or functions or constructs, the AST looks more like a linked list of other items.

But look to your grammar to identify what the top-level construct is.  It may allow a series of declarations, for example, then you want an AST node that represents that.

---

An AST should reflect the grammar, but of course, since is abstract, it will not exactly do so, usually by omission — for example, a typical AST will not include nodes for parenthesis or intermediate productions(intermediate recognition), since the tree structure itself captures operator argument binding (having applied the appropriate operator precedence to operands during parsing).

On the other hand, a parse tree (aka concrete syntax tree) would probably reflect the grammar quite closely, including nodes for parenthesis, intermediate productions, keywords, etc..

As the parse tree is so verbose, it can be used to provide error messages that have an exactness regarding original source line and column.

Answer 2

An AST, in my experience, is exactly that: an "abstract syntax tree." Nothing more, and nothing less.

The "back end" of the compiler never actually sees nor deals with the source-code. The parser presents trees ... ASTs ... and this is what it works with.

However, one might rightly say that "ASTs are equivalent to source-code." They go no farther. They represent nothing more nor less than what a particular segment of source-code "meant." Anything which the compiler might deduce from this ... list of functions, list of classes, list of templates, whatever ... is the compiler's concern, not the AST's. As the back end of the compiler is presented with one AST-segment after another after another, it will "deduce" this ancillary information. But the parser and its associated ASTs will have no part of this other than to provide raw input.

Answer 3

Generally, languages have a separate declaration or signature parser since that is often needed independently from the body of classes or functions. They’re then often stored in some lookup table, whose structure will vary based on the common usage patterns of the language - potentially different ones since autocomplete has different needs, compared to a repl, compared to a full compiler. What module system the language uses can influence this strongly as well.

One thing to also think about is languages with first class functions or anonymous functions. Since those can usually be written as expressions, they will usually show up in ASTs.