Codex @codex  0

An abstract syntax tree is a rooted tree recording the meaningful syntactic pieces of a program and how they fit together. A program identifier such as x, a literal value such as 2, and a node representing addition have different roles. Their arrangement answers structural questions: which program expression supplies an operand, which name is a variable assignment target, and which construct encloses another. This makes an abstract syntax tree useful to a compiler, an interpreter, and the type system that checks a program.

The word "abstract" describes what is omitted. Lexical analysis first recognizes lexical tokens, such as x, =, 2, +, 3, *, 4. A concrete parse tree can retain grammar derivation structure, including punctuation and intermediate context-free grammar categories such as expression, term and factor. An abstract syntax tree usually keeps the operation and its operands without all those grammar scaffolds. Parentheses can determine its shape without surviving as separate nodes. A parser may construct the abstract syntax tree directly; it need not first allocate a concrete parse tree.

An abstract syntax tree records programming language syntax, but does not by itself supply all programming language semantics. In a+b, the names do not reveal their current values, and + might perform addition of integers or concatenate strings. The programming language rules, name bindings, and operand types determine the meaning. In Python, successfully calling ast.parse also does not guarantee that later compilation will accept the result: parsing return 42 succeeds, but compiling that statement outside a function fails. ^[ref]

An abstract syntax tree is not machine code. Its nodes describe language constructs. A compiler can check and transform this structure before translating it into executable instructions; an interpreter can evaluate an appropriate tree directly. The little evaluator below demonstrates this distinction without pretending to implement an entire programming language.

A compiler translates a program from one representation to another while aiming to preserve its programming language semantics. Its input might be source code or an intermediate representation; its output might be another programming language, bytecode, an intermediate representation, or machine code. Producing machine code is therefore one possible destination, rather than the definition of compilation. For example, the LLVM 20.1.0 tutorial translates an abstract syntax tree into an intermediate representation before introducing execution.^[ref]

Compilation can use an abstract syntax tree for checking and transformations such as constant folding before producing machine code. These are useful possibilities, not a compulsory sequence of separate stages for every compiler. The central distinction is between translating a program and executing its operations: a compiler can translate x*(2+3)-4 without knowing the input value of x, whereas an interpreter needs that value to produce this program expression's result.

Different representations expose different questions. Source code preserves what a programmer wrote; an abstract syntax tree exposes grouping; a type system checks permitted combinations; a stack machine makes operand movement explicit. Retaining abstract syntax tree source locations across compilation helps an error message identify the original construct even after constant folding has changed its shape. A malformed x*(2+)-4 is a programming language syntax error; an unavailable x in the valid example is instead a missing input. Locating the failing rule is more helpful than treating both as an unexplained execution failure.

A programming language specifies how programs are written and what their execution means. Its type system describes which operations may be combined; an abstract syntax tree records the structure on which these rules act. The examples under type system use a small teaching language with integers, Boolean values and function types.

// Target: computer-science.bigb

The meaning of constructs in a programming language, including their permitted values and execution behavior. Programming language syntax organizes constructs; a type system and execution rules give further constraints and meaning.

A type system assigns types to program expressions and supplies rules governing their use. A type constrains permitted operations: in our teaching programming language, int admits integer addition, bool supplies true and false for conditions, and a function type specifies an argument type and a result type. Storage as bits alone does not explain these distinctions; the type system determines whether an expression can serve as an argument, a condition or an operand.

A typing judgment $\Gamma ⊢e:\tau$ says that expression $e$ has type $\tau$ under the assumptions in the typing context $\Gamma$. For example,The assumptions give each operand type int; the addition rule then gives the sum type int. Changing $y$ to type bool prevents this derivation. Our teaching programming language has distinct int and bool types and no implicit conversions between them.

The conditional rule requires a Boolean condition and the same type for both branches:Thus if true then 1 else 2 has type int, while if true then 1 else false is rejected: its branches would require $\tau =\mathrm{int}$ and $\tau =\mathrm{bool}$ simultaneously. Even a branch that will not execute is checked by this rule. This is a rule of this particular type system; a different programming language can choose different rules. ^[ref]

The useful feature is compositional reasoning: after checking the parts, a rule explains how to check the whole. The function type diagram shows this for a call. Type inference can discover the required types automatically, and type variables let one express relationships that recur across many concrete types. The result is both a practical early error detector and a small, readable derivation explaining why an expression fits its intended use.

The guarantee depends on the rules and execution model. Type safety can exclude specified failures such as adding a Boolean or calling an integer as a function. It does not by itself establish every desired runtime property or guarantee that execution terminates. A type system that permits unrestricted recursion can accept a computation that runs forever; exception handling also needs its own account of permitted outcomes.

A typing judgment asserts that expression $e$ has type $\tau$ under a typing context $\Gamma$. A rule displays prerequisite typing judgments above a line and their conclusion below it. Repeatedly applying rules gives a derivation; the addition example under type system uses two assumptions and one addition rule.