= 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.
Back to article page
