How does a compiler work when it's not directly compiling to machine code

Question

I know the compilation process goes with this flow:

source -> parse -> AST -> intermediate code -> assembly -> machine code

and in the case of Java you will have bytecode which is translated by JVM.

In languages such as C/C++ and GO, we parse the source code and output direct machine code in a compiled file, easy enough;

But what about other languages, such as Java, JavaScript, Python etc?

Lets say I want to construct my own simple language and write it's Just in time compiler in C, my language is going to be similar to JavaScript, here is a code snippet:

my language:

var a, b = 5;
print(a+b)

My compiler (which is written in C), after it has constructed an AST will try to add these 2 tree nodes together:

int compilerDoAdd(node a, node b){
 return a + b;
}

Here is my question:

Is the above method the normal way to create a compiler? I'm not creating a heap, I'm not creating stack, I'm not creating assembly, I'm not creating machine code or instructions directly anywhere and I'm just letting the C language do all that work for me. My compiler will act just as a parser.

Is this how other languages like Python and JavaScript work? or do they create their own machine instructions (and basically redo whatever C is designed to do)?

Edit. is what I just explained how an Interpreter works? I have read in many places that An interpreter steps through the source code line by line, figuring out what it’s doing and does it. but it never explains how the does it works, does it turn into machines code? Or it works like how I explained it.

Answer 1

I know the compilation process goes with this flow:

source -> parse -> AST -> intermediate code -> assembly -> machine code

,and in the case of Java you will have bytecode which is translated by JVM.

This is not true for many, many, reasons.

• Not all compilers produce "machine code" (except for the trivial interpretation that all code in some language is machine code for an abstract machine induced by that language). For example, lots of compilers produce ECMAScript source code: CoffeeScript, TypeScript, PureScript, Elm, Opal, GWT, Emscripten, Babel, Clozure, Scala.js, Kotlin, Clue.
• Not all compilers use assembly as an intermediate language.
• Not all compilers use an intermediate language at all, they may generate code directly from the AST, for example.
• Compilers may have multiple intermediate languages. E.g. in GCC, there are GENERIC, GIMPLE, and RTL, and frontends may also have their own intermediate languages as well.
• Many compilers have a tokenization step (aka lexical analysis, lexing, scanning) before the parsing step.
• Many compilers will first produce a parse tree (aka Concrete Syntax Tree / CST) and then transform that to an Abstract Syntax Tree / AST.
• You are completely missing any form of semantic analysis, e.g. type checking, type inference, name resolution / binding, definite assignment.
• Most compilers perform optimizations. In fact, the entirety of what is usually called the mid-end is missing from your description.
• You are not accounting for things like macros, compile-time metaprogramming, compile-time reflection, etc., which may require embedding an interpreter (or another compiler) inside the compiler.

In languages such as C/C++ and GO, we parse the source code and output direct machine code in a compiled file, easy enough;

This is also not true. There is nothing in the language specification of C, C++, or Go that says that it has to be implemented by a compiler that produces machine code. In fact, there is nothing in those specifications that says the language has to be implemented by a compiler at all.

For example, Cint is an interpreter for C. Clue is a compiler for C that outputs Lua, Javascript, Perl, Common Lisp, Java, or C. GCC, one of the most widely-used C compilers does not output machine code either, it actually outputs assembly to be compiled by an assembler. You just don't see it because for performance reasons, modern versions no longer write the assembly to a file, they hand the code off to the assembler directly in memory.

But what about other languages, such as Java, Javascript, Python etc?

Still the same. A language is simply a set of abstract mathematical / logical rules and restrictions. That's it. A language is a piece of paper, written in English.

How you implement this piece of paper is completely your choice. You could write an interpreter. You could write a compiler that outputs ECMAScript. You could write a compiler that outputs C. You could write a compiler that outputs JVM bytecode. You could write a compiler that outputs bytecode for a specialized VM for that language.

The language says nothing about how it is going to be implemented. That is purely a choice for the implementor. You can implement C with an interpreter if you want, and indeed, it has been done. You can implement ECMAScript with a compiler that compiles to native machine code if you want, and indeed, it has been done.

Lets say I want to construct my own simple language and write it's Just in time compiler in C, my language is going to be similar to Javasciprt, here is a code snippet:

my language

var a, b = 5;
print(a+b)

My compiler (which is written in C), after it has constrcuted an AST will try to add these 2 tree nodes together:

int compilerDoAdd(node a, node b){
 return a + b;
}

Here is my question:

Is the above method the normal way to create a compiler?

It depends on what you mean by "normal way to create a compiler". There are many, many, many different ways of creating a compiler. This could in fact be part of a compiler that produces subroutine-threaded code or indirect-threaded code. If you interpret "normal" as "common in mainstream compilers", then no, subroutine-threaded or indirect-threaded code is not used in mainstream compilers. Threaded code is popular in the Forth community, for example, but I would not consider Forth "mainstream" in the general purpose computing market.

It actually looks much more likely that what you have is a part of an interpreter. But it is impossible to say without knowing how this function is called, and what the rest of the code is doing.

I'm not creating a heap, I'm not creating stack, I'm not creating assembly, I'm not creating machine code or instructions directly anywhere and I'm just letting the C language do all that work for me.

Heaps, stacks, assembly, machine code, they are not necessary components of a compiler. A compiler is simply a program which takes a program P written in language X as input and produces a semantically equivalent program P′ written in language Y as output, where "semantically equivalent" means that running P on an interpreter for X should have the exact same result as running P′ on an interpreter for Y.

My compiler will act just as a parser.

Well, then it is not a compiler, nor is it an interpreter. It is a parser.

Is this how other languages like Python and Javascript work? or do they create their own machine instructions (and basically redo whatever C is designed to do)?

Again, this has nothing to do with the language. It has to do with how the particular version of the particular implementation of the language works. For example, the Nashorn implementation of ECMAScript works very different from the V8 implementation of ECMAScript. And the current version of the V8 implementation of ECMAScript works very different than the original version of the V8 implementation of ECMAScript, both of which are again different from some of the versions that came in between.

Edit. is what I just explained how an Interpreter works? I have read in many places that An interpreter steps through the source code line by line,

Only some very simple interpreters do that. In fact, in languages where a single statement can span multiple lines, it isn't even possible to do this. For example, the following snippet of ECMAScript cannot possibly be executed line-by-line, since neither of the lines makes sense on its own:

console.log(
"Hello");

A very simple interpreter may indeed execute code statement-by-statement, but the majority of interpreters create an AST and interpret that. (So-called AST-walking interpreters.) The original interpreter for Ruby was such an interpreter, for example.

Many implementations that are called interpreters are actually combinations of interpreters and compilers. For example, the CPython "Python interpreter" actually compiles Python to CPython bytecode, then interprets that bytecode. So, technically calling it a "Python interpreter" is simply wrong, since it never interprets Python, it interprets a different language. However, calling it a "Python compiler", while technically correct, could also be perceived as misleading.

figuring out what it’s doing and does it. but it never explains how the does it works, does it turn into machines code? or it works like how I explained it.

If it turns it into machine code, then it is not an interpreter, it is a compiler.

Again: a compiler translates from one language to another. An interpreter executes.

To answer also some of your questions from the comments:

Thanks for the great detailed info. So just to confirm, compilerDoAdd in it's current state is an interpreter?,

It very much looks like an interpreter, but it could also be part of a compiler for subroutine-threaded or indirect-threaded code. It is impossible to tell without seeing the rest of the system. The main question is: do you call this function? If you call this function, then it is an interpreter. If you emit code that calls this function, then it is a subroutine-threaded compiler.

by saying an interpreter executes things; this is how it's done? you let your parent language do the work

In some sense this is trivially true. Your interpreter is written in some language, so everything this interpreter does, must somehow be performed by that language.

However, I interpret your question to mean whether there is usually a simple, direct, 1:1 mapping the interpreted language and the host language of the interpreter. The answer is most often: "No". There can only be a simple, direct, 1:1 mapping if the semantics of the two languages are very similar. But if the semantics of the two languages are very similar, then why have two languages? Usually, we create new languages because we want them to be semantically different from existing languages. We want them to be in some sense "better".

The only exception to this are languages that are specifically designed to be semantically identical (or close) but with different syntax. E.g. Vala and Genie are such examples, both Vala and Genie are intended to be semantically identical with Vala having a syntax inspired by C♯ and Genie having a syntax inspired by Python. (Note, however, that in reality, both Vala and Genie are implemented as compilers to C, not as interpreters.)

Languages like TypeScript are also examples of this. TypeScript is designed to be mostly a semantic and syntactic superset of ECMAScript, so for the parts where TypeScript is semantically identical to ECMAScript, a hypothetical TypeScript interpreter implemented in ECMAScript could just use ECMAScript semantics to execute the code. (Note, however, that in reality, TypeScript is implemented as a compiler, not an interpreter, and it is implemented in TypeScript, not ECMAScript.)

Looking at your example, though, you say that your language is "similar to JavaScript". In that case, what you have written is probably not valid, since you are assuming that adding two values in your language behaves the same as adding two ints in C. I can tell you that this is most definitely not the case for JavaScript, and if your language is similar in that aspect, then it is also not the case for yours!

For example, here are some properties of adding ints in C that are not true for adding values in JavaScript:

• Addition of ints in C is commutative: a + b == b + a. This is not true in JavaScript, e.g. for a = "Hello"; b = "World";.
• ints in C have a limited range but they are always precise. Numbers in JavaScript have also a limited range, but much larger than typical ints in C. BUT!!! Most importantly, they are variably precise, i.e. numbers very close to 0 as well as very large and very small numbers are imprecise. For example, for a very large number a it can happen that a + 1 == a. This is not true for ints in C.
• On the other hand, in JavaScript, it is always true that a + 1 >= a, whereas in C, it can happen that a + 1 <= a.

So, it is highly likely that you will have to do more work to implement the + operator than simply to delegate to int addition in C. You will have to check whether a and b are strings, arrays, or numbers, and when they are numbers, you will have to check if the numbers are integers or real numbers, and when they are integers, you will have to check if the numbers and their result fit into a C int or you need e.g. something like a C long or even BigInt math, and generally do some other clever things, and implement your own logic for adding things. Especially if your language is really like JavaScript, where [] + {} is {} and {} + [] is 0.

Here are some other questions and answers on this site that may help you:

• Understanding the differences: traditional interpreter, JIT compiler, JIT interpreter and AOT compiler
• Which components/phases of a JIT compiler are different from a traditional ahead of time compiler?
• Does an interpreter produce machine code?

Answer 2

A compiler is always a tool that transforms a representation of something into another representation. Sometimes they can transform an HTML page into an image (not that I know of any that do off the top of my head), JavaScript into machine code, or even C into... more C. All of these are compilers. So, the question becomes, what do you want the output target to be?

An interpreter takes a representation of something, and in some way executes it: virtual machines are inherently interpreters, but so too are processor chips.

A parser takes an input representation, and analyzes it to extract semantic meaning from it.

So, the question becomes several:

• Do you want to execute immediately, or later? If immediately, you want an interpreter, if later, you want a compiler. Note that it is possible to do both, coding your compiler to execute some or all of the code at compile-time instead of "run time", and there have even been demonstrations for C++ where this was used to execute simple games (e.g. pong) at compile-time.

• Supposing you want to output something to be executed later, in what format? You can output in assembly/machine code, or C/JavaScript/Lisp/COBOL, or threaded code (I recommend reading about Forth, and in particular Brad Rodriguez's Moving Forth articles), or even the very same language that you received as input.

• Supposing you want to interpret, does it even make sense to properly build an AST, or are you planning to execute tokens as you encounter them without maintaining state?

Regardless, the compilerDoAdd() function you show is only appropriate in two instances: 1) You're interpreting, 2) You're compiling, and specifically that's what you output.

If you want to compile, then you WILL be emitting instructions. Those instructions can be in the form of C code calls to functions (in fact, in a C subroutine-threaded system, you could choose to emit your "add" as "compilerDoAdd( a, b );", though I'd actually suggest "compilerDoAdd( stack );" or the like), in the form of assembly/machine code (note that bytecode is actually included here, not separately!), or even as pointers.

Supposing that you really do want to compile, I personally will suggest the "ITC" style of threaded code (it's worth noting that ITC can be considered a particular style of AST). Functions in ITC essentially consist of the following C structure:

typedef struct itc_func {
    void (*handler)( itc_func* );
    intptr_t body[];
} itc_func;

The handler function may be any of a number of possible handlers, but at least in Forth, it's normally one referred to as "docolon" or something similar, which does the return-pointer management that you'd normally expect from a call instruction, before instructing the underlying management system to start treating the intptr_t values in it's body as pointers to other itc_func instances that it needs to execute in sequence. Other handlers implement "leaf" functions such as addition.

My own implementation of ITC uses the following three pieces:

typedef funobj (*funptr)( void*, context* );
struct funobj
{
    funptr func;
    void *data;
};
int run( context *ctx )
{
    if( ctx )
    {
        funobj func = ( ctx->boot.func )( ctx->boot.data, ctx );
        while( func.func )
        {
            func = ( func.func )( func.data, ctx );
        }
        return( 1 );
    }
    return( -1 );
}

The context structure contains stack pointers, as well as various other useful variables. My own runloop actually contains a few other functionalities as well, but they've been removed for being superfluous.

With a system like this in place, it begins to become somewhat simpler to build your compiler, as well as to add interpretive aspects to it. The "machine code" encoding is just structures, so you can use the same system for both the output of your compiler, as well as an interpretable AST, all without having to deal with execution protection. Adding constants together, for example, becomes a matter of detecting that they are constants, and instead of outputting an addition to the function currently being written, you instead have the addition perform the actual addition, discarding the constants and replacing them with the result, before finishing by pretending (if this is even necessary!) that the addition itself was a constant all along. If you wanted to, you could even use the same version of the "add" handler in the compiler, any "immediately executable" output files, and in the linker if you wanted to allow link-time execution.

Answer 3

A compiler is a program which transforms code from one language into another. An interpreter is a program which executes some code.

Your example is an interpreter, not a compiler.

The process for your interpreter is:

source -> parse -> AST -> evaluate

This is a common way to implement interpreters. It is a bit inefficient though, since you have to parse the source code every time you execute it. Therefore languages like Python use a hybrid approach, where the source code is first compiled into bytecode and then interpreted.

Step 1: Compile

source -> parse -> AST -> bytecode

Step 2: Execute

bytecode -> evaluate

The advantage is you can save the bytecode, so you only need to parse the source code when it changes.

JIT compilers like Java also uses an intermediate bytecode, but compiles the bytecode into machine code:

 bytecode -> assembly -> machine code

Of course this is simplified. For example a compiler might actually evaluate constant expression like 2 + 2 and generate the bytecode for 4. Modern JIT's may also use a number of clever tricks to optimize performance, e.g dynamically recompile sections of code based on usage patterns.

JavaScript is quite diverse. The first implementations were (I believe) straightforward interpreters but current implementation uses advanced JIT's.