Compilers, interpreters & automata

1 · Compiled vs interpreted vs bytecode VM essential

There are three broad ways to run source code. Compiled (C, Rust, Go): a compiler translates the whole program to native machine code ahead of time; you ship a binary. Interpreted (classic shell, early BASIC): a program reads and executes your source line by line. Bytecode VM (Python, Java, C#): the source is compiled to portable bytecode, then a virtual machine executes that bytecode.

Python is not purely interpreted: it compiles your .py to bytecode first. You can see the bytecode with the standard-library dis module:

show_bytecode.pyimport dis
def add(a, b):
    return a + b
dis.dis(add)

  2           RESUME                   0

  3           LOAD_FAST_LOAD_FAST      1 (a, b)
              BINARY_OP                0 (+)
              RETURN_VALUE

2 · The compiler pipeline essential

Whether it ends in machine code or an interpreter, a language processor's front end is the same assembly line: lexing chops text into tokens, parsing builds an AST (abstract syntax tree) that captures structure, and the back end does code generation or direct evaluation.

3 · Build a lexer advanced

A lexer (tokenizer) turns a flat string into a list of meaningful tokens, discarding whitespace. For arithmetic we need numbers, the four operators, and parentheses:

lexer.pydef tokenize(src):
    tokens, i = [], 0
    while i < len(src):
        ch = src[i]
        if ch.isspace():
            i += 1
        elif ch.isdigit():
            j = i
            while j < len(src) and src[j].isdigit():
                j += 1
            tokens.append(("NUM", int(src[i:j])))
            i = j
        elif ch in "+-*/()":
            kind = {"+": "PLUS", "-": "MINUS", "*": "STAR",
                    "/": "SLASH", "(": "LP", ")": "RP"}[ch]
            tokens.append((kind, ch))
            i += 1
        else:
            raise SyntaxError(f"unexpected char {ch!r}")
    tokens.append(("EOF", None))
    return tokens

for t in tokenize("3 + 4 * 2"):
    print(t)

('NUM', 3)
('PLUS', '+')
('NUM', 4)
('STAR', '*')
('NUM', 2)
('EOF', None)

4 · A grammar in BNF intermediate

A grammar defines which token sequences are valid. Written in BNF (Backus–Naur Form), our arithmetic grammar encodes precedence — *// bind tighter than +/- — by layering the rules:

grammar.bnfexpr   ::= term  (("+" | "-") term)*
term   ::= factor (("*" | "/") factor)*
factor ::= NUMBER | "(" expr ")"

# "expr is made of terms joined by + or -"
# "term is made of factors joined by * or /"   <- tighter binding
# "factor is a number or a parenthesised expr" <- recursion / grouping

5 · A recursive-descent parser & evaluator advanced

A recursive-descent parser is one function per grammar rule, calling each other exactly as the grammar nests. Here we fold evaluation into the parse (a one-pass interpreter): each rule returns the numeric value of what it parsed, so the calculator is complete.

parser.pyclass Parser:
    def __init__(self, tokens):
        self.toks, self.pos = tokens, 0
    def peek(self):  return self.toks[self.pos]
    def eat(self, kind):
        tok = self.toks[self.pos]
        if tok[0] != kind:
            raise SyntaxError(f"expected {kind}, got {tok[0]}")
        self.pos += 1
        return tok

    def parse(self):
        v = self.expr()
        self.eat("EOF")
        return v
    def expr(self):                      # expr ::= term (("+"|"-") term)*
        v = self.term()
        while self.peek()[0] in ("PLUS", "MINUS"):
            op = self.eat(self.peek()[0])[0]
            v = v + self.term() if op == "PLUS" else v - self.term()
        return v
    def term(self):                      # term ::= factor (("*"|"/") factor)*
        v = self.factor()
        while self.peek()[0] in ("STAR", "SLASH"):
            op = self.eat(self.peek()[0])[0]
            v = v * self.factor() if op == "STAR" else v // self.factor()
        return v
    def factor(self):                    # factor ::= NUM | "(" expr ")"
        tok = self.peek()
        if tok[0] == "NUM":
            self.eat("NUM"); return tok[1]
        self.eat("LP"); v = self.expr(); self.eat("RP")
        return v

def calc(src):
    return Parser(tokenize(src)).parse()

print("3 + 4 * 2      =", calc("3 + 4 * 2"))      # * binds tighter
print("(3 + 4) * 2    =", calc("(3 + 4) * 2"))    # parens override
print("20 / 4 - 1     =", calc("20 / 4 - 1"))

3 + 4 * 2      = 11
(3 + 4) * 2    = 14
20 / 4 - 1     = 4

6 · Regular languages & finite automata advanced

The lexer above recognised numbers with a loop — that loop is really a finite automaton. A DFA (deterministic finite automaton) is the simplest machine: a set of states, a transition for each input symbol, a start state, and some accepting states. It has no memory beyond its current state, so it recognises exactly the regular languages — the same class that regular expressions describe.

Let's build a DFA that accepts binary strings representing numbers divisible by 3. The trick: the state is the running remainder mod 3. Reading a bit b updates r = (r*2 + b) % 3; accept if we end in remainder 0.

dfa.py# states 0,1,2 = value-so-far mod 3;  start = 0;  accept = {0}
TRANSITION = {
    (0, "0"): 0, (0, "1"): 1,
    (1, "0"): 2, (1, "1"): 0,
    (2, "0"): 1, (2, "1"): 2,
}
ACCEPT = {0}

def accepts(s):
    state = 0                             # start state
    for ch in s:
        state = TRANSITION[(state, ch)]   # deterministic step
    return state in ACCEPT

for s in ["0", "11", "110", "1001", "1010", "111"]:
    print(f"{s:>5}  (={int(s, 2):>2})  accepted={accepts(s)}")

    0  (= 0)  accepted=True
   11  (= 3)  accepted=True
  110  (= 6)  accepted=True
 1001  (= 9)  accepted=True
 1010  (=10)  accepted=False
  111  (= 7)  accepted=False

7 · The Chomsky hierarchy & the limits of computation professional

Languages form a hierarchy by the power of machine needed to recognise them (Chomsky, 1956). More power = more memory structure:

A DFA can't count unbounded nesting — matching (( )) to arbitrary depth needs a stack, i.e. a context-free grammar (which is why our parser, not the lexer, handles parentheses). At the top sits the Turing machine, the model of everything computable.

Knowledge check check yourself

answer = {
  'C':      'compiled to native machine code  -> executable binary',
  'Python': 'compiled to bytecode -> run by CPython VM (.pyc)',
  'Java':   'compiled to bytecode -> run by JVM, often JIT (.class)',
}
for k, v in answer.items():
    print(k, '->', v)

def tokenize(src):
    toks, i = [], 0
    ops = {'+':'PLUS','-':'MINUS','*':'STAR','/':'SLASH',
           '%':'PERCENT','(':'LP',')':'RP'}
    while i < len(src):
        c = src[i]
        if c.isspace(): i += 1
        elif c.isdigit():
            j = i
            while j < len(src) and src[j].isdigit(): j += 1
            toks.append(('NUM', int(src[i:j]))); i = j
        elif c in ops:
            toks.append((ops[c], c)); i += 1
        else: raise SyntaxError(c)
    toks.append(('EOF', None)); return toks

print(tokenize('10 % 3'))
# [('NUM', 10), ('PERCENT', '%'), ('NUM', 3), ('EOF', None)]

def factor(self):
    tok = self.peek()
    if tok[0] == 'MINUS':          # unary minus
        self.eat('MINUS')
        return -self.factor()
    if tok[0] == 'NUM':
        self.eat('NUM'); return tok[1]
    self.eat('LP'); v = self.expr(); self.eat('RP')
    return v

# with this factor(): calc('-5 + 2') == -3 ; calc('-(3 + 4)') == -7

# states: 0 = start/other, 1 = ends in 'a', 2 = ends in 'ab' (accept)
T = {
    (0,'a'):1, (0,'b'):0,
    (1,'a'):1, (1,'b'):2,
    (2,'a'):1, (2,'b'):0,
}
def accepts(s):
    st = 0
    for c in s: st = T[(st, c)]
    return st == 2

for s in ['ab','aab','abab','ba','a']:
    print(s, accepts(s))
# ab True / aab True / abab True / ba False / a False

# parser builds nodes; evaluation is a separate pass
def ev(node):
    if node[0] == 'num': return node[1]
    op, l, r = node
    a, b = ev(l), ev(r)
    return {'+':a+b, '-':a-b, '*':a*b, '/':a//b}[op]

# AST for 3 + 4 * 2  (built by the parser, precedence preserved):
ast = ('+', ('num', 3), ('*', ('num', 4), ('num', 2)))
print('AST  :', ast)
print('value:', ev(ast))   # 11

# DANGER: eval runs ANY Python -- never on untrusted input
#   eval("__import__('os').system('rm -rf /')")   # catastrophic

# SAFE: our grammar can only ever describe arithmetic.
def safe_calc(src):
    try:
        return Parser(tokenize(src)).parse()
    except SyntaxError as e:
        return f'rejected: {e}'

print(safe_calc('2 + 3 * 4'))            # 14
print(safe_calc("__import__('os')"))     # rejected: unexpected char '_'
print(safe_calc('2 +'))                   # rejected: expected LP, got EOF