Compiler Algorithms

// a tokenizer as a table-driven state machine (the tiny browser's HTML tokenizer is the switch-statement form of this)
const STATES = { start: 0, ident: 1, number: 2, string: 3, op: 4 }
const classify = ch => /[a-zA-Z_$]/.test(ch) ? 'alpha' : /[0-9]/.test(ch) ? 'digit' : ch === '"' ? 'quote' : /\s/.test(ch) ? 'space' : 'other'
// transition table: state × class → [nextState, action]   (action: 'start' a token, 'append', 'emit' and re-read, 'skip')
const T = {
  0: { alpha: [1, 'start'], digit: [2, 'start'], quote: [3, 'start'], space: [0, 'skip'], other: [4, 'start'] },
  1: { alpha: [1, 'append'], digit: [1, 'append'], quote: [0, 'emit'], space: [0, 'emit'], other: [0, 'emit'] },
  2: { digit: [2, 'append'], alpha: [0, 'emit'], quote: [0, 'emit'], space: [0, 'emit'], other: [0, 'emit'] },
  3: { quote: [0, 'emitInclusive'], alpha: [3, 'append'], digit: [3, 'append'], space: [3, 'append'], other: [3, 'append'] },
  4: { alpha: [0, 'emit'], digit: [0, 'emit'], quote: [0, 'emit'], space: [0, 'emit'], other: [4, 'append'] },
}
function* tokenize(src) {
  let state = 0, buf = ''
  for (let i = 0; i <= src.length; i++) {
    const ch = i < src.length ? src[i] : ' ', [next, action] = T[state][classify(ch)]
    if (action === 'start') buf = ch; else if (action === 'append') buf += ch
    else if (action === 'emit') { yield { state, text: buf }; buf = ''; i-- }        // re-read ch in the start state
    else if (action === 'emitInclusive') { yield { state, text: buf + ch }; buf = '' }
    state = next
  }
}
// O(n): one table lookup per character; no backtracking. a regex-based lexer (/\w+|\d+|"[^"]*"|./gy) is the same automaton compiled by the regex engine.
// keywords: check the identifier against a Set after emitting (V8: a perfect hash on length + first chars). the slash ambiguity (/ vs regex):
// the parser tells the tokenizer which to expect (the JS course part 1)

// linear scan register allocation (Poletto & Sarkar), the algorithm behind most JIT backends including V8's (with splitting)
// input: live intervals per SSA value: [start, end] in instruction order. k physical registers.
function linearScan(intervals, k) {
  intervals.sort((a, b) => a.start - b.start)
  const active = []                                    // intervals currently holding a register, sorted by end
  const free = [...REGISTERS]                          // k of them
  for (const iv of intervals) {
    for (let j = 0; j < active.length; ) {             // expire old intervals: free their registers
      if (active[j].end < iv.start) { free.push(active[j].reg); active.splice(j, 1) } else j++
    }
    if (free.length === 0) {                           // spill: the interval that ends last gives up its register
      const last = active[active.length - 1]
      if (last.end > iv.end) { iv.reg = last.reg; last.reg = null; last.spilled = true; active.pop(); insertByEnd(active, iv) }
      else iv.spilled = true
    } else { iv.reg = free.pop(); insertByEnd(active, iv) }
  }
}
// O(n log n) for n intervals (the sort; active is small). vs graph colouring: O(n²) to build the interference graph. JITs cannot afford that.
// a spilled value lives on the stack and is reloaded around uses; V8's allocator splits intervals at use points so a value is spilled only
// across the gap where it is not needed. what you see: --print-opt-code shows mov to/from [rbp-N] slots where pressure was high;
// functions with many simultaneously-live values (big destructurings, wide expressions) spill more.