Compilation arithmetic example

Consider the program expression x*(2+3)-4 in a deliberately small programming language. Its only program identifier is x, supplied as an integer input. Its literal values are nonnegative decimal numerals, interpreted as integers. Whitespace is ignored between lexical tokens. Its context-free grammar is:

expression ::= term (("+" | "-") term)*
term       ::= factor ("*" factor)*
factor     ::= numeral | "x" | "(" expression ")"
numeral    ::= digit digit*
digit      ::= "0" | "1" | "2" | "3" | "4"
             | "5" | "6" | "7" | "8" | "9"

Here * outside quotation marks means zero or more repetitions. Repeated operators are grouped to the left, specifying operator associativity; term gives multiplication higher operator precedence than addition and subtraction. Parentheses override that grouping. There is no unary minus, variable assignment, function call, or side effect in this language. Evaluation obtains each left operand before its right operand and uses exact integer arithmetic, with no fixed-width overflow.

Lexical analysis recognizes x, *, (, 2, +, 3, ), -, 4. Parsing constructs the concrete abstract syntax tree Sub(Mul(Name(x), Add(Int(2), Int(3))), Int(4)). Parentheses have done their work by making Add a child of Mul; they need not survive as nodes. Constant folding changes this to Sub(Mul(Name(x), Int(5)), Int(4)). It cannot replace Name(x) by a literal value because the input is supplied at execution. The resulting function of the input is $f(x)=5x-4$.

A compiler for our stack machine emits LOAD x; PUSH 5; MUL; PUSH 4; SUB. LOAD x pushes the current input; PUSH n pushes the integer literal value n. Each binary instruction removes the top item as its right operand, then the next item as its left operand, and pushes the result. The instruction sequence is an intermediate representation that an interpreter can execute; no machine code has been emitted. A compact binary encoding could make it bytecode, but these printed instruction names are only a readable notation.

Why does this compilation preserve the result? A structural induction supplies a short proof outline. Translating a literal value or x appends its value to any initial stack. For a binary abstract syntax tree node, first translating the left child and then the right child appends the two operand values; the matching instruction replaces them by exactly the original operation's result. Previously present stack items remain intact. Constant folding also preserves the result because $2+3=5$ in the specified integer arithmetic. Together these facts explain agreement for every integer input, rather than merely agreement for one trial.