Expression Parsing & Evaluation

An expression parser reconstructs a tree from a one-dimensional token stream. Precedence decides which operator owns an ambiguous neighboring operand; associativity decides how operators at one precedence chain; parentheses state grouping explicitly. Evaluation is a later operation: it gives that chosen tree meaning in a numeric, logical, or application-specific domain.

Keeping those stages separate prevents a long list of bugs. The lexer decides whether - is a token but context decides whether it is prefix negation or infix subtraction. The parser decides that a + b * c means a + (b * c) but does not decide whether + adds integers, concatenates strings, overflows, or invokes user code. The evaluator applies those semantic rules only after structure is known.

The pipeline has four contracts #

This chapter focuses on parsing and direct evaluation, but the boundaries matter. A calculator may combine stages for convenience; a compiler normally preserves an abstract syntax tree (AST) so later passes can resolve names, type-check, optimize, and generate code.

Tokenize before reasoning about operators #

The character string

total<=limit-2**shift

might become:

IDENT(total)  LE(<=)  IDENT(limit)  MINUS(-)  NUMBER(2)
POWER(**)  IDENT(shift)  EOF

The lexer must know that <= and ** are longest valid tokens, distinguish identifiers from numeric literals, skip or preserve whitespace according to the language, and attach byte/code-point offsets for diagnostics. Parsing raw characters as operators fails as soon as operators have multiple characters, comments exist, or number syntax contains signs/exponents.

Parsing a literal's text into a numeric value has its own overflow, radix, decimal, and locale rules; see Conversion, Coercion & Parsing at the Boundary. A lexer should not silently accept a prefix such as 123 while discarding malformed suffix xyz unless that token split is explicitly legal.

Precedence resolves an otherwise ambiguous grammar #

The grammar

$$E\to E+E\mid E*E\mid -E\mid(E)\mid\mathtt{id}$$

does not decide whether a + b * c has + or * at the root. Grammars & Formal Languages explains that this is grammar ambiguity: one token sequence has competing parse trees.

An expression language resolves the choices with an operator contract. For a small illustrative language:

Only relative precedence matters. The table is part of the language, not a universal law: mathematical notation, Python, ECMAScript, spreadsheets, shells, and DSLs differ. Parentheses create a primary expression whose interior is recursively parsed under the full expression rule.

Shunting-yard: precedence through an operator stack #

Dijkstra's shunting-yard method converts infix tokens to reverse Polish notation (RPN/postfix) or constructs the same tree directly. It maintains:

• an output sequence for operands and operators whose operands are already determined;
• an operator stack for operators waiting to see whether a stronger operator or parenthesized expression binds first.

For an incoming binary operator $o$, pop a stack-top operator $t$ to output while

$$prec(t)>prec(o),$$

or while

$$prec(t)=prec(o)\quad\text{and }o\text{ is left-associative}.$$

The equality case is exactly associativity. A right-associative incoming ^ must not pop an equal-precedence ^; delaying the older operator produces a b c ^ ^, which groups as a (b c ^) ^.

for token in tokens:
    if token is an operand:
        append token to output

    else if token is a left parenthesis:
        push token onto operators

    else if token is a right parenthesis:
        pop operators to output until a left parenthesis appears
        if no left parenthesis appears: error "unmatched )"
        discard the matching left parenthesis

    else if token is an operator o:
        while stack top is operator t and
              (precedence(t) > precedence(o) or
               (precedence(t) == precedence(o) and o is left-associative)):
            append pop(operators) to output
        push o onto operators

at end of input:
    pop every remaining operator to output
    if a parenthesis is encountered: error "unmatched ("

Every operand goes to output once; every operator is pushed and popped once. With constant-time stack operations, conversion is $O(n)$ time and $O(n)$ worst-case auxiliary space.

Full trace #

Convert

3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

where ^ is right-associative and stronger than *//, which are stronger than +/-:

The postfix stream contains the parse without parentheses:

3 4 2 * 1 5 - 2 3 ^ ^ / +

Prefix, postfix, calls, and commas need explicit extensions #

The binary core is not a full language parser. A preceding-token state can classify - as prefix after start, another operator, (, or a comma, and as infix after an operand, ), or postfix expression. Give the two forms distinct internal token kinds such as NEGATE and SUBTRACT.

Function calls need an arity protocol. On f(a,b), the parser must distinguish call parentheses from grouping parentheses, treat commas as argument separators that pop pending operators to the call's (, count empty/nonempty arguments, and emit a call token carrying arity. Empty calls, trailing commas, and missing arguments are language decisions, not details to guess.

Postfix operators such as factorial or indexing bind to the expression already produced; ternary operators have separated delimiters and usually need custom handling. When operator forms become rich or dynamically extensible, a Pratt parser often expresses the rules more locally.

Postfix evaluation is a stack invariant #

Scan an RPN stream from left to right:

for token in postfix:
    if token is an operand:
        push(resolve(token))
    else:
        require at least arity(token) values
        args = pop arity(token) values, restoring left-to-right order
        push(apply(token, args))

require exactly one final value
return that value

After every prefix of a valid postfix stream, the value stack contains the results of the maximal complete subexpressions in that prefix, in left-to-right order. A binary operator replaces its two top subresults by their parent result, reducing stack height by one.

For the traced expression:

This result assumes real-valued division and exponentiation. Integer division, bounded integer overflow, decimal arithmetic, negative-base fractional powers, and division by zero require different specified behavior.

Stack underflow means an operator lacks operands. More than one final value means operands were never joined. An empty final stack means there was no expression. These are syntax/structure errors; arithmetic exceptions happen only when applying a structurally valid operator.

Build an AST by replacing values with nodes #

The same postfix evaluator can push AST nodes rather than values. On an operand, push Literal or Name; on an operator, pop child nodes and push an operator node. The final one-node stack is the AST root.

For

-2 ^ 2 + 5 * 3

under the illustrative precedence table, a compact prefix rendering of the AST is

(+
  (negate (^ 2 2))
  (* 5 3))

Parentheses and precedence punctuation disappear because the tree already records grouping. Source spans should remain on nodes so later type errors and runtime diagnostics can point back to the original text.

LLVM's Kaleidoscope tutorial follows the AST path: the lexer produces tokens, recursive-descent and operator-precedence routines construct expression nodes, and later code generation assigns target semantics.

Pratt parsing gives each token local behavior #

Pratt's top-down operator-precedence parser gives tokens two parsing roles:

• a prefix/null denotation handles a token that starts an expression—literal, identifier, prefix operator, or (;
• an infix/postfix/left denotation handles a token that continues an already parsed left expression.

Binding powers decide when recursion owns the next operator. This compact core parses literals, names, grouping, prefix +/-, left-associative arithmetic, and right-associative exponentiation:

# For the loop condition below:
# left-associative operators use right_bp = left_bp + 1
# right-associative operators use right_bp = left_bp
INFIX = {
    "+": (10, 11),
    "-": (10, 11),
    "*": (20, 21),
    "/": (20, 21),
    "^": (40, 40),
}
PREFIX_BP = 30

def parse_expression(tokens, min_bp=0):
    token = tokens.take()

    if token.kind == "NUMBER":
        left = ("number", token.value, token.span)
    elif token.kind == "IDENT":
        left = ("name", token.text, token.span)
    elif token.kind in ("+", "-"):
        right = parse_expression(tokens, PREFIX_BP)
        left = ("unary", token.kind, right, token.span)
    elif token.kind == "(":
        left = parse_expression(tokens, 0)
        tokens.expect(")")
    else:
        raise SyntaxError(f"expected expression at {token.span}")

    while True:
        operator = tokens.peek()
        powers = INFIX.get(operator.kind)
        if powers is None:
            break

        left_bp, right_bp = powers
        if left_bp < min_bp:
            break

        tokens.take()
        right = parse_expression(tokens, right_bp)
        left = ("binary", operator.kind, left, right, operator.span)

    return left

Why the binding-power pairs work:

• For a-b-c, parsing the right side of the first - at minimum 11 refuses the next - with left power 10. The outer loop then consumes it, producing (a-b)-c.
• For a^b^c, parsing the right side at minimum 40 accepts the next ^ with left power 40, producing a^(b^c).
• Prefix - parses its operand at 30, so -2^2 admits the stronger ^ inside and becomes -(2^2), while -2*3 stops before weaker * and becomes (-2)*3.

Postfix calls, indexing, and member access fit into the continuation loop with high left binding powers. A ternary token can parse its middle and right operands with custom delimiters. This locality is Pratt parsing's main engineering advantage: syntax behavior lives with the token form instead of being spread across one grammar function per precedence level.

Shunting-yard, precedence climbing, Pratt, or a generated parser? #

Precedence climbing is essentially the binary-operator portion of the Pratt loop expressed as one function over a minimum precedence. Recursive descent with one function per grammar level is often clearest when the operator set is small and fixed. A generated LR/GLR/PEG-style parser may be preferable when the entire language, ambiguity handling, and error recovery should remain grammar-driven. Expression parsing is a component boundary, not a religion.

Evaluation semantics are larger than arithmetic #

An evaluator walks the AST or executes postfix instructions. Literals produce values; names consult an environment or symbol table; an operator requests its operands and applies a declared semantic function.

Evaluation order and short-circuiting #

For pure arithmetic, recursively evaluating both children seems harmless. It is wrong for operators whose semantics control evaluation:

• false && dangerous() must not evaluate the right operand in a short-circuit language;
• true || expensive() likewise skips the right operand;
• condition ? a() : b() evaluates one branch, not both;
• assignment needs an assignable location on the left, not merely its current value;
• function calls and overloaded operators may have side effects or throw.

An AST evaluator handles these nodes specially. A postfix VM needs jumps or lazy instructions; ordinary eager AND over two already-pushed values cannot implement short-circuit semantics.

Values need a declared domain #

For each operator, specify:

• accepted operand types and coercions;
• result type;
• overflow, underflow, and precision behavior;
• division/remainder convention and zero handling;
• comparison behavior for NaN, null, strings, and mixed types;
• error versus exceptional value versus saturation;
• purity, side effects, and evaluation order.

Constant folding must use the same semantics as runtime execution. Folding with arbitrary-precision host integers when runtime uses wrapping 32-bit integers changes the program. Reordering floating-point operations can change rounding and exceptions. Calling a user-defined “pure-looking” operator at compile time can trigger effects.

Errors need positions and expected structure #

A useful token carries at least a kind and half-open source span [start,end). AST nodes combine child spans. Diagnostics can then say:

price * (count + )
                 ^ expected an expression after '+'

Detect errors at the narrowest responsible stage:

A calculator can fail at the first error. An IDE or compiler may recover at synchronization tokens such as comma, semicolon, or closing delimiter, but recovery must guarantee progress: either consume a token or unwind to a strictly outer context. Otherwise one bad token can create an infinite diagnostic loop.

Complexity and hostile inputs #

For a fixed operator table, shunting-yard and Pratt/precedence-climbing parsing consume each token a constant number of times, so ordinary time is $O(n)$ and representation space is $O(n)$. The hidden risk is depth:

• ((((...x...)))) creates nesting depth $O(n)$;
• a right-associative chain a^b^c^... creates recursive Pratt depth $O(n)$;
• a deeply nested AST can overflow recursive evaluation;
• a syntactically small expression such as 2^(2^1000000) can demand impossible evaluation resources;
• function calls can recurse, allocate, or access expensive services.

For untrusted expressions, enforce token count, source length, nesting depth, AST node count, literal size, exponent/collection limits, evaluation steps, wall-clock budget, and allowed functions. Use an explicit parser/evaluator stack if legitimate depth may exceed the host call stack.

A test matrix that catches real parser bugs #

For every valid expression, compare at least two representations: expected AST shape, expected postfix stream, and evaluated result under a small reference semantics. Result-only tests miss wrong trees whenever the chosen numbers happen to make both groupings equal.

Failure diagnostics #

1. Is the input tokenized with longest-match and source spans before parsing?
2. Is prefix/infix/postfix role chosen from parser context rather than token spelling alone?
3. Are precedence and associativity explicit parts of the language contract?
4. Does an equal-precedence shunting-yard pop depend on the incoming operator's associativity?
5. Can parentheses, commas, calls, and empty argument lists be distinguished correctly?
6. Does postfix evaluation restore operand order and finish with exactly one value?
7. Does the Pratt caller require the expected delimiter or EOF, rejecting trailing tokens?
8. Are syntax construction and runtime semantics separate enough to type-check before effects?
9. Are short-circuit/control operators represented lazily rather than as eager arithmetic?
10. Do constant folding and runtime share overflow, precision, and coercion rules?
11. Do diagnostics retain the original source spans through AST construction?
12. Are nesting, token, AST, numeric, and execution budgets enforced on untrusted input?

Exercises #

1. Convert a - b * c ^ d ^ e + f to postfix under the article's precedence table.
2. Trace the Pratt binding powers for a-b-c and a^b^c, identifying the recursive call that accepts or refuses the second operator.
3. Give the two ASTs for -2^2 and (-2)^2, then evaluate both under real arithmetic.
4. Explain why eager postfix instructions lhs rhs AND cannot implement lhs && rhs when evaluating rhs may have an effect.
5. Extend the shunting-yard state with calls and commas. State what must be stored to distinguish f(), f(a), and f(a,b).