pushdown parser

import { useEffect, useMemo, useRef, useState } from 'react';

// The grammar this parser implements, shown to the reader as well as
// encoded below. Precedence is structural: expr sits above term, so a term
// binds tighter, and the loops are what make both operators left-associative.
const GRAMMAR = [
  { rule: 'expr', body: "term (('+' | '-') term)*" },
  { rule: 'term', body: "factor (('*' | '/') factor)*" },
  { rule: 'factor', body: "number | '(' expr ')' | '-' factor" },
];

type Tok = {
  type: 'num' | 'op' | 'lparen' | 'rparen';
  value: string;
  start: number;
  end: number;
};

function tokenize(src: string): Tok[] {
  const tokens: Tok[] = [];
  let i = 0;
  while (i < src.length) {
    const c = src[i];
    if (/\s/.test(c)) {
      i++;
      continue;
    }
    if (/[0-9]/.test(c)) {
      let j = i;
      while (j < src.length && /[0-9]/.test(src[j])) j++;
      tokens.push({ type: 'num', value: src.slice(i, j), start: i, end: j });
      i = j;
      continue;
    }
    if ('+-*/'.includes(c)) {
      tokens.push({ type: 'op', value: c, start: i, end: i + 1 });
      i++;
      continue;
    }
    if (c === '(' || c === ')') {
      tokens.push({
        type: c === '(' ? 'lparen' : 'rparen',
        value: c,
        start: i,
        end: i + 1,
      });
      i++;
      continue;
    }
    const err = new Error(`unexpected character '${c}'`);
    (err as Error & { pos?: number }).pos = i;
    throw err;
  }
  return tokens;
}

export type Node =
  | { type: 'num'; value: number }
  | { type: 'unary'; op: string; operand: Node }
  | { type: 'binary'; op: string; left: Node; right: Node };

type Ev =
  | { kind: 'enter'; rule: string }
  | { kind: 'exit'; rule: string }
  | { kind: 'consume'; token: Tok }
  | { kind: 'build'; node: Node; children: number }
  | { kind: 'accept' }
  | { kind: 'error'; message: string; pos: number | null };

// Written as a generator so the UI can drive the parse one event at a time.
// Every enter/exit pair is a push and a pop of the pushdown store; that stack
// is the entire difference between this and the finite automaton on the regex
// page. Verified standalone before being ported: the resulting AST evaluates
// identically to JavaScript's own arithmetic across thousands of randomly
// generated expressions, which pins down precedence and associativity.
function* parseTokens(tokens: Tok[]): Generator<Ev, Node, void> {
  const st = { i: 0 };
  const peek = () => tokens[st.i];
  const atEnd = () => st.i >= tokens.length;

  function fail(msg: string): never {
    const t = peek();
    const err = new Error(
      t ? `${msg} — found "${t.value}"` : `${msg} — input ended`,
    );
    (err as Error & { pos?: number | null }).pos = t ? t.start : null;
    throw err;
  }

  function* parseExpr(): Generator<Ev, Node, void> {
    yield { kind: 'enter', rule: 'expr' };
    let node = yield* parseTerm();
    while (!atEnd() && peek().type === 'op' && '+-'.includes(peek().value)) {
      const op = peek();
      st.i++;
      yield { kind: 'consume', token: op };
      const right = yield* parseTerm();
      node = { type: 'binary', op: op.value, left: node, right };
      yield { kind: 'build', node, children: 2 };
    }
    yield { kind: 'exit', rule: 'expr' };
    return node;
  }

  function* parseTerm(): Generator<Ev, Node, void> {
    yield { kind: 'enter', rule: 'term' };
    let node = yield* parseFactor();
    while (!atEnd() && peek().type === 'op' && '*/'.includes(peek().value)) {
      const op = peek();
      st.i++;
      yield { kind: 'consume', token: op };
      const right = yield* parseFactor();
      node = { type: 'binary', op: op.value, left: node, right };
      yield { kind: 'build', node, children: 2 };
    }
    yield { kind: 'exit', rule: 'term' };
    return node;
  }

  function* parseFactor(): Generator<Ev, Node, void> {
    yield { kind: 'enter', rule: 'factor' };
    if (atEnd()) fail('expected a number, "(" or "-"');
    const t = peek();
    let node: Node;
    if (t.type === 'num') {
      st.i++;
      yield { kind: 'consume', token: t };
      node = { type: 'num', value: Number(t.value) };
      yield { kind: 'build', node, children: 0 };
    } else if (t.type === 'lparen') {
      st.i++;
      yield { kind: 'consume', token: t };
      node = yield* parseExpr();
      if (atEnd() || peek().type !== 'rparen') fail('expected ")"');
      const close = peek();
      st.i++;
      yield { kind: 'consume', token: close };
    } else if (t.type === 'op' && t.value === '-') {
      st.i++;
      yield { kind: 'consume', token: t };
      const operand = yield* parseFactor();
      node = { type: 'unary', op: '-', operand };
      yield { kind: 'build', node, children: 1 };
    } else {
      fail('expected a number, "(" or "-"');
    }
    yield { kind: 'exit', rule: 'factor' };
    return node;
  }

  const node = yield* parseExpr();
  if (!atEnd()) fail('unexpected trailing input');
  yield { kind: 'accept' };
  return node;
}

interface Parsed {
  events: Ev[];
  tokens: Tok[];
  ast: Node | null;
  error: string | null;
}

function parseAll(src: string): Parsed {
  const events: Ev[] = [];
  let tokens: Tok[] = [];
  try {
    tokens = tokenize(src);
    const gen = parseTokens(tokens);
    let res = gen.next();
    while (!res.done) {
      events.push(res.value);
      res = gen.next();
    }
    return { events, tokens, ast: res.value, error: null };
  } catch (e) {
    const err = e as Error & { pos?: number | null };
    events.push({ kind: 'error', message: err.message, pos: err.pos ?? null });
    return { events, tokens, ast: null, error: err.message };
  }
}

function evalNode(n: Node): number {
  if (n.type === 'num') return n.value;
  if (n.type === 'unary') return -evalNode(n.operand);
  const a = evalNode(n.left);
  const b = evalNode(n.right);
  return n.op === '+'
    ? a + b
    : n.op === '-'
      ? a - b
      : n.op === '*'
        ? a * b
        : a / b;
}

function label(n: Node): string {
  return n.type === 'num' ? String(n.value) : n.op;
}
function childrenOf(n: Node): Node[] {
  if (n.type === 'num') return [];
  if (n.type === 'unary') return [n.operand];
  return [n.left, n.right];
}

// ---------- tree layout ----------
const NODE_W = 30;
const NODE_H = 24;
const X_GAP = 14;
const Y_GAP = 46;
const PAD = 10;

interface Placed {
  node: Node;
  x: number;
  y: number;
  children: Placed[];
}

function layout(roots: Node[]): {
  placed: Placed[];
  width: number;
  height: number;
} {
  let cursor = PAD;
  let maxDepth = 0;

  function place(n: Node, depth: number): Placed {
    maxDepth = Math.max(maxDepth, depth);
    const kids = childrenOf(n);
    if (kids.length === 0) {
      const x = cursor + NODE_W / 2;
      cursor += NODE_W + X_GAP;
      return { node: n, x, y: depth * Y_GAP + PAD + NODE_H / 2, children: [] };
    }
    const placedKids = kids.map((k) => place(k, depth + 1));
    const x =
      placedKids.length === 1
        ? placedKids[0].x
        : (placedKids[0].x + placedKids[placedKids.length - 1].x) / 2;
    return {
      node: n,
      x,
      y: depth * Y_GAP + PAD + NODE_H / 2,
      children: placedKids,
    };
  }

  const placed = roots.map((r) => {
    const p = place(r, 0);
    cursor += X_GAP * 2; // gap between separate trees in the forest
    return p;
  });
  return {
    placed,
    width: Math.max(cursor + PAD, 120),
    height: maxDepth * Y_GAP + NODE_H + PAD * 2,
  };
}

function flatten(p: Placed): { nodes: Placed[]; edges: [Placed, Placed][] } {
  const nodes: Placed[] = [];
  const edges: [Placed, Placed][] = [];
  (function walk(n: Placed) {
    nodes.push(n);
    for (const c of n.children) {
      edges.push([n, c]);
      walk(c);
    }
  })(p);
  return { nodes, edges };
}

const PRESETS = [
  {
    label: '1 + 2 * 3',
    src: '1 + 2 * 3',
    note: 'Precedence is structural — term sits below expr, so the multiplication ends up deeper in the tree and therefore binds tighter.',
  },
  {
    label: '(1 + 2) * 3',
    src: '(1 + 2) * 3',
    note: 'Parentheses send the parser back down into expr from inside factor. That is the recursion, and it is what the stack pays for.',
  },
  {
    label: '10 - 3 - 2',
    src: '10 - 3 - 2',
    note: 'Left-associative: the loop in expr folds each new term onto the tree built so far, so this is (10 - 3) - 2 = 5, not 10 - (3 - 2).',
  },
  {
    label: '((((7))))',
    src: '((((7))))',
    note: 'Four nested pairs, and the stack grows to match. A finite automaton has no way to remember how many opening brackets it has seen — this is exactly the aⁿbⁿ problem.',
  },
  {
    label: '-3 * -(1 + 2)',
    src: '-3 * -(1 + 2)',
    note: 'factor refers to itself through the unary minus rule, so negation nests without any extra machinery.',
  },
  {
    label: '1 + * 2',
    src: '1 + * 2',
    note: 'A deliberate syntax error. The parser reaches factor, finds an operator where a value must start, and fails at a precise position.',
  },
];

export default function PushdownParser() {
  const [src, setSrc] = useState(PRESETS[0].src);
  const [presetNote, setPresetNote] = useState(PRESETS[0].note);
  const [step, setStep] = useState(0);
  const [playing, setPlaying] = useState(false);
  const [speed, setSpeed] = useState(320);
  const timer = useRef<number | null>(null);

  const parsed = useMemo(() => parseAll(src), [src]);
  const total = parsed.events.length;
  // Changing the input re-parses, and the effect below resets the step
  // counter -- but not until after this render. In between, `step` can still
  // be a value from the previous, longer parse, so everything downstream
  // reads the clamped value rather than indexing past the end of the events.
  const at = Math.min(step, total);

  useEffect(() => {
    setStep(0);
    setPlaying(false);
  }, [src]);

  useEffect(() => {
    if (!playing) return;
    if (at >= total) {
      setPlaying(false);
      return;
    }
    timer.current = window.setTimeout(() => setStep(at + 1), speed);
    return () => {
      if (timer.current) clearTimeout(timer.current);
    };
  }, [playing, at, speed, total]);

  // Replay the first `step` events to get the state at this point.
  const state = useMemo(() => {
    const stack: string[] = [];
    const forest: Node[] = [];
    let consumed = 0;
    let maxDepth = 0;
    let status: 'parsing' | 'accepted' | 'error' = 'parsing';
    let message: string | null = null;
    let errPos: number | null = null;
    let lastBuilt: Node | null = null;

    for (let i = 0; i < at; i++) {
      const e = parsed.events[i];
      if (e.kind === 'enter') {
        stack.push(e.rule);
        maxDepth = Math.max(maxDepth, stack.length);
      } else if (e.kind === 'exit') {
        stack.pop();
      } else if (e.kind === 'consume') {
        consumed++;
      } else if (e.kind === 'build') {
        forest.splice(forest.length - e.children, e.children);
        forest.push(e.node);
        lastBuilt = e.node;
      } else if (e.kind === 'accept') {
        status = 'accepted';
      } else if (e.kind === 'error') {
        status = 'error';
        message = e.message;
        errPos = e.pos;
      }
    }
    return {
      stack,
      forest,
      consumed,
      maxDepth,
      status,
      message,
      errPos,
      lastBuilt,
    };
  }, [parsed, at]);

  const current = at > 0 ? parsed.events[at - 1] : null;
  const activeRule = state.stack[state.stack.length - 1] ?? null;
  const nextToken = parsed.tokens[state.consumed] ?? null;

  const tree = useMemo(() => layout(state.forest), [state.forest]);
  const flat = useMemo(() => tree.placed.map(flatten), [tree]);

  const done = at >= total;

  return (
    <div className="pda">
      <div className="grammar">
        {GRAMMAR.map((g) => (
          <div
            className={g.rule === activeRule ? 'prod active' : 'prod'}
            key={g.rule}
          >
            <span className="prod-name">{g.rule}</span>
            <span className="prod-arrow">→</span>
            <span className="prod-body">{g.body}</span>
          </div>
        ))}
      </div>

      <div className="field">
        <label htmlFor="pda-input">input</label>
        <input
          id="pda-input"
          type="text"
          value={src}
          onChange={(e) => {
            setSrc(e.target.value);
            setPresetNote('');
          }}
          spellCheck={false}
        />
      </div>

      <div className="tape">
        {parsed.tokens.length === 0 && (
          <span className="tape-empty">no tokens</span>
        )}
        {parsed.tokens.map((t, i) => (
          <span
            key={i}
            className={
              i < state.consumed
                ? 'tok done'
                : i === state.consumed
                  ? 'tok next'
                  : 'tok'
            }
          >
            {t.value}
          </span>
        ))}
      </div>

      <div className="controls">
        <button
          type="button"
          onClick={() => setStep(Math.min(total, at + 1))}
          disabled={done}
        >
          step
        </button>
        <button
          type="button"
          onClick={() => setPlaying((p) => !p)}
          disabled={done && !playing}
        >
          {playing ? 'pause' : 'play'}
        </button>
        <button
          type="button"
          onClick={() => {
            setStep(0);
            setPlaying(false);
          }}
        >
          reset
        </button>
        <button
          type="button"
          onClick={() => {
            setStep(total);
            setPlaying(false);
          }}
          disabled={done}
        >
          finish
        </button>
        <label className="speed">
          speed
          <input
            type="range"
            min={40}
            max={600}
            step={20}
            value={640 - speed}
            onChange={(e) => setSpeed(640 - Number(e.target.value))}
          />
        </label>
        <span className="progress">
          {at} / {total}
        </span>
      </div>

      <div className="panes">
        <div className="pane stack-pane">
          <h3>
            pushdown store
            <span className="depth">
              depth {state.stack.length} · max {state.maxDepth}
            </span>
          </h3>
          <div className="stack">
            {state.stack.length === 0 && (
              <span className="stack-empty">empty</span>
            )}
            {[...state.stack].reverse().map((r, i) => (
              <div className={i === 0 ? 'frame top' : 'frame'} key={i}>
                {r}
              </div>
            ))}
          </div>
        </div>

        <div className="pane tree-pane">
          <h3>
            syntax tree
            <span className="depth">
              {state.forest.length === 0
                ? 'nothing built yet'
                : state.forest.length === 1
                  ? '1 tree'
                  : `${state.forest.length} partial trees`}
            </span>
          </h3>
          <div className="tree-scroll">
            <svg
              width={tree.width}
              height={tree.height}
              role="img"
              aria-label="syntax tree built so far"
            >
              {flat.map((f, fi) => (
                <g key={fi}>
                  {f.edges.map(([p, c], i) => (
                    <line
                      key={i}
                      x1={p.x}
                      y1={p.y + NODE_H / 2}
                      x2={c.x}
                      y2={c.y - NODE_H / 2}
                      stroke="#2a2d31"
                      strokeWidth={1.5}
                    />
                  ))}
                  {f.nodes.map((n, i) => {
                    const isNew = n.node === state.lastBuilt;
                    const isLeaf = n.children.length === 0;
                    return (
                      <g key={i}>
                        <rect
                          x={n.x - NODE_W / 2}
                          y={n.y - NODE_H / 2}
                          width={NODE_W}
                          height={NODE_H}
                          rx={4}
                          className={isNew ? 'n new' : isLeaf ? 'n leaf' : 'n'}
                        />
                        <text
                          x={n.x}
                          y={n.y + 4}
                          textAnchor="middle"
                          className={isNew ? 't new' : 't'}
                        >
                          {label(n.node)}
                        </text>
                      </g>
                    );
                  })}
                </g>
              ))}
            </svg>
          </div>
        </div>
      </div>

      <div className="status">
        {state.status === 'accepted' && parsed.ast && (
          <span className="ok">
            accepted — the tree evaluates to{' '}
            <strong>{evalNode(parsed.ast)}</strong>
          </span>
        )}
        {state.status === 'error' && (
          <span className="bad">
            rejected — {state.message}
            {state.errPos !== null && ` (position ${state.errPos + 1})`}
          </span>
        )}
        {state.status === 'parsing' && (
          <span className="muted-status">
            {current
              ? current.kind === 'enter'
                ? `entered ${current.rule} — pushed`
                : current.kind === 'exit'
                  ? `finished ${current.rule} — popped`
                  : current.kind === 'consume'
                    ? `consumed "${current.token.value}"`
                    : current.kind === 'build'
                      ? 'built a node'
                      : ''
              : nextToken
                ? `ready — next token "${nextToken.value}"`
                : 'ready'}
          </span>
        )}
      </div>

      <div className="presets">
        <span className="group-label">try</span>
        {PRESETS.map((p) => (
          <button
            key={p.label}
            type="button"
            className={p.src === src ? 'active' : ''}
            onClick={() => {
              setSrc(p.src);
              setPresetNote(p.note);
            }}
          >
            {p.label}
          </button>
        ))}
      </div>
      {presetNote && <p className="preset-note">{presetNote}</p>}

      <style>{`
        .pda {
          border: 1px solid #2a2d31;
          background: #0e1113;
          padding: 1.25rem 1rem;
        }
        .pda .grammar {
          border: 1px solid #2a2d31;
          background: #0b0d0f;
          padding: 0.6rem 0.75rem;
          display: flex;
          flex-direction: column;
          gap: 0.25rem;
          font-size: 0.8rem;
          overflow-x: auto;
        }
        .pda .prod {
          display: flex;
          gap: 0.5rem;
          white-space: nowrap;
          color: var(--muted);
          padding: 0.1rem 0.25rem;
          border-left: 2px solid transparent;
        }
        .pda .prod.active {
          border-left-color: var(--accent);
          background: rgba(124, 242, 156, 0.06);
        }
        .pda .prod-name {
          color: #b7bcc4;
          min-width: 3.2rem;
        }
        .pda .prod.active .prod-name {
          color: var(--accent);
        }
        .pda .prod-arrow {
          color: #5f656d;
        }
        .pda .field {
          display: flex;
          flex-direction: column;
          gap: 0.25rem;
          margin-top: 1rem;
        }
        .pda .field label,
        .pda .group-label {
          color: var(--muted);
          font-size: 0.7rem;
          text-transform: uppercase;
          letter-spacing: 0.04em;
        }
        .pda input[type='text'] {
          font-family: var(--mono);
          font-size: 0.9rem;
          color: var(--fg);
          background: rgba(0, 0, 0, 0.4);
          border: 1px solid #2a2d31;
          padding: 0.4rem 0.5rem;
          width: 100%;
          box-sizing: border-box;
        }
        .pda .tape {
          display: flex;
          flex-wrap: wrap;
          gap: 0.3rem;
          margin-top: 0.6rem;
          min-height: 1.9rem;
          align-items: center;
        }
        .pda .tape-empty,
        .pda .stack-empty {
          color: #5f656d;
          font-size: 0.75rem;
        }
        .pda .tok {
          border: 1px solid #2a2d31;
          padding: 0.15rem 0.45rem;
          font-size: 0.8rem;
          color: #b7bcc4;
        }
        .pda .tok.done {
          color: #4e545c;
          border-color: #1e2125;
        }
        .pda .tok.next {
          color: #0b0d0f;
          background: var(--accent);
          border-color: var(--accent);
        }
        .pda .controls {
          display: flex;
          flex-wrap: wrap;
          align-items: center;
          gap: 0.5rem;
          margin-top: 0.9rem;
        }
        .pda button {
          font-family: inherit;
          font-size: 0.75rem;
          color: #8a8f98;
          background: rgba(0, 0, 0, 0.4);
          border: 1px solid #2a2d31;
          padding: 0.25rem 0.6rem;
          cursor: pointer;
        }
        .pda button:hover:not(:disabled) {
          color: #e6e6e6;
        }
        .pda button:disabled {
          opacity: 0.4;
          cursor: default;
        }
        .pda button.active {
          color: #0b0d0f;
          background: var(--accent);
          border-color: var(--accent);
        }
        .pda .speed {
          display: flex;
          align-items: center;
          gap: 0.4rem;
          color: var(--muted);
          font-size: 0.75rem;
        }
        .pda .speed input {
          width: 6rem;
        }
        .pda .progress {
          color: var(--muted);
          font-size: 0.75rem;
          margin-left: auto;
        }
        .pda .panes {
          display: grid;
          grid-template-columns: 9rem 1fr;
          gap: 0.9rem;
          margin-top: 1.1rem;
        }
        .pda .pane h3 {
          font-size: 0.7rem;
          font-weight: normal;
          text-transform: uppercase;
          letter-spacing: 0.04em;
          color: var(--muted);
          margin: 0 0 0.4rem;
          display: flex;
          flex-direction: column;
          gap: 0.1rem;
        }
        .pda .depth {
          text-transform: none;
          letter-spacing: 0;
          color: #5f656d;
          font-size: 0.7rem;
        }
        .pda .stack {
          display: flex;
          flex-direction: column;
          gap: 0.2rem;
          border: 1px solid #2a2d31;
          background: #0b0d0f;
          padding: 0.4rem;
          min-height: 8rem;
          max-height: 16rem;
          overflow-y: auto;
        }
        .pda .frame {
          border: 1px solid #2a2d31;
          padding: 0.15rem 0.4rem;
          font-size: 0.75rem;
          color: #8a8f98;
          text-align: center;
        }
        .pda .frame.top {
          color: var(--accent);
          border-color: var(--accent);
        }
        .pda .tree-scroll {
          border: 1px solid #2a2d31;
          background: #0b0d0f;
          overflow: auto;
          min-height: 8rem;
          max-height: 16rem;
        }
        .pda .n {
          fill: rgba(0, 0, 0, 0.4);
          stroke: #2a2d31;
        }
        .pda .n.leaf {
          stroke: #3a3f45;
        }
        .pda .n.new {
          fill: rgba(124, 242, 156, 0.14);
          stroke: var(--accent);
        }
        .pda .t {
          font-family: var(--mono);
          font-size: 12px;
          fill: #b7bcc4;
        }
        .pda .t.new {
          fill: var(--accent);
        }
        .pda .status {
          margin-top: 0.8rem;
          font-size: 0.8rem;
          min-height: 1.2rem;
        }
        .pda .ok {
          color: var(--accent);
        }
        .pda .ok strong {
          font-weight: normal;
        }
        .pda .bad {
          color: #d98a8a;
        }
        .pda .muted-status {
          color: var(--muted);
        }
        .pda .presets {
          display: flex;
          flex-wrap: wrap;
          align-items: center;
          gap: 0.4rem;
          margin-top: 1rem;
          padding-top: 0.9rem;
          border-top: 1px solid #2a2d31;
        }
        .pda .preset-note {
          color: var(--muted);
          font-size: 0.78rem;
          margin: 0.7rem 0 0;
        }
        @media (max-width: 34rem) {
          .pda .panes {
            grid-template-columns: 1fr;
          }
          .pda .stack {
            min-height: 0;
            flex-direction: row;
            flex-wrap: wrap;
          }
        }
      `}</style>
    </div>
  );
}