4.7 Chapter Summary

There are a variety of ways to implement a programming language. All language implementations have a syntactic component (or front end) that determines whether the source program is valid and, if so, produces an abstract-syntax tree. Language implementations vary in how they process this abstract-syntax tree.

Two traditional approaches to language implementation are compilation and interpretation. A compiler translates the abstract-syntax tree through a series of transformations into another representation (e.g., assembly code) typically closer to the instruction set architecture of the target processor intended to execute the program. The output of a compiler is a version of the source program in a different language. An interpreter traverses the abstract-syntax tree to evaluate and directly execute the program. The input to an interpreter is both the source program to be executed and the input of that source program. The output of an interpreter is the output of the source program. Ultimately, the final representation (e.g., x86 object code) produced by a compiler (or assembler) must be interpreted—traditionally by a hardware interpreter (e.g., an x86 processor).

Languages in which the final representation produced by a compiler is interpreted by a software interpreter are implemented using a hybrid system. For instance, the Java compiler translates Java source code to Java bytecode, and the Java bytecode interpreter then interprets the Java bytecode to produce program output. Just as a compiler can produce a series of intermediate representations of the original source program en route to a final representation, a source program can be interpreted through a series of software interpreters (i.e., the source program is interpreted by a software interpreter, which is itself interpreted by a software interpreter, and so on). As a corollary, compilers and interpreters are mutually dependent on each other. A compiler is dependent on either a hardware or software interpreter; a software interpreter is dependent on a compiler so that the interpreter itself can be translated into object code and run.

Compilers and interpreters are often complementary in terms of their advantages and disadvantages—hence the conception of hybrid implementation systems. The primary advantage of compilation is production of a fast executable. Interpretation results in slow execution because it takes longer to decode (and re-decode) high-level program statements than machine instructions. However, interpreters support run-time flexibility in the source language, which is often less practical in compiled languages. The interplay of language goals (e.g., speed of execution, speed of development), language design choices (e.g., static or dynamic bindings), and execution environment (e.g, WWW) have historically influenced both the evolution and the implementation of programming languages.