递归下降分析器易于理解的解释

Question

递归下降分析器易于理解的解释

parsingrecursionrecursive-descent

3

请用简单的语言解释一下递归下降分析器是什么？

我在理解上遇到了困难，wikipedia 的解释很模糊。

递归下降分析器是自顶向下的一种语法分析器，它由一组递归过程构成，每个过程实现文法中的一个产生式规则。

所以，我的理解正确吗？这个分析器是一个程序，按预定顺序逐个执行命令，每次执行命令时具有相同的含义，但根据输入会以某种方式调整输出，这意味着根据不同的输入，调整可能每次都不同。

但我仍然不明白为什么在这里使用递归这个词。

- Yaroslav

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adrian McCarthy · Accepted Answer

首先，一些术语。

解析器是一种软件，可以检查文本输入是否符合某种语法的句法正确性。解析器还可以将文本输入转换为其他软件更容易使用的表示形式。

语法是语言句法的定义。语言是所有句法正确的“句子”的（可能无限）集合。句子是符号序列。

语法用一组产生式来描述。 产生式是规则，告诉您如何用其他符号序列替换符号序列。

现在我们可以通过一个例子使这更加具体：平衡括号的所有可能序列的简单语言。例如，字符串“（）”将是该语言的成员，如“（）（）（）”和“（（（）））”。我们的语言不包含不平衡括号的字符串：“（”和“（））”不属于我们的语言。

该语言的语法可以写成以下形式：

S ::= ""
S ::= '(' S ')' S

这里，S 是一个非终结符号，特别地，它是起始符号。每行表示语法中的一个产生式。更有趣的语言将具有更多的非终结符和更多的产生式。

如果你想生成我们语言中的有效字符串，你从字符串S开始，然后迭代地应用产生式规则来替换任何非终结符号，在你的字符串中加入新的序列。

所以我们从S开始，选择一个产生式规则进行应用。假设我们选择第二个，我们得到( S ) S。由于我们的字符串中仍然有非终结符，我们必须继续进行。如果我们再次用第二个规则替换第一个S，我们得到( ( S ) S ) S。现在让我们开始选择第一个规则，它说我们可以用空字符串替换一个S。（我写成了""，但有时你会看到人们使用希腊字母ε来表示。）如果我们将这个规则应用于字符串中所有剩余的S，我们最终得到( ( ) )，这是语言中的一个有效序列。

好的，但现在我们想要走另一条路。我们获得一个字符串作为输入，想知道它是否属于这个语言。这就是解析器的工作。

对于许多（但不是全部）语法，你可以使用特定风格的解析器实现，称为递归下降解析器。基本想法是编写与语法中产生式相对应的函数。每个函数可以调用其他函数来检查子字符串。它们甚至可以调用自己（这就是“递归”发挥作用的地方）。

让我们稍微改写一下我们的语法：

S ::= '(' P | ""
P ::= S ')' S

竖杠符号表示“或”。因此，S可以被替换为( P 或空字符串。

现在假设我们编写两个名为ParseS和ParseP的函数。这些函数可以查看剩余的输入字符串，并在下一段字符串与相应的产生式匹配时返回true。伪代码如下：

bool ParseS() {
  if next character is '(' {
    skip the `(`
    return ParseP()
  }
  return true;  // handles the empty string
}

bool ParseP() {
  if ParseS() and the next character is `)` {
    skip the ')'
    return ParseS();
  }
  return false;
}

这些函数共同构成了我们语言的递归下降解析器。它们告诉我们输入字符串是否符合语法定义的语言，这就是解析器的基本定义。因为ParseS可以调用ParseP，而ParseP又可以调用ParseS，所以它是递归的。

实际上有点过于简化了。正确的解析器应该在返回最终true之前检查确保没有更多的输入。按照现有的方式，这个解析器将接受任何前缀为语言成员的字符串。实际上很容易解决，但是这会在已经太长的答案中引入分散注意力的细节。