递归下降解析器很容易得到解释

Question

有人能用简单的术语解释一下递归下降解析器是什么吗？

我被困在试图得到它.在维基百科中解释的确非常模糊.

递归下降解析器是一种自上而下的解析器,它构建为一组递归过程,每个过程都实现了语法的生成规则.

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

而且我仍然不明白为什么在这里使用递归这个词.

Answer 1

首先是一堆术语.

一个解析器是一种软件,可以检查文本输入语法正确根据一些语法.解析器还可以将文本输入转换为另一种表示,以便其他软件更容易使用.

一个语法是语言的语法的定义.一个语言是所有的语法正确的(可能是无限的)集合"的句子." 句子是一系列符号.

用一组制作描述语法. 制作是一些规则,告诉您如何用其他符号序列替换符号序列

现在我们可以用一个例子来说明这一点:具有所有可能的平衡括号序列的简单语言.例如,字符串"()"将是语言的成员,"()()()"和"((()))"也是如此.我们的语言不包含一串不平衡的括号:"("和"())"不是我们语言的一部分.

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

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

这里,S是非终端符号,具体地,是起始符号.每行代表语法中的一个产生.更有趣的语言有更多的非终端符号和更多的制作.

如果要为我们的语言生成有效字符串,请从字符串开始S,然后迭代地应用生成规则以使用新序列替换字符串中的任何非终结符号.

所以我们从开始S,并选择一个生产规则来应用.假设我们选择第二个,我们得到( S ) S.由于我们仍然在字符串中有非终端,我们必须继续前进.如果我们S再次用第二个规则替换第一个规则,我们就得到了( ( S ) S ) S.现在让我们开始选择第一个规则,它说我们可以用S空字符串替换.(我写它"",但有时你会看到人们用希腊小量了点.)如果我们将此规则应用于所有剩余的S字符串中的ES,我们结束了( ( ) ),这是在语言的有效序列.

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

对于许多(但不是全部)语法,可以使用称为递归下降解析器的特定样式的解析器实现.基本思想是编写与语法中的作品相对应的函数.每个函数都可以调用其他函数来检查子字符串.他们甚至可以自称(这是"递归"发挥作用的地方).

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

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

[*]好吧,差不多.它实际上有点过于简单了.正确的解析器会检查以确保在返回最终的true之前没有其他输入.如上所述,这个将接受任何前缀是该语言成员的字符串.这在实践中很容易解决,但它会在已经太长的答案中引入令人分心的细节.