时间戳

首页 > 解决方案 > 如何跟踪迭代（非递归）函数的嵌套信息

algorithm - 如何跟踪迭代（非递归）函数的嵌套信息

问题描述

假设我有一个递归下降解析器，它定义了一堆嵌套规则。

Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Value (('*' / '/') Value)*
Value   ← [0-9]+ / '(' Expr ')'

说我是对的 ● 在Value此过程中的第二个：

Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Value (('*' / '/') ●)*
Value   ← [0-9]+ / '(' Expr ')'

这意味着我在这里的某个地方处于嵌套级别让我们说：

Expr
  Sum
    |Product
     +
     Product
    |Product
     -
     Product
       |Value
        *
        Value
       |Value
        *
        ●

递归下降解析时，是递归的，所以Value返回时，我们回到“序列”*解析节点，然后返回Product节点，返回产品序列节点等。所以很容易构建解析树.

但是，假设您想使用迭代堆栈来执行此操作。问题是，如何跟踪嵌套信息，以便您可以在代码中（最终）说：

function handleValue(state, string) {
  // ...
}

function handleValueSequence(state, string) {
  if (state.startedValueSequenceEarlier) {
    wrapItUp(new ValueSequence(state.values))
  }
}

function handleProduct(state, string) {
  // ...
}

function handleProductSequence(state, string) {
  if (state.startedProductSequenceEarlier) {
    wrapItUp(new ProductSequence(state.products))
  }
}

棘手的部分是，这可以任意嵌套，所以你可能有：

Product
  Value
    Product
      Value
        Product
          ...

因此，如果您的函数 likehandleProductSequence除了函数的参数之外没有任何上下文，我不知道它应该如何弄清楚如何“wrapItUp”并最终创建该ProductSequence对象。在我添加的那个state对象中，我试图考虑添加state.stack属性或其他东西的方法，但我不确定那里会发生什么。任何帮助将非常感激。

标签： algorithmparsingrecursiondata-structuresstack

解决方案

您的堆栈必须在控制流中包含“您所在的位置”。在递归下降解析器中，这实际上与您在解析中的位置相同，因此您可以以这种方式编写一个通用的 LL 解析器。就个人而言，我可能会将产品表示为具有标记列表和处理函数的对象。（加上 EBNF 运算符的一些扩展，*如

但是当 LR 解析器生成器已经存在时，很难找到这样做的充分理由，基本上使用这种表示，并且它们可以处理更多的语法。

推荐阅读