Language Theory §

Why the hierarchy matters for compilers: a regular grammar can be recognized by a finite-state machine (no memory beyond the current state), which is exactly what a tokenizer does. A context-free grammar requires a stack (unbounded memory), which is what a parser uses. This is why tokenization is “easier” than parsing: it needs less memory and simpler logic.

Example grammar (arithmetic):

E → E + T | T
T → T * F | F
F → ( E ) | id

Here $V = \{E, T, F\}$, $\Sigma = \{+, *, (, ), id\}$, $S = E$. The grammar is context-free because every production has a single non-terminal on the left.

The broader decidability and complexity questions (“can we always decide if a string is in the language?”, “how fast?”) are studied in Theory of Computation.

DFA (Deterministic Finite Automaton): a set of states, a transition function $\delta: Q \times \Sigma \to Q$, one start state, and a set of accept states. At each step, exactly one transition is possible. Tokenizers are DFAs: the current state encodes “I am inside a number”, “I am inside a string literal”, etc.

NFA (Nondeterministic Finite Automaton): allows multiple transitions from a state on the same symbol (or $\epsilon$-transitions). NFAs are equivalent in power to DFAs but can be more compact. Tools like flex build an NFA from regexes, then determinize it into a DFA.

Pushdown Automaton (PDA): a finite automaton augmented with a stack. The stack allows it to match nested structures (parentheses, blocks). This is the theoretical model behind all context-free parsers. In practice, parsers do not run a PDA directly; they use table-driven algorithms (LL, LR) or recursive descent that simulate the PDA’s stack with the call stack or an explicit stack.

The mapping grammar class → automaton → parser strategy gives a unifying framework: the more memory the automaton needs, the more complex the parser algorithm.

Lexical analysis is a regular language problem: the set of valid tokens is described by regular expressions. Tools like lex/flex generate C code from regex specifications. The DFA states track what kind of token is being read (number, identifier, string, comment, etc.).

Maximal munch: the tokenizer always takes the longest possible match. a++ → a, ++ (not a+, +). a->b → a, ->, b (not a-, >b).

Preprocessing: many languages (C, C++) have a preprocessor that handles #include, #define, and conditional compilation before tokenization.

Why tokenization is separate from parsing: the regular-language restriction means the lexer can be a simple, fast table-driven loop with no backtracking. The parser then works on a clean token stream, free from character-level concerns. This separation is a direct consequence of the Chomsky hierarchy: regular ⊂ context-free.

Recursive descent: hand-written top-down parser; one function per grammar rule. Simple, debuggable, but limited to LL(1) grammars (no left recursion). Used in many language implementations (e.g., Go’s compiler, Python’s ast module).

Shift-reduce (LR): maintain a stack of tokens and states. Shift: push the next token. Reduce: replace the top of the stack with a non-terminal when it matches a production. The conflict (shift-reduce, reduce-reduce) determines whether a grammar is LR(1). LR parsers handle left-recursive grammars naturally, which is why they are the workhorse of C/C++/Java compilers.

PEG (Parsing Expression Grammar): uses ordered choice ($e_1 / e_2$ tries $e_1$ first, falls back to $e_2$ only if $e_1$ fails). This makes PEGs unambiguous by construction (the first successful alternative wins). However, PEGs do not always terminate: left-recursive rules (e.g., expr: expr '+' term) cause infinite recursion and must be rewritten (e.g., expr: term ('+' term)*). PEG parsers are used in the peg crate (formerly rust-peg) for Rust, in PEP 617 (the PEG-based parser in CPython 3.9+), and in the parsimonious third-party library for Python.

REPL (Read-Eval-Print Loop): an interactive environment that reads an expression, evaluates it, prints the result, and loops. It requires an evaluator that maintains a persistent environment across expressions (variables defined in one expression are visible in the next). Languages with a REPL (Lisp, Scheme, Python, Ruby, Elixir) are well-suited to exploratory programming and teaching.

Homoiconicity: the language’s data structures (e.g., Lisp s-expressions) are the same as its code. (+ 1 2) is both a list and a program. This enables macros (code that manipulates code at compile time), because the macro system can read and rewrite the program’s own data structures. Most mainstream languages (C, Java, Python) are not homoiconic; their syntax is not directly representable as a data structure.

These properties interact with Control Flow and Semantics: a REPL’s persistent environment is essentially a long-lived scope, and homoiconicity affects how control-flow constructs can be extended via macros.

Structure:

• Product types (tuples, structs): $A \times B$. AoS (Array of Structs): [{x, y}, {x, y}, ...]. SoA (Struct of Arrays): [{x, x, ...}, {y, y, ...}]. SoA is cache-friendly for SIMD.
• Sum types (enums, tagged unions): $A + B$. Exhaustive pattern matching.
• Function types: $A \to B$.

Functionality:

• Duck typing: “if it quacks like a duck…” (Python, JavaScript). No static check; errors at runtime.
• Strong vs. weak typing: strong types do not allow implicit conversions (Rust, Haskell); weak types do (JavaScript: "1" + 1 = "11").
• Nominal vs. structural: nominal types are distinct by name (struct Point1 {x, y} ≠ struct Point2 {x, y}); structural types are compatible if their shapes match (TypeScript, Go interfaces).
• Hindley–Milner type inference: infer types from usage without annotations. $f x = x + 1$ infers $f: \text{Num} a \Rightarrow a \to a$.
• Polymorphism: parametric (generics: $\forall a. [a] \to [a]$) and ad hoc (overloading: + for Int and Float).
• Subtyping: $A \leq B$ means values of $A$ can be used where $B$ is expected. Contravariance: function parameters are contravariant ($(A \to C) \leq (B \to C)$ if $B \leq A$).

Type checking is the semantic-analysis phase in the Compilation pipeline, and the types it assigns determine the semantics of Control Flow and Semantics (e.g., what a match must cover).

This is an LR(1) grammar (standard arithmetic with precedence: * binds tighter than +).

Parse (shift-reduce):

1. Shift a → stack: a
2. Reduce a → F → stack: F
3. Reduce F → T → stack: T
4. Reduce T → E → stack: E
5. Shift + → stack: E +
6. Shift b → stack: E + b
7. Reduce b → F → T → stack: E + T
8. Shift * → stack: E + T *
9. Shift c → stack: E + T * c
10. Reduce c → F → stack: E + T * F
11. Reduce T * F → T → stack: E + T
12. Reduce E + T → E → stack: E ✓

AST:

    +
   / \
  a   *
     / \
    b   c

The * is a child of +, not a sibling, reflecting that b * c is evaluated first.