He estado explorando escribir un intérprete muy básico/limitado en javascript como ejercicio. Todo iba bien hasta que introduje el concepto de LOOP.
Dado el siguiente guión:
LOOP 2 A LOOP 3 B END LOOP 4 C LOOP 5 D END E END F ENDEl algoritmo debe visitar los tokens internos en la siguiente secuencia:
ABBBCDDDDDECDDDDDECDDDDDECDDDDDEFABBBCDDDDDECDDDDDECDDDDDECDDDDDEFLo siguiente funciona, pero requiere muchas iteraciones sobre los tokens. Es una mejora con respecto a un enfoque de corte anterior que usé que expandía manualmente los bucles, pero está lejos de ser óptimo.
/** * 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/
¿Cuál es una mejor manera de lograr este enfoque basado en matriz utilizando un solo paso a través del script, o en el peor de los casos, 2 pases, pero no pases N-LOOP?
No necesita saber la posición del end coincidente del ciclo cuando comienza a interpretarlo. Todo lo que necesitas registrar es la posición a la que saltar cuando te encuentres con el siguiente end , pero hasta entonces solo continúa interpretando token por token.
Estas posiciones, junto con los respectivos contadores, se pueden almacenar en una estructura de pila.
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 result; }; console.log(interpret(parse(script))); He simplificado un poco la estructura para usar los bucles do - while , por lo que nunca tendría que omitir el cuerpo del bucle. En un código de bytes verdadero, emitido por un analizador, los objetivos de salto (tanto de ida como de vuelta) serían parte de las propias instrucciones, y solo las "variables" de conteo tendrían que almacenarse en la pila. Los objetivos de salto nunca cambian, por lo que deberá generarlos solo una vez en la función de parse .