regex - 递归下降解析器的局限性？

Question

假设我有一个简单的上下文无关语法:

Z = XY
X = ("ab")+
Y = "abc"

我的这个语法的简化递归下降解析器看起来像:

// takes an input string and returns the length of match, -1 for failure
int Z(str) {
  int len1 = X(str);
  if (len1 >= 0) {
    int len2 = Y(str.substr(length));
    if (len2 >= 0) {
      return len1 + len2; // matches
    }
  }
  return -1; // doesn't match
}
int X(str) {
  // matches 1 or multiple "ab"
  int len = 0;
  while (str.startsWith("ab")) {
    len += 2;
    str = str.substr(2);
  }
  return len > 0 ? len : -1;
}
int Y(str) {
  // matches "abc" exactly
  return str.startsWith("abc") ? 3 : -1;
}

问题是如何用这个算法匹配“abababc”？这对我来说似乎是递归下降解析器的限制，只是想确认一下，如果我的理解有误，请纠正我。

PS:有人提到它不需要递归下降解析器，它是一个正则表达式。我有兴趣了解递归下降解析器在这个问题上的能力和局限性，对用正则表达式解决它不感兴趣。更具体地说，递归下降解析器可以解析什么样的语法？什么不能。

Answer 1

您的代码的递归下降版本将是:

int Z(string s)
{
    int m = X(s);
    if (m < 0)
        return m;

    string sub = s.Substring(m);
    int m2 = Y(sub);
    if (m2 < 0)
    {
        m2 = Z(sub);    // recursive call
        if (m2 < 0)
            return m2;
    }

    return m + m2;
}

int X(string s)
{
    return s.StartsWith("ab") ? 2 : -1;
}

int Y(string s)
{
    return s.Equals("abc") ? 3 : -1;
}

请注意，正如@EJP 所说，这可以在没有递归下降的情况下完成。递归下降解析 context-free语言。大多数编程语言都是上下文无关的；值得注意的异常(exception)包括 Lisp 和 C++。解析这些语言需要 recursively-enumerable解析器，因为它们允许标记(例如 Lisp 宏或 C++ 模板)的含义在解析期间发生变化。