这个嵌套算法的名称是什么

What is the name of this nesting algorithm?

本文关键字：是什么 算法 嵌套      更新时间：2023-09-26

我正在编写一个包含嵌套作用域的解析器。在解析器计算完标记的深度后，我想将它们嵌套在适当的位置，以简化标记生成器的工作。

将{ 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]]

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

值得注意的是，您在某种程度上混合了标记器和解析器的角色。令牌的"深度"是一个解析时间属性，在令牌化过程中通常不会对其进行标记。相反，一个典型的标记化器会吐出这样的东西（使用L和R作为假想的左右分隔符）：

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

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

我不知道你特别提到的算法，但我相信你在解析器方面看到的是一个从左到右自上而下的解析器，特别是LL（1）解析器。

相关文章：