Why do compilers typically convert code into abstract syntax/parse trees before the final product?

I never found the need to produce an intermediate representation before the final output.

Well then, you go!

what is the purpose of producing an intermediate representation such as a tree before producing the final product?

Your assumption is that the "final product" is machine code. Historically, that's spot on; by definition, a compiler is a program which takes in a string in one language and produces a semantically equivalent string of another language. If you can do that in one pass, great. (Bonus points if you can also produce sensible, actionable error messages when given an incorrect program.)

But that definition is no longer sufficient. A modern compiler provides multiple services. Translation is perhaps the most important service, but it is far, far from the only one. We designed Roslyn -- the C#/VB compiler architecture -- to be able to answer any question an IDE might reasonably have about code:

• How should this fragment be coloured?
• What is the type of this expression? Where is the declaration for that type, either in source or metadata?
• If we performed an introduce-explanatory-variable refactoring, what would the resulting code look like? Would doing so introduce a new error?
• If the dev has just typed "Console.W" in the IDE, what's the most likely completion?

And so on and so on and so on. And by the way all these questions must be answered about code that is syntactically wrong, as the user is typing in an editor, and the analysis must happen faster than the user can type; we budgeted 30 milliseconds maximum for a service call to return.

A lex and parse tree are in my experience necessary but insufficient to answer many of these questions. Reducing the parse tree to a lazily-computed semantic tree within a tight performance budget was the bulk of my work from 2005 to 2012. If you've got a better way to do that than building a syntactic or semantic tree I would love to know what it is!

How could it not take on an intermediate form? That's actually rather tricky. Consider this fragment:

x + y...

What bytecode do you emit? Perhaps it's loading the value of x, then loading the value of y then adding them? What happens next?

x + y * 2

How unfortunate is that. Given that you've added x and y already, how will you recover? Perhaps you're clever and load y and add it again. But what if it was

x + y * z

Now you're trapped. You really needed something to hold onto the "x +" bit for a while, so that you can look ahead to see if there's a multiplication. A stack would do. And while it may not be immediately obvious, that's a intermediate representation. It's a stepping stone between the written text and the final output.

I point this out because there's nothing special about an intermediate representation. Every non-trivial program (i.e. more than one instruction) has some intermediate representation for the final output. Some are closer to the text than others, but they're all intermediate representations.

The more complex the application, the more complex its intermediate representations tend to be. Compilers are typically pretty darn complex. It turns out to be very convenient to be able to split up the problem they solve into smaller parts. The intermediate representations you are thinking of are the middle steps before the final output. They are typically chosen to have nice properties. They might strip strings that are no longer needed, or mark the lifespan of objects. They have properties that make it easier to write the next layer.

Yes, you can in theory do it in "one step." You still have an intermediate form, it's just in a far more difficult format to work with or prove. As you work with more complicated compiling tasks, it starts to be nice to not force yourself to work harder when you don't have to.

And, in the end, you still ended up with an intermediate representation, even if you somehow went from text to machine code in one step. There's not an x64 CPU today which actually executes x64 machine code. All of them treat the machine code as an intermediate representation and turn it into processor-specific microcode before executing that!

You may also be interested in the cut-elimination theorem from proof theory. The mathematical operation of a "cut" in proof theory is very close to the idea of intermediate representations. Formally, it says if you can prove $A\to B$ and $B\to C$, there exists a proof that $A\to C$ is also true. $B$ looks a lot like an intermediate representation, if you ask me. The cut-elimination theorem guarantees that if there is a proof that uses this "cut" rule, there must also exist a cut-free rule (lacking such intermediate representations).

In his essay "Don't Eliminate Cut!" George Boolos demonstrated that there was a derivation that could be completed in a page using cut, but whose analytic proof could not be completed in the lifespan of the universe.

Intermediate representations are a pretty nifty idea!

what is the purpose of producing an intermediate representation such as a tree before producing the final product?

Compilers have to parse the source code and produce machine code. Those responsibilities are often broken into a "front end" (the parser) and a "back end" (object code generator). Optimizing compilers might perform optimization as a separate phase after parsing and before code generation, sometimes called the "middle end." Intermediate representations are how the information is passed from one end to the next.

Having intermediate representations helps with separation of concerns. If the job of the front-end parser is to translate the source into an intermediate representation, then you could swap in another implementation of the front-end for a different source language, and (ideally) not have to re-write the optimizer or the code generator. Likewise, you could swap the back-end to generate code for a different target processor.

This separation also makes it easier to test and debug the compiler itself. Suppose you come across a program that, when fed to the compiler, produces bad object code. Where's the bug? Instead of trying to step through the compiler end-to-end, you could check the intermediate representation after the front end and after the middle end to figure out whether it's a bug in the parser, the optimizer, or the final code generation.

With the main steps of the pipeline separated, you can create test cases that exercise targeted portions of the compiler. For example, you could write a test that feeds a certain input (in the form of the intermediate representation) into the optimizer and that checks that its output (also as intermediate representation) is correct. The test would depend only on the optimizer code, not on the parser or the code generation.

A parse tree or abstract syntax tree is usually just one of the first intermediate representations in a compiler. At various phases, it may be convenient to have a control flow graph, a data flow graph, a series of instructions for an abstract machine, indexes of type definitions, etc.

Features like "whole program optimization" may rely on intermediate representations as well. The compiler cannot do much to optimize a call from one compilation unit to another. But at link time, the linker could see that your code calls a small function in another library. If the intermediate representation were available, the linker could sent the relevant clumps of IR back to the compiler, giving the optimizer a chance to inline the library function, optimize the result, and produce fresh machine code.

The other answers are very good, but I'd like to come at this from a few other angles that you may not have considered.

A single-pass compiler needs a language designed for that

If you compile in a single pass over the code, from source text to generated code, then you need all of the information to generate that code at the point where you parse it.

Such compilers have been extremely successful; the Borland "Turbo" compilers are famous examples. But they do require one important feature that not all languages have: You need to declare everything before you use them, such as forward-declared functions.

While C and Pascal have this property, many modern languages do not. Java and C# allow you to use a class member before it is declared, without forward declarations, so a single-pass compiler is simply not possible. And many other languages effectively require retaining some of the earlier source code, such as type inference or C++ templates.

But even so, there is always some tree (or more general graph) structure required, if only to store things like type information. If you have structs/records with structs/records as members, then you have a recursive structure, and the best way to represent that is as a tree of some kind.

Character-by-character processing is expensive

Consider a modestly-sized identifier, like print. Even though that's only 5 bytes long, anything that has to iterate over the characters in the identifier's name is always going to be more expensive than manipulating a single pointer. And it adds up; the pass over the program that has to deal with individual characters is usually one of the more expensive linear-time passes that a compiler has to do.

Program text is not only expensive to manipulate, but also expensive to store. Now it's true that a lot of thinking on compiler frontend design is partly informed by the more limited resources on a typical computer of the past, but even today, this is still a consideration.

In many popular interpreted languages of today like JavaScript or Python, the compiler frontend runs on the same machine, even in the same process, that is executing the program. And this could be on a device with limited performance, such as a mobile device, or a virtual machine provisioned from a cloud provider, where having more RAM or more CPU speed might mean mean more cost at scale.

It's true that today, virtual address space is extremely cheap, even on quite modest machines, so you can memory-map input files instead of storing them, assuming the source program comes from a file. Nonetheless, the less time a compiler spends scanning characters, the better.

A compiler is one part of a toolchain

The final thing you might want to consider is all of the other software development tools that a programmer might want or expect. Even leaving JIT compilation or linking to one side, consider debuggers, profilers, coverage analysers, and so forth.

Maybe you can generate code in a single pass from the input string more or less directly. But a compiler is, realistically, only one product in a product line of tools.

This goes double if you want to reuse existing tools. I mean, maybe you are happy with the existing state of debuggers. Fine. But you still have to generate whatever those tools need as output, as well as generating code. And that will either complicate your code generator, or usually require retaining some data about the structure of the program for use in a subsequent pass.

You can make quite an advanced compiler without converting the surface syntax into abstract syntax. A compiler can go, in a single pass, to an intermediate representation (which is not a syntax tree) on which all sorts of optimizations can be applied.

An abstract syntax tree, however, lets you do certain useful things:

1. Transformations: you can implement language features by manipulating the abstract syntax. While this can be done by manipulating the surfaces syntax at the character or token level, it is more reliable and efficient to manipulate the AST. Transformations of concrete syntax can produce bad syntax by misplacing parentheses for instance; whereas those don't even exist in the abstract syntax tree: you can easily guard against producing an invalid AST node (bad syntax). Transformations at this level can implement not only language features, but certain optimizations, like ones based on algebraic simplifications. In the C language PTR->MEMB is equivalent to (*PTR).MEMB. In an AST-based compiler, it's very easy to convert the -> node in the tree into the two nodes representing (*PTR).MEMB, or vice versa. Note that (*PTR).MEMB is not parsed by a single rule. A compiler that doesn't build an AST cannot easily recognize the (*PTR).MEMB pattern. Tree pattern matching on an AST easily discover occurrences of the pattern. The parentheses disappear in the AST, so the problem boils down to identifying the . (member selection dot) nodes, whose left child is * (pointer dereference) node.

2. Multiple passes: abstract syntax lets you examine the program more than once, in a way whereby your compiler is sure that it's looking at the same thing. An AST node is an object in memory with a fixed identity. When the compiler makes another pass over the tree, the nodes are the same ones. Meta-information can be attached to the nodes in one pass, which can be counted on to be there in the next pass. Multiple passes are possible over the character or token-level representation of the program also, without building an AST, but each pass has to process the syntax rules and construct new information about the syntax, which somehow has to be related to the previous visit of the same part of the program (perhaps using a hash table keyed on file/line/column?) To write multiple passes without retaining an AST, we need to apply exactly the same tokenizing and parsing rules two or more times; if we parse anything differently between passes, we will end up with hard-to-find bugs. This means our parser has to have each rule implemented in one place, and each rule has to invoke pass-specific processing logic, once it has parsed out the pieces it needs. It doesn't seem impossible, only inefficient, inconvenient and conductive to poor program organization.

It's certainly possible to design compilers that accept a stream of source code and produce a stream of output which could be loaded into memory using a relatively simple loader without having to generate any other intermediate form. In many cases, however, having a compiler be able to inspect a section of code before generating code can greatly improve the efficiency of the code thus generated.

As a simple example, consider the following code snippet:

extern struct s foo[10]; // Assume `s` has member `int x;`.
int i;

for (i=0; i<10; i++)
{
  foo[i].x = 123456;
  ...

If the size of struct foo isn't a power of two (and on some systems, even if it is) code to compute the address of foo[i].x given i might need to do a fair amount of work (not all platforms can perform multiplication efficiently). It might be advantageous for a compiler to rewrite the inner loop code as:

{
  register int offset, n123456;
  register uintptr_t base = 10*sizeof (struct s) + (uintptr_t)&foo[0].x;

  n123456 = 123456;
  offset = -10*sizeof (struct s);
  do
  {
    *(int*)(base + offset) = n123456;
    ...
  } while ((offset += sizeof (struct s)) != 0);
}

but such an optimization would only be valid if nothing within loop modifies the value of i, and might be counter-productive if the value of i is used elsewhere in the loop, or if the registers used to hold base and n123456 could be more efficiently used for some other purpose. A compiler which had only scanned up to the ..., however, would have no way of knowing whether any of those conditions might apply.

Keeping the program as a syntax tree facilitates determinations such as whether any code within a loop modifies i, at least in common cases. If a loop contains any goto labels which are reached from code outside the loop, it may be impractical for a compiler to make such determinations, forcing it to presume that i might be modified within the loop in ways it doesn't understand, but syntax trees make it easy for a compiler to e.g. record for each node whether it contains any goto statements or target labels, which objects are read, written, or have their address taken within that node, etc. and then draw inferences such as "if a for loop is of the form for (x=constant; x<constant; x++) [same x used in all places), the body of the loop doesn't modify x, and x never has its address taken anywhere it is in scope, keep track of how often x ends up being scaled by different amounts. If all uses of x are scaled by the same amount as part of address computation, rewrite the loop using the pattern above." If the program is stored as a syntax tree, and the system records the appropriate information at each node, it will be much easier to determine when the conditions are right for various optimization transforms than if the compiler had to search through some other non-tree form to perform such analysis.