javascript - 这种嵌套算法的名称是什么？

Question

我正在编写一个包含嵌套范围的解析器。在解析器计算完标记的深度后，我想就地嵌套它们以简化标记器的工作。

考虑 { depth: 1, value: '...' } 简化为 1，

[1, 2, 3, 3, 2, 1, 3, 2, 1] 应该给出 [1, [2, [3, 3], 2], 1 [[3], 2], [1]]

我用这个递归函数(使用 lodash ，但我想可以理解为普通函数)达到了预期的结果:

var arr = [1, 2, 3, 3, 2, 1, 3, 2, 1];

var tokens = (function nestDeeperTokens(tokenArray, level){

  var nestedTokens = _.reduce(tokenArray, function(m, v, i){
    if (v == level) { m.push(v); return m; }
    if (_.isArray(_.last(m))) { m[m.length - 1].push(v); return m; }
    m.push([v]); return m;
  }, []);

  return _.map(nestedTokens, function(v){
    return _.isArray(v) ? nestDeeperTokens(v, level + 1) : v;
  });

})(arr, 1);

// => [1, [2, [3, 3], 2], 1 [[3], 2], [1]]

是否有这个特定模式/操作的名称？有更好的方法吗？

Answer 1

值得注意的是，您在某种程度上混合了分词器和解析器的 Angular 色。 token 的“深度”是一个解析时间属性，通常不会在 token 化期间标记。相反，一个典型的分词器会吐出类似的东西(使用 L 和 R 作为假想的左右分隔符):

[1, L, 2, L, 3, 3, R, 2, R, 1, L, L, 3, R, 2, R, 1]

解析器的工作是创建“层次结构”并将其转换为有意义的树状或嵌套数组结构。

我不知道您特别提到的目的的算法，但我相信您在解析器方面看到的是一个从左到右的自上而下的解析器，特别是 LL(1) parser .