Recursive descent parser 易于理解的解释

Question

谁能用简单的术语向我解释什么是递归下降解析器？

我一直在尝试获取它。在wikipedia.

中解释的真的很模糊

Recursive Descent Parser is a kind of top-down parser built as a set of recursive procedures each implementing a production rule of the grammar.

那么，我做对了吗？解析器是一个程序，它以预定义的顺序一个一个地执行命令，每次执行的每个命令都具有相同的含义，但它会根据输入以某种方式调整输出，这意味着每次输入的调整都可能不同已更改。

我还是不明白为什么要用递归这个词。

Answer 1

首先，一堆术语。

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

一个语法是一种语言语法的定义。语言是一组（可能是无限的）所有语法正确的集合"sentences."一个句子是一系列符号。

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

现在我们可以用一个例子使这个更具体：所有可能的平衡括号序列的简单语言。例如，字符串“()”将是该语言的成员，“()()()”和“((()))”也是如此。我们的语言不会包含不平衡括号的字符串：“(”和“())”不是我们语言的一部分。

这种语言的语法可以这样写：

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

这里，S是一个非终结符号，具体来说就是开始符号。每行代表语法中的一个产生式。更有趣的语言有更多的非终结符号和更多的产品。

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

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

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

对于许多（但不是全部）语法，您可以使用一种特定样式的解析器实现，称为 递归下降解析器。基本思想是编写与语法中的产生式相对应的函数。每个函数都可以调用其他函数来检查子字符串。他们甚至可以给自己打电话（这就是 "recursion" 发挥作用的地方）。

让我们以不同的方式重新编写语法：

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

竖线表示"or"。所以S可以用( P代替或空串

现在假设我们写了两个函数 ParseS 和 ParseP。这些函数可以看到输入字符串的其余部分，如果字符串的下一位与相应的产生式匹配，则 return 为真。在伪代码中：

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 可以调用 ParseS.

[*] 嗯，差不多。它实际上有点过于简单化了。正确的解析器会检查以确保在 return 最终的 true 之前没有更多的输入。正如所写的那样，这个将接受前缀是该语言成员的任何字符串。这在实践中很容易解决，但它会在已经太长的答案中引入分散注意力的细节。

Recursive descent parser 易于理解的解释

Recursive descent parser easy to get explanation

recursion

parsing

recursive-descent