如何使用非递归堆栈编写递归函数？

Question

为了尝试在JavaScript中实现PEG而不会使旧版浏览器从堆栈溢出中崩溃,我想制作一个解析表达式语法,以非递归方式解析字符串.你怎么做到这一点？感到心灵弯曲.

假设你有这样的结构:

• A grammar有很多表达方式
• 一个expression有很多matchers
• A matcher有很多tokens(或者更好的词)
• A token可以指向另一个expression,也可以是原始字符串或正则表达式.因此,如果它指向另一个表达式,则这是递归开始的位置.

所以说你定义这样的层次结构:

var grammar = new Grammar('math');
var expression = grammar.expression;

expression('math')
  .match(':number', ':operator', ':number', function(left, operator, right){
    switch (operator) {
      case '+': return left + right;
      case '-': return left - right;
      case '*': return left * right;
      case '/': return left / right;
    }
  });

expression('number')
  .match(/\d+/, parseInt);

expression('operator')
  .match('+')
  .match('-')
  .match('*')
  .match('/');

var val = grammar.parse('6*8'); // 42

当你调用时grammar.parse,它从根表达式开始(它与它的名字相同,所以"math").然后它遍历每个匹配器,然后遍历每个标记,如果标记是表达式,则递归.基本上这个(解析器将跟踪它匹配模式的字符串的偏移/位置;这只是伪代码):

function parse(str, expression, position) {
  var result = [];

  expression.matchers.forEach(function(matcher){
    matcher.tokens.forEach(function(token){
      var val;
      if (token.expression) {
        val = parse(str, token.expression, position);
      } else {
        val = token.parse(str, position);
      }
      if (val) result.push(val);
    });
  });

  return result;
}

parse('6*8', grammar.root, 0);

因此,对于一个简单的表达式,例如6*8递归非常少,但您可以快速找到具有多层嵌套的复杂表达式.加上乘以所有这些嵌套的for循环嵌套,堆栈变大(我不实际使用forEach,我用的循环,但在for循环中调用大部分时间的函数,所以它最终被相当多相同).

问题是,你如何"扁平化"？而不是做递归,你如何做到这一点,所以它基本上是这样的:

while (token = stack.pop()) {
  val = token.parse(val);
  if (val) result.push(val);
}

我不是在寻找如何实现这个特定PEG问题的解决方案的细节,我更倾向于寻找以非递归方式跟踪递归状态的一般方法.

Answer 1

一般来说，您要做的就是在代码中编写一个堆栈，然后将 \xe2\x80\x9clocal\xe2\x80\x9d 变量放入您保留的 \xe2\x80\x9cstack 框架\xe2\x80\x9d 上下文对象中在那个堆栈上。然后，在进行 \xe2\x80\x9c 递归调用 \xe2\x80\x9d 的地方，存储当前堆栈帧并为新的当前上下文创建一个新堆栈帧。执行 \xe2\x80\x9creturn\xe2\x80\x9d 只是反转操作的问题。它并不是特别复杂，但它确实使代码有点混乱。唯一需要注意的是，当您完成解析表达式时，您会到达堆栈的底部（这样尾随标记和丢失标记就不会导致问题）。

\n\n

这非常类似于用机器代码维护的堆栈所发生的情况，只不过您不限于原始值，并且因此可以使事情变得更加整洁（在数据结构级别）。

\n\n

如果您有时间，请考虑编写（或使用其他人的）LR(1) 解析器。它们维护的系统堆栈非常少，并且比您自制的 LL(k) 语法更好地处理语法中的许多邪恶情况。然而，它们的工作原理比您现在所拥有的要神秘得多。

\n