Adding some of my favorite toys

1 files changed, 141 insertions, 0 deletions

diff --git a/src/toys/turing/js/parser.js b/src/toys/turing/js/parser.js
new file mode 100644
index 0000000..dd65613
--- /dev/null
+++ b/src/toys/turing/js/parser.js
@@ -0,0 +1,141 @@
+export function parseInstructionSet(code) {
+  const lines = code.split("\n");
+  const instructions = [];
+  const config = {
+    startState: null,
+    acceptStates: new Set(),
+    rejectStates: new Set()
+  };
+
+  lines.forEach((line, lineIndex) => {
+    const withoutComments = line.replace(/\/\/.*$/, "").trim();
+    if (!withoutComments) {
+      return;
+    }
+
+    if (withoutComments.startsWith("#")) {
+      applyDirective(withoutComments.slice(1).trim(), config, lineIndex + 1);
+      return;
+    }
+
+    const parts = withoutComments.split(/\s+/).filter(Boolean);
+    if (parts.length !== 5) {
+      throw new Error(`Invalid instruction on line ${lineIndex + 1}: expected 5 parts, received ${parts.length}`);
+    }
+
+    const [fromState, readSymbol, writeSymbol, direction, toState] = parts;
+    if (!config.startState) {
+      config.startState = fromState;
+    }
+
+    instructions.push({ fromState, readSymbol, writeSymbol, direction, toState, line: lineIndex + 1 });
+  });
+
+  if (!instructions.length) {
+    throw new Error("No instructions provided");
+  }
+
+  const { acceptStates, rejectStates } = deriveHaltingStates(instructions, config);
+  const rules = buildRuleMap(instructions);
+
+  return {
+    rules,
+    startState: config.startState ?? instructions[0].fromState,
+    acceptStates,
+    rejectStates
+  };
+}
+
+function applyDirective(directiveLine, config, lineNumber) {
+  if (!directiveLine) {
+    return;
+  }
+
+  const [keyword, ...values] = directiveLine.split(/\s+/).filter(Boolean);
+  if (!keyword) {
+    return;
+  }
+
+  switch (keyword.toLowerCase()) {
+    case "start": {
+      if (values.length !== 1) {
+        throw new Error(`#start on line ${lineNumber} must provide exactly one state`);
+      }
+      config.startState = values[0];
+      break;
+    }
+    case "accept":
+    case "accepts":
+    case "accepting": {
+      if (!values.length) {
+        throw new Error(`#${keyword} on line ${lineNumber} must include at least one state`);
+      }
+      values.forEach((value) => config.acceptStates.add(value));
+      break;
+    }
+    case "reject":
+    case "rejects":
+    case "rejecting": {
+      if (!values.length) {
+        throw new Error(`#${keyword} on line ${lineNumber} must include at least one state`);
+      }
+      values.forEach((value) => config.rejectStates.add(value));
+      break;
+    }
+    default:
+      throw new Error(`Unknown directive '#${keyword}' on line ${lineNumber}`);
+  }
+}
+
+function deriveHaltingStates(instructions, config) {
+  const fromStates = new Set();
+  const toStates = new Set();
+  const allStates = new Set();
+
+  instructions.forEach(({ fromState, toState }) => {
+    fromStates.add(fromState);
+    toStates.add(toState);
+    allStates.add(fromState);
+    allStates.add(toState);
+  });
+
+  // Remove any overlap so rejects always win
+  config.rejectStates.forEach((state) => config.acceptStates.delete(state));
+
+  if (!config.acceptStates.size) {
+    for (const state of allStates) {
+      if (!fromStates.has(state) && toStates.has(state) && !config.rejectStates.has(state)) {
+        config.acceptStates.add(state);
+      }
+    }
+  }
+
+  return {
+    acceptStates: Array.from(config.acceptStates),
+    rejectStates: Array.from(config.rejectStates)
+  };
+}
+
+function buildRuleMap(instructions) {
+  const rules = new Map();
+
+  instructions.forEach(({ fromState, readSymbol, writeSymbol, direction, toState, line }) => {
+    const dir = direction.toUpperCase();
+    if (!["L", "R", "S"].includes(dir)) {
+      throw new Error(`Invalid direction '${direction}' on line ${line}. Use L, R, or S.`);
+    }
+
+    const key = `${fromState}:${readSymbol}`;
+    if (rules.has(key)) {
+      throw new Error(`Duplicate rule for state '${fromState}' reading '${readSymbol}' (line ${line})`);
+    }
+
+    rules.set(key, {
+      nextState: toState,
+      writeSymbol,
+      direction: dir
+    });
+  });
+
+  return rules;
+}