C15: Languages, parsing, interpreters, and compiler structure

A. Prerequisites and observable goals#

Level: Degree core introduction; this language is intentionally smaller than Python or C++.

B. The central question: how do characters acquire meaning?#

The text 2 + 3 * 4 is a sequence of characters. A language definition tells us which character sequences are valid and how to interpret them. Lexical analysis groups characters into tokens such as number, identifier, plus, and parenthesis. Parsing organizes tokens according to a grammar. Semantic analysis and evaluation then determine what the organized expression means under an environment.

Syntax concerns form; semantics concerns meaning. The expression x + 1 can be syntactically valid while evaluation fails because x has no binding. The expression 1 / 0 can parse correctly while its requested arithmetic operation is undefined. Reporting every failure as a syntax error hides these distinctions and makes debugging harder.

A compiler translates a source representation to another representation, often through an intermediate representation before machine code. An interpreter executes the meaning of a representation directly or through a runtime. These strategies can be combined: a system may parse to bytecode, interpret it, and compile hot paths. Static versus dynamic type checking is a different distinction; compilation does not automatically imply static typing, nor does interpretation automatically imply dynamic typing.

C. A grammar makes precedence explicit#

Our language supports finite numeric literals, identifiers, unary signs, parentheses, and the four arithmetic binary operators. A useful grammar, with braces meaning repetition and brackets here avoided to prevent confusion, is

A term consumes multiplication and division before the surrounding expression consumes addition and subtraction. Iterative left folding makes subtraction and division left-associative: 10-3-2 means $(10-3)-2$, not $10-(3-2)$. Parentheses explicitly override the usual structure. Unary signs are handled before binary multiplication in this grammar.

An abstract syntax tree, or AST, keeps the semantic structure while omitting punctuation that is no longer needed. A binary node contains an operator and two subtrees. A literal node contains a value. A variable node contains a name. For 2*(x+3)-1, the root is subtraction, with multiplication on the left and literal $1$ on the right.

The drawing is an exact representation of the parse structure, not a memory-address diagram. Evaluation follows dependencies from leaves toward the root: at $x=4$, compute $4+3=7$, then $2(7)=14$, then $14-1=13$.

D. Recursive descent mirrors the grammar#

Each grammar level becomes a function. expression() calls term() for its first operand and repeatedly extends the tree when it sees plus or minus. term() does the analogous work for multiplication and division. atom() handles literals, names, signs, or a parenthesized recursive expression. A token cursor records how much input has been consumed.

The parser must require end-of-input after the expression. Otherwise it might accept a valid prefix and ignore trailing garbage, such as parsing 1 2 as just $1$. Every successful token consumption advances the cursor; loops consume an operator and an operand. Nested parentheses and unary signs reduce the remaining token suffix. The companion also bounds source length at $4096$ characters and tokens at $128$, making the educational recursion depth controlled by small input rather than arbitrary untrusted programs.

An environment maps identifiers to values. Evaluation of a literal returns that value; evaluation of a variable looks up its binding; evaluation of a binary node evaluates both children and applies the operator. The environment is passed explicitly instead of silently reading mutable global variables. The interpreter does not use Python’s eval; its accepted language and effects are defined by our own parser and evaluator.

E. Type rules and optimization need semantic assumptions#

A simple type judgment $\Gamma\vdash e:\text{Number}$ means that under type environment $\Gamma$, expression $e$ has numeric type. One arithmetic rule says that if both operands are numbers, their sum is a number. This can reject some invalid operations before execution, but it does not prove a denominator is nonzero or every resource use is bounded. Richer types, contracts, and static analyses can express more properties at additional complexity.

A compiler pipeline often contains tokenization, parsing, name and type checking, intermediate representation, optimization, code generation, and linking. Optimizations must preserve the relevant language semantics. Replacing $x\times0$ with $0$ is valid for mathematical real numbers, but not an unconditional floating-point transformation when $x$ may be infinity or NaN. Reordering side-effecting function calls can change behavior even when an algebraic expression appears commutative. C09’s machine representation and C03’s lifetime rules remain relevant after parsing succeeds.

A bounded interpreter is useful in game tooling, configuration, and teaching because it makes language boundaries visible. Production scripting requires much more: resource accounting, safe host interfaces, isolation, debugging facilities, versioning, and a threat model. Rejecting Python syntax alone does not establish a secure sandbox.

F. Worked error classification#

For 2*(3+4, the tokenizer succeeds but the parser expects a closing parenthesis and encounters end-of-input: syntax failure. For speed+1 with an empty environment, parsing succeeds but lookup raises a missing-name error: binding failure. For 1/(2-2), the AST is valid and denominator evaluation yields zero: arithmetic failure. For 1e999, lexical recognition finds a number-shaped token but the conversion is nonfinite and is rejected by the numeric-literal contract.

A useful test suite keeps these categories separate. It includes precedence, associativity, nested parentheses, unary signs, valid variables, trailing input, illegal characters, missing names, division by zero, nonfinite results, and size limits. Testing only a successful arithmetic expression says little about the parser’s boundary behavior.

G. Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

H. Complete solutions: C15#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""C15.05: bounded arithmetic language, parsed without Python eval."""
import math
import re
TOKEN = re.compile(r"\s*(?:(\d+(?:\.\d*)?|\.\d+)(?:([eE][+-]?\d+))?|([A-Za-z_]\w*)|([+*/()\-]))")

def tokenize(source: str) -> list[tuple[str, object]]:
    if len(source) > 4096:
        raise ValueError("source too long")
    out, pos = [], 0
    while pos < len(source):
        if source[pos:].isspace(): break
        match = TOKEN.match(source, pos)
        if match is None:
            raise ValueError(f"unexpected character at offset {pos}")
        number, exponent, name, op = match.groups()
        if number is not None:
            value = float(number + (exponent or ""))
            if not math.isfinite(value):
                raise ValueError("nonfinite literal")
            out.append(("number", value))
        elif name is not None:
            out.append(("name", name))
        else:
            out.append((op, op))
        pos = match.end()
        if len(out) > 128:
            raise ValueError("educational token limit exceeded")
    return out + [("end", None)]

class Parser:
    def __init__(self, source: str):
        self.tokens = tokenize(source)
        self.i = 0

    def peek(self):
        return self.tokens[self.i][0]

    def take(self, kind):
        if self.peek() != kind:
            raise ValueError(f"expected {kind}, got {self.peek()}")
        token = self.tokens[self.i]
        self.i += 1
        return token[1]

    def expression(self):
        node = self.term()
        while self.peek() in {"+", "-"}:
            op = self.peek(); self.take(op)
            node = (op, node, self.term())
        return node

    def term(self):
        node = self.atom()
        while self.peek() in {"*", "/"}:
            op = self.peek(); self.take(op)
            node = (op, node, self.atom())
        return node

    def atom(self):
        if self.peek() == "-":
            self.take("-")
            return ("neg", self.atom())
        if self.peek() == "+":
            self.take("+")
            return self.atom()
        if self.peek() == "number":
            return ("num", self.take("number"))
        if self.peek() == "name":
            return ("var", self.take("name"))
        self.take("(")
        node = self.expression()
        self.take(")")
        return node

    def parse(self):
        node = self.expression()
        self.take("end")
        return node

def evaluate(node, env: dict[str, float]) -> float:
    op = node[0]
    if op == "num": return node[1]
    if op == "var":
        value = float(env[node[1]])
        if not math.isfinite(value): raise ValueError("nonfinite variable")
        return value
    if op == "neg": return -evaluate(node[1], env)
    a, b = evaluate(node[1], env), evaluate(node[2], env)
    if op == "+": result = a + b
    elif op == "-": result = a - b
    elif op == "*": result = a * b
    elif op == "/": result = a / b
    else: raise ValueError("invalid AST operator")
    if not math.isfinite(result): raise ArithmeticError("nonfinite result")
    return result

def interpret(source: str, env: dict[str, float] | None = None) -> float:
    return evaluate(Parser(source).parse(), {} if env is None else env)

if __name__ == "__main__":
    print(interpret("2*(x+3)-1", {"x": 4}))

I. Retention and readiness#

Retrieve C02 recursive progress, C05 structural induction, and C09 language versus machine semantics. Advance when you can build an AST by hand, locate the first invalid token, and explain what a type rule does not guarantee. Continue with a scoped extension such as let-bindings and lexical environments before attempting a full compiler.