Computer Science › Section G · Programming languages › Topic G.4

Language implementation: translation and compilers

A line of Python or Java means nothing to a processor until a translator has taken it apart, checked it and rebuilt it as instructions the machine can run. Seeing how that happens explains error messages, speed differences and why some mistakes are caught early and others never are.

From source program to object program

Translation converts a program from one language into another. The original is the source program; the result is the object program, usually machine language or an intermediate code. A compiler carries out the whole translation before the program runs. Inside, the work falls into three activities: lexical analysis, which groups characters into meaningful units; parsing, which works out the grammatical structure; and code generation, which produces the instructions. In a simple compiler these are interleaved rather than done one after another: the parser asks for one unit at a time and calls the code generator whenever it recognises a complete statement.

Lexical analysis: finding the tokens

A program arrives as a stream of characters. The lexical analyser reads them one by one and groups them into tokens, each a single meaningful unit with a category. For the Python line total = price * 3 # running sum, it produces five tokens: the name total, the operator =, the name price, the operator *, and the number 3. The spaces between tokens and the comment carry no meaning for the machine, so they are discarded. (Python's indentation at the start of a line does matter, and becomes tokens of its own.) The characters 3, 1 and 4 written together form one number token, 314, not three. From here on, the parser sees only tokens, never individual characters.

Parsing: grammars and parse trees

Parsing decides how tokens fit together into expressions and statements, guided by the language's grammar, a precise set of rules for its syntax. Grammars are often drawn as syntax diagrams or written in a rule notation. A small grammar for arithmetic says: an expression is a term, or an expression followed by + and a term; a term is a factor, or a term followed by * and a factor; a factor is a name or a bracketed expression. The parser records how a statement fits the rules as a parse tree, with the whole statement at the root and the tokens at the leaves.

Worked example: a parse tree

Parse (a + b) * c with the small grammar. Steps: (1) The top-level operator outside brackets is *, so the whole expression is a term made of a term, the symbol *, and a factor. (2) The right-hand factor is the name c. (3) The left-hand term is a single factor, the bracketed expression (a + b). (4) Inside the brackets, a + b is an expression: an expression a, the symbol +, and a term b. (5) The tree therefore puts + lower than *, so the addition is computed first. In a + b * c, by contrast, * sits lower and is done first. Precedence is built into the grammar's shape.

Ambiguous grammars

A grammar that allows two different parse trees for the same string is ambiguous, and an ambiguous grammar leaves the meaning undecided. A classic case is the dangling else: in if B1 then if B2 then S1 else S2, does the else belong to the first if or the second? The two trees give different programs. Languages settle this by rule or by layout. C and Java attach an else to the nearest unmatched if, whatever the indentation suggests. Python avoids the question altogether, because indentation shows which if each else belongs to. Language designers check grammars carefully for such hidden ambiguities.

The symbol table and type checking

As the parser reads declarations, it records each name, its type and other details in a symbol table. Later, it uses that table to give each operation its exact meaning: + between two integers needs integer addition, while + between two floats needs floating-point addition, a different machine operation. When the types differ, the language may convert one implicitly, which is coercion. Python turns 2 + 3.5 into float addition and gives 5.5, but rejects "2" + 3 with a TypeError. Java allows widening, so double d = 5; is fine, but int n = 3.9; is a compile error unless the programmer writes an explicit cast, (int) 3.9, which gives 3.

Code generation and optimisation

Code generation builds the instructions that carry out each recognised statement. A good code generator also optimises, producing faster or smaller code with the same effect. If one statement has just loaded a value into a register, the next statement can use it from there instead of fetching it from memory again. Constant expressions can be worked out once during translation: Python's compiler turns seconds = 60 * 60 * 24 into code that simply stores 86400, and its dis module shows this. Optimisation never changes what a correct program computes.

Compiled, interpreted, or both

C and C++ are normally compiled straight to machine code for one processor, which runs fast but must be recompiled for another platform. An interpreter executes statements as it translates them, which makes testing quick but is usually slower. Many systems combine the two. Java source is compiled to bytecode, a machine-independent intermediate language run by the Java Virtual Machine, so one compiled program runs on any computer with a JVM; C# works similarly on .NET. The standard Python interpreter first compiles source to bytecode and then interprets it. Just-in-time compilers translate frequently run code to machine code during execution, as modern JavaScript engines and JVMs do.

Syntax, semantics and three kinds of error

Syntax is the form of a program: which arrangements of tokens the grammar allows. Semantics is the meaning: what a valid program does when it runs. Errors fall into three groups. Syntax errors break the grammar and are caught during translation; the program never starts. Runtime errors happen during execution, such as dividing by zero or indexing past the end of a list. Logic errors produce wrong answers without any message at all, because the program is valid and runs, but it computes something other than what was intended. Only testing and reasoning find logic errors.

Worked example: classifying errors

Classify each faulty Python program. Steps: (1) if x > 3 followed by an indented print(x), with no colon: the grammar requires a colon after the condition, so translation fails with SyntaxError: expected ':' before any line runs. This is a syntax error. (2) A function average(nums) that returns sum(nums) / len(nums), called with an empty list: it translates fine, but dividing 0 by 0 raises ZeroDivisionError as it runs. This is a runtime error. (3) A loop meant to add 1 to 10 written as for i in range(1, 10):, which stops at 9: it runs without complaint and gives 45 instead of 55. This is a logic error, an off-by-one.

Common mistakes to avoid

Thinking an interpreter needs no translation: it still analyses and parses the source, it just executes as it goes. Assuming Java or Python programs are pure machine code, when both normally pass through bytecode. Believing a program that compiles must be correct: compilers catch syntax and many type errors, never logic errors. Trusting indentation in C or Java to decide which if an else belongs to. Thinking optimisation changes results; it may change speed or size, never the output of a correct program.

Key takeaways

Translation turns a source program into an object program through lexical analysis, parsing and code generation, done in an interleaved way. The lexical analyser produces tokens; the parser fits them to a grammar and builds a parse tree, and ambiguous grammars must be avoided. The symbol table supports type checking, coercion and casts. Code generation includes optimisation. Systems may compile, interpret, or compile to bytecode with just-in-time compilation. Syntax errors stop translation, runtime errors stop execution, and logic errors give wrong results silently.

Flashcards

Flashcard

Source program

The program as written, before translation

The object program is the result.

Test your understanding

Question 1 of 5

Which tokens does a lexical analyser produce from the line count = count + 10 # add ten?

Question 2 of 5

Using the small grammar from the reading, where does + appear in the parse tree for x * (y + z)?

Question 3 of 5

In Java, int n = 7.8; fails to compile but int n = (int) 7.8; works. What does the second statement do?

Question 4 of 5

A program runs to completion and prints 45 when the correct total is 55. What kind of error is this?

Question 5 of 5

Why can one compiled Java program run on Windows, macOS and Linux machines?

← Previous topicNext topic →