Блог

Я изучал написание очень простого / ограниченного интерпретатора на javascript в качестве упражнения. Все шло хорошо, пока я не ввел концепцию циклов.

Учитывая следующий сценарий:

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

Алгоритм должен посетить внутренние токены в следующей последовательности:

 ABBBCDDDDDECDDDDDECDDDDDECDDDDDEFABBBCDDDDDECDDDDDECDDDDDECDDDDDEF
 

Следующее делает свое дело, но для этого требуется много повторений по токенам. Это улучшение по сравнению с предыдущим подходом к нарезке, который я использовал, когда вручную расширял петли, но он далек от оптимального.

 /**
 * 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]);
}
 

https://jsfiddle.net/5wpa8t4n/

Каков лучший способ реализовать этот подход на основе массива, используя один проход через скрипт или, в худшем случае, 2 прохода, но не N-циклических проходов?

Вам не нужно знать положение совпадения end цикла, когда вы начинаете его интерпретировать. Все , что вам нужно записать, — это позиция, в которую нужно вернуться при встрече со следующим end , но до тех пор просто продолжайте интерпретировать токен за токеном.

Эти позиции вместе с соответствующими счетчиками могут храниться в структуре стека.

 const script = `
DO
  A
  DO
    B
  LOOP 3
  DO
    C
    DO
      D
    LOOP 5
    E
  LOOP 4
  F
LOOP 2
`

const parse = (script) =>
  script
    .replace(/[W_] /g, " ")
    .split(" ")
    .filter(Boolean);

const interpret = (code) => {
  let loops = []; // Active loops: iteration count and jump target
  let ip = 0; // instruction pointer

  let result = "";
  while (ip < code.length) {
    const instruction = code[ip];
    switch (instruction) {
      case "DO": {
          ip;
        loops.push({count: 0, start: ip});
      } break;
      case "LOOP": {
        const limit = Number(code[  ip]);
        const {count, start} = loops.pop();
        if (count < limit) {
          loops.push({count: count 1, start});
          ip = start; // jump back
        } else {
            ip;
        }
      } break;
      default: {
          ip;
        result  = instruction; // a print statement
      } break;
    }
  }
  return resu<
};

console.log(interpret(parse(script))); 

Я немного упростил структуру, чтобы использовать do while циклы, поэтому мне никогда не придется пропускать тело цикла. В истинном байтовом коде, выдаваемом синтаксическим анализатором, цели перехода (как туда, так и обратно) были бы частью самих инструкций, и в стеке нужно было бы хранить только количество «переменных». Цели прыжка никогда не меняются, поэтому вам нужно будет сгенерировать их только один раз в parse функции.