Limitation of recursive descent parser?

Question

Say I have a simple context free grammar:

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

My simplified recursive descent parser for this grammar looks like:

// 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;
}

The problem is that how can I match "abababc" with this algorithm? It looks like a limitation of recursive descent parser to me, just wanted to confirm, please correct me if my understanding is wrong.

PS: some people mentioned it doesn't need a recursive descent parser, it's a regular expression. I'm interested in understanding the power and limitation of recursive descent parser in this question, not interested in solving it with regular expression. To be more specific, what kind of grammar can be parsed with a recursive descent parser? and what can't.

Is this X = (ab)+ really will be used in the input? Means, that + plus sign is a real plus,or just an option of at least one or more instances? Please clarify. As the example of input which you gave doesn't contain +... — Am_I_Helpful
It looks like a limitation of your unshown code to me, specifically in the methods X() and Y(). Post your attempts. — user207421
It's also really strange to be using a parser for a regular-expression problem. There is no recursion here, so no need for parsing technology. This is not only a context-free grammar, it is a regular expression. — user207421
If you want to understand recursive-descent, set yourself a problem that requires it. This isn't one. You gave the game away yourself by using the term 'greedy'. That's a regular-expression concept, not a recursive-descent concept. In any case until you post your attempts at X() and Y() your question is unanswerable. — user207421

Dour High Arch Dour High Arch · Accepted Answer · 2015-05-27T23:51:34

A recursive-descent version of your code would be:

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;
}

Note that, as @EJP says, this could be done without recursive descent. Recursive descent parses context-free languages. Most programming languages are context-free; notable exceptions include Lisp and C++. Parsing these languages require a recursively-enumerable parser because they allow the meaning of tokens (such as a Lisp macros or C++ template) to change during the parse.

Limitation of recursive descent parser?

1 Answers