JavaScript实现简易解释器时解析LOOP循环的优化方案咨询

正在练习用JavaScript编写一个功能十分有限的基础解释器，此前所有功能运行正常，直到引入LOOP循环概念后遇到了性能瓶颈。

测试用例 #

测试脚本如下：

LOOP 2
  A
  LOOP 3
    B
  END
  LOOP 4
    C
    LOOP 5
      D
    END
    E
  END
  F
END

算法预期输出的token访问顺序为：

ABBBCDDDDDECDDDDDECDDDDDECDDDDDEFABBBCDDDDDECDDDDDECDDDDDECDDDDDEF

现有实现的问题 #

当前实现可正确运行，但需要对tokens数组进行大量重复遍历，虽然比手动展开循环的切片方案有所优化，但性能仍远未达到最优，问题核心在于每次遇到LOOP都需要嵌套遍历查找对应的END标记，遍历次数随循环嵌套层级上升而激增。
原有核心代码如下：

/**
 * In practice, we'll grab each token as we read the script,
 * but to keep this simple and focus on the loop algorithm,
 * we can cheat and make an array of all the tokens.
 */

const getTokens = (s) => s.replace(/[\W_]+/g, " ").split(" ").filter(Boolean);

/* Temp vars - ideally, I'd like to solve this with arrays. */
const start = []; // Loop start indices
const end = []; // Loop end indices
const counts = []; // Times to loop
const completed = []; // Loops completed

for (let i = 0; i < tokens.length; i++) {
  const token = tokens[i];

  if (token === "LOOP") {
    if (start.length == 0 || i > start[start.length - 1]) {
      // Add new loop index if we haven't seen it before
      start.push(i); // Store the loop index
      counts.push(Number(tokens[i + 1])); // The loop count is always next LOOP token
      completed.push(0); // Initialize with 0 completed at index

      // Find the end index for the loop
      // Note: This is the slowest part.
      let skip = 0;
      for (let j = i + 2; j < tokens.length; j++) {
        if (tokens[j] == "LOOP") {
          skip++; // Increase nest depth
        } else if (tokens[j] == "END") {
          if (skip == 0) {
            end.push(j); // Found matching loop close
            break;
          }
          skip--;
        }
      }
    }

    i++; // Skip over the loop count
    continue;
  } else if (token === "END") {
    let j;
    for (j = 0; j < end.length; j++) {
      if (end[j] == i) break; // Found matching end index
    }
    const isCompleted = completed[j] == counts[j] - 1;
    if (!isCompleted) {
      i = start[j] + 1;
      completed[j]++;
      for (let k = j + 1; k < start.length; k++) {
        completed[k] = 0; // Reset nested loops in between
      }
    }
    continue;
  }

  console.log(tokens[i]);
}

优化需求 #

寻找更优的基于数组的实现方案，支持最多对脚本做2次遍历即可完成解析，避免每次遇到LOOP都做N次遍历的问题。

完全可以实现仅两次遍历完成解析：

• 第一次遍历：预计算所有LOOP与END的对应关系、每个LOOP的循环次数，仅需一次线性遍历，时间复杂度O(n)
• 第二次遍历：执行脚本，直接复用预计算的映射关系即可，无需再次嵌套查找

具体实现代码 #

const getTokens = (s) => s.replace(/[\W_]+/g, " ").split(" ").filter(Boolean);

function runScript(scriptStr) {
  const tokens = getTokens(scriptStr);
  const tokenLen = tokens.length;
  // 预计算映射表，第一次遍历
  const loopStartToMeta = new Array(tokenLen); // 存LOOP索引对应的{ count, endIdx }
  const loopEndToStart = new Array(tokenLen); // 存END索引对应的LOOP起始索引
  const loopStack = [];

  for (let i = 0; i < tokenLen; i++) {
    const token = tokens[i];
    if (token === 'LOOP') {
      loopStack.push(i);
      // 跳过count位
      i++;
    } else if (token === 'END') {
      const startIdx = loopStack.pop();
      const count = Number(tokens[startIdx + 1]);
      loopStartToMeta[startIdx] = { count, endIdx: i };
      loopEndToStart[i] = startIdx;
    }
  }

  // 执行阶段，第二次遍历
  const output = [];
  const activeLoops = []; // 栈存当前活跃循环的{ remaining, endIdx }
  let i = 0;
  while (i < tokenLen) {
    const token = tokens[i];
    if (token === 'LOOP') {
      const meta = loopStartToMeta[i];
      // 循环次数为1不需要入栈，直接走一遍就行
      if (meta.count > 1) {
        activeLoops.push({ remaining: meta.count - 1, endIdx: meta.endIdx });
      }
      // 跳转到LOOP后的第一个执行token
      i += 2;
    } else if (token === 'END') {
      const topLoop = activeLoops.at(-1);
      // 如果当前END是栈顶循环的结束，且还有剩余次数
      if (topLoop && topLoop.endIdx === i) {
        if (topLoop.remaining > 0) {
          topLoop.remaining--;
          // 跳回循环开始后的第一个执行token
          i = loopEndToStart[i] + 2;
        } else {
          activeLoops.pop();
          i++;
        }
      } else {
        i++;
      }
    } else {
      output.push(token);
      i++;
    }
  }
  return output.join('');
}

// 测试
const testScript = `LOOP 2
  A
  LOOP 3
    B
  END
  LOOP 4
    C
    LOOP 5
      D
    END
    E
  END
  F
END`;
console.log(runScript(testScript));

优化点说明 #

1. 预计算阶段用栈匹配LOOP和END，仅需一次线性遍历，彻底解决原有每次遇到LOOP都嵌套查找END的性能问题
2. 执行阶段直接复用预计算的映射关系，无需额外遍历查找循环对应关系
3. 循环次数为1的场景无需入栈，进一步减少运行时开销
4. 原有实现查找END对应LOOP需要遍历end数组，优化后直接通过数组下标取对应关系，时间复杂度从O(k)降到O(1)，k为嵌套层级

内容的提问来源于stack exchange，提问作者noobcode