1

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?

  • If I'm understanding your question correctly, you're asking how a syntax tree represents the implementation of functionCall() in its parsing of a line like int i = functionCall(); in addition to the fact that it's an invocation of that function, right? If so, I believe the answer is "it doesn't represent that at all; the part where function names are assigned meaning comes later in the compilation process". – Ixrec Nov 28 '15 at 12:11
  • thanks @lxrec, I added some additional stuff that hopefully makes my question clearer – NeomerArcana Nov 28 '15 at 12:17
  • 2
    What are you compiling into? Also, why do you think you need a concrete tree? – Telastyn Nov 28 '15 at 13:38
2

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/

  • The practical details of concrete syntax trees matter a lot (in particular, how they keep source location information, etc...) – Basile Starynkevitch Nov 28 '15 at 20:30
  • @Basile, interesting, can you give a bit more info? I guess I think of intermediate data structures as being able to keep source location information, and, say, debug information. – Erik Eidt Nov 28 '15 at 20:33
  • It is implementation specific, depends upon the language (does it has some C-like preprocessor) and on how precise you want it to be (e.g. do you want to generate debug information for DWARF, and which version) – Basile Starynkevitch Nov 28 '15 at 20:34
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.

  • 2
    good answer, but I think you are showing an abstract syntax tree. However, I must admit that I don't know why the OP is asking about concrete syntax trees... – Erik Eidt Nov 28 '15 at 20:22
2

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)

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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