summaryrefslogtreecommitdiff
path: root/src/toys/turing/js/parser.js
diff options
context:
space:
mode:
Diffstat (limited to 'src/toys/turing/js/parser.js')
-rw-r--r--src/toys/turing/js/parser.js141
1 files changed, 0 insertions, 141 deletions
diff --git a/src/toys/turing/js/parser.js b/src/toys/turing/js/parser.js
deleted file mode 100644
index dd65613..0000000
--- a/src/toys/turing/js/parser.js
+++ /dev/null
@@ -1,141 +0,0 @@
-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;
-}