Programming Languages & Compilers: How Text Becomes a Machine

You make a typo in a program, say you forget a closing bracket. Within a second, before anything has run, an editor underlines the line and says expected ')'. Something has read your text, understood its structure well enough to know a bracket is missing, and told you where. Nobody sat down and wrote a rule for your particular typo.

Later you write 7 / 2 and get 3.5 in one language and 3 in another. Same symbols, different answers. And you hear, in the same week, that one language "has no garbage collector", another "checks everything at compile time", and a third "is just interpreted". These phrases are the vocabulary of a course that most programmers pick up in pieces. This piece puts the pieces together.

A language is syntax plus semantics

Every programming language has two layers. Syntax is which strings of characters count as a program: where the brackets go, which words are reserved. Semantics is what a valid program means: what it does when it runs. Syntax is the spelling and grammar; semantics is the sense.

The two come apart more than newcomers expect. The same syntax can have different semantics in different languages, and most arguments about "which language is better" are really about semantics.

Languages also differ in how they are defined. Some have a long formal specification; some are defined by their main implementation; many are defined by a standard that a committee maintains. The notation used to write down a language's grammar, with rules like "an expression is a term, optionally followed by plus or minus and another term", is the first tool the rest of this piece uses.

Interpreters and compilers

A processor understands only its own machine instructions. A program in a human-friendly language must be translated. There are two basic ways:

• A compiler translates the whole program ahead of time into another form, usually machine code, which you then run. You pay once, and the result runs fast.
• An interpreter reads the program and carries out its meaning directly, step by step, while it runs. There is no separate translation step, which makes it easy to try things and easy to build.

Real systems blur the line. Python compiles your source into bytecode for a virtual machine, and runs that (its documentation includes a disassembler for the bytecode). Java compiles to bytecode for the Java Virtual Machine, and the JVM can compile hot parts to machine code while the program runs, a technique called just-in-time (JIT) compilation; modern JavaScript engines do the same. So "is language X compiled or interpreted?" is usually a question about one implementation, not about the language.

The idea of a compiler is old. Grace Hopper's A-0 system (1951–52) is often called an early compiler-related tool, and IBM's FORTRAN, led by John Backus, shipped in 1957 with a compiler good enough to convince working programmers that they no longer needed to write machine code by hand.

The pipeline: text to tokens to tree to code

A classical compiler is a pipeline, and each stage has one job.

1. Lexing chops the character stream into tokens: numbers, names, operators, brackets. 12+x becomes the tokens 12, +, x.
2. Parsing arranges the tokens into a tree that reflects the grammar. The tree is where precedence lives: in 2+3*4, the multiplication sits below the addition, so it happens first.
3. Type checking and other analysis walk the tree and reject nonsense, like adding a number to a list.
4. Optimisation rewrites the tree (or a later form) into an equivalent but cheaper one: computing 2*3 now rather than every time the program runs (constant folding).
5. Code generation turns the tree into instructions for the target. Here we use a simple stack machine: push numbers, then apply operations to the top of the stack.

The tree is the most important idea. Once the program is a tree, an interpreter can walk it to compute the answer, and a compiler can walk it to print instructions. Same tree, two different walks.

Notice what the type-checking and optimisation stages buy. Without a tree there is nowhere to ask "is this part constant?" or "does this add a number to text?". Real compilers do hundreds of such rewrites and work over several intermediate forms, but each is the same move: walk the structure, change it, keep the meaning.

Types: catching mistakes before they run

A type is a label on a value that says what you may do with it: you can add numbers, you cannot add a number to a calendar. Languages split by when they check.

• Static typing (Java, Rust, C, Go): types are checked before the program runs. A wrong combination is a compile error.
• Dynamic typing (Python, JavaScript, Ruby): values carry types, and the check happens when the line actually runs. A wrong combination is a runtime error, only if that line is reached.

The debate is real, and both camps have a case. Static advocates point out that a whole class of mistakes disappears before shipping, that types document the code and make large refactors safer, and that tools can offer better autocompletion. Dynamic advocates point to quick experiments, shorter code and flexibility, and say good tests catch most of what types would. Evidence is mixed: one widely cited study (Gao, Bird and Barr, 2017) took real public JavaScript bugs and found that adding TypeScript or Flow annotations would have detected about 15% of them. The authors present that as a lower bound, because these were bugs that had survived testing and review; critics note it still means most bugs are not type errors. Both camps now converge somewhat: Python has optional type hints and JavaScript has TypeScript, an approach called gradual typing.

The sharp way to see the difference is in how a bug hides. A static check looks at every line. A dynamic check, or a test, sees only the lines that run.

This is the whole case for static types in one line: they check the rare path too. And the whole case against them: they only check the kinds of mistakes the type system can express, and they add ceremony. Neither replaces tests for logic errors.

Memory: who cleans up?

Programs make objects in memory and must give the space back. Languages have three broad answers.

• Manual: the programmer frees memory (C's malloc and free). It is fast and predictable, and the mistakes are costly: forget and you leak; free twice or use after freeing and you get crashes and security holes.
• Garbage collection: the runtime finds unreachable objects and reclaims them. John McCarthy introduced garbage collection around 1959 for Lisp. It is used by Java, Python, JavaScript, Go and many others. The costs are occasional pauses and some extra memory use, which good collectors work hard to hide.
• Ownership (Rust): each value has exactly one owner, and when the owner goes out of scope the value is dropped. The compiler checks this, so the program has no garbage collector and no manual free. Rust 1.0 was announced in May 2015.

Rust's trick is that assignment moves a value, and the old name stops working:

let s1 = String::from("hello");
let s2 = s1;          // ownership moves to s2
println!("{}", s1);   // compile error: borrow of moved value `s1`

That error appears at compile time, not at 3 a.m. in production, and it is the price of Rust's guarantees: you must learn to think about who owns what.

Garbage collectors come in flavours too. The simplest idea, reference counting, frees an object when nothing points at it. But two objects that point at each other keep each other alive forever. Tracing collectors instead start from the live variables (the roots), mark everything reachable, and sweep away the rest.

Paradigms: three ways to say the same thing

A paradigm is a style of organising a program. Most languages support more than one.

• Imperative: a sequence of commands that change state. Variables are boxes you update. It maps directly onto how hardware works.
• Functional: build results by composing functions that take inputs and return outputs without changing anything else. Fewer surprises, and easier to run in parallel; state changes become explicit.
• Object-oriented: bundle data with the operations on it into objects that send each other messages. Good for modelling things that have identity and changing state, such as accounts and windows.

None of them wins everywhere. Many large systems mix all three, and a graduate learns to pick the style that fits the problem and to recognise it in whatever language they meet.

What a graduate just sees

• Every program is a tree before it is anything else; precedence and meaning live in the tree.
• "Compiled or interpreted" describes an implementation, and most real systems do some of each.
• A compiler error is a gift: a mistake found on the rare path, before a user finds it.
• Same syntax does not mean same semantics; 7 / 2 depends on the language.
• Memory has to be freed by someone: you, the runtime, or the compiler's ownership rules, and each choice has a price.
• Two objects pointing at each other defeat naive reference counting.
• Static versus dynamic typing is a trade-off argued by serious people, not a right answer.
• Imperative, functional and object-oriented are styles you can write in almost any language.

Where it shows up next

• Theory of Computation (34/29): the grammars that parsers use are the same objects studied in that course (regular expressions for lexing, context-free grammars for parsing).
• Computer Architecture (34/25): the code generator's target is the instruction set; registers and the stack are real hardware.
• Software Engineering (34/31): type systems, linters and static analysers are how teams catch mistakes at scale.
• Computer Security (34/33): memory-safety bugs in manual-memory languages are a major source of vulnerabilities, which is one reason ownership-based languages exist.
• In the world: your editor's squiggles, a database's query planner, a spreadsheet's formulas and a browser's JavaScript engine are all small compilers.

If you want to go deeper

• 📘 Compilers: Principles, Techniques, and Tools (the "Dragon Book", 2nd edition 2006), Aho, Lam, Sethi and Ullman: the classic university text, best for parsing theory.
• 📘 Engineering a Compiler, 3rd edition (2022), Keith Cooper and Linda Torczon: more modern, best for optimisation and code generation.
• 📘 Gentler: Crafting Interpreters by Robert Nystrom, free to read online. You build two complete interpreters, step by step.
• 🌐 Free courses: Stanford CS143 Compilers and MIT OpenCourseWare 6.035 Computer Language Engineering.