How are individual lines of code and functions stored in a Concrete Syntax Tree?

Question

I'm trying to write a simple compiler for learning purposes. I've been reading the Dragon Book and Modern Compiler Design and one part I don't understand is how the Concrete Syntax Tree is actually created and stored.

I understand that by looping through the Tokens produced by the Lexer it's a simple matter to collect all the pieces of an assignment operator; for example:

int i = 0;

is pretty straight-forward to collect the type, identifier and that we're assigning a value of const_number zero. And I understand how this concrete syntax tree looks like.

And if it's assigned like an expressions like:

int i = a * b;

I also understand what this concrete syntax tree would look like.

But then let's say I have:

int i = functionCall();

What does this look like in a concrete syntax tree?

And further, considering a language like C that's a bunch of functions, with one of them, the main function being denoted as the entry point; how does this all fit into a concrete syntax tree?

Does each one have its own tree?

The creation of a heirarchy of Node types for my tree, each with the specific components it needs makes sense to me; but not how this factors in function calls; unless every single function was inlined.

Additional Info from Comments

So, say I have some code that looks like:

int AddProc(int i, int j)
{
    return i + j;
}

void main()
{
    int x = 8;
    int y = 0;
    int z = x + y;
    x = AddProc(y,z);
}

The Token stream starts from the top to the bottom; simple; each token tells the Parser if it's a TYPE or ID or CONST or ADD_OP whatever. The first stage of the parser is to produce a Concrete Syntax Tree, that's then turned into an Abstract Syntax Tree.

My question is what does the Concrete Syntax Tree look like for the above; and further, the AST as well?

Answer 1

Concrete syntax trees follow directly from the grammatical production rules of the language (i.e. its grammar). They are complex, wordy and offer little benefit for the next phases of the compiler (analysis and code generation).

I don't think that most compilers represent or store concrete syntax (let alone concrete syntax trees), concrete syntax is at best manifest within the parsing algorithm itself (for example, sometimes using recursion); generally on successfully parsing something the parser generates some intermediate data structure, and if that is a tree, it is likely more reflective of an abstract syntax tree.

Look at the diagram for the "Parse Tree" in this answer and https://stackoverflow.com/a/10176731/471129 , and compare with the AST further on in @Guy's answer.

http://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees/

Answer 2

If your code contains a line like

x = AddProc(y,z);

then the syntax tree for that expression would look similar to this:

       assignment
      /          \
    ID(x)  FunctionCall(AddProc)
                /      \
              ID(y)   ID(z)

One important thing to note is that the implementation of AddProc is not part of this syntax tree. Instead, the systax tree for the complete program will have a separate syntax sub-tree for the definition of AddProc.

In languages like C, where programs can be spread over multiple files and contain multiple functions, the compiler will create a separate syntax tree for each file, which in turn contains separate sub-trees for each declaration and definition that is found at file level.
For the creation of syntax trees, the main function is not considered to be special. This function only gets some special treatment when checking the program for errors and when generating code.

Answer 3

In practice, compilers keep some abstract syntax tree (perhaps several sorts of them, e.g. both typed and untyped ASTs) with additional meta-information (e.g. source position as a filename + line, etc...). That meta-information could be kept inside trees or outside them. And most compilers also maintain some symbol table.

So your "concrete syntax tree" is often some initial form of the AST decored with some initial meta-data.

Did you look into the implementation of concrete compilers like Ocaml, GCC, Clang, etc...? Did you consider compiling to C, to LLVM, to GCCJIT, etc...? The devil is in the details !

For GCC, my documentation page of GCC MELT contains links to a lot of other sites and hundreds of slides explaining more details. Read also the GCC internals documentation, notably chapters on GENERIC trees and on GIMPLE.

Notice also that most compilers have numerous passes (GCC has several hundreds of them) and a pass is transforming some internal representation (often such a decorated AST) into some other one (often, but not always, the source and target IR has similar types; Ocaml has both typeless trees and typed trees after the type inference pass).

^{(there is no a single universal answer to your question(s); it is a matter of opinion, of source language, of target language, of objectives -ease of error recovery during compilation-, etc...; you might care about debug info, e.g. in DWARF!)}

If you are fluent in Lisp or Scheme, consider reading C.Queinnec's book Lisp In Small Pieces (which gives several implementations of Lisp and the theory behind them). Read also Scott's Programming Languages Pragmatics

Often, a compiler would canonicalize or simplify some AST, e.g. into A-normal form or CPS form (or transforming a for loop in C into something simpler with while or if & goto)

Of course, you'll learn a lot by studying the source code of several free software compilers and interpreters, and by coding your own compiler (perhaps targeting C, or Javascript, or LLVM, or GCCJIT, or libjit...); the structure of the target language and the source language may dictate the transformations and the internal representations of your compiler.

Read about semantics (operational semantics, denotational semantics, types & programming languages ....) & about undefined behavior (notably, what every C programmer should know about UB)

Answer 4

The concrete syntax tree is an early step in the compilation process, and it only contains the information from the lexical level. The node for a function call does not "know" anything about the function that is called or even if it exists at all.

At later stages it will be verified if the identifier is the name of a function declared somewhere else in the program, that the types of the parameters matches the argument at the call site and so on. But these semantic checks happens at a later stage, and is not present in the syntax tree.