Recursive-descent parser

Question

The question is to write a recursive-descent parser for a language that contains sentences of form w+w', in which w is an arbitrary string of lowercase chars, w' is the reverse of w, and + the plus character. Examples of this language are:

• racecar+racecar
• example+elpmaxe

I can write a parsing function without recursion using a stack: just keep pushing until hitting '+', after which pop from the stack to check with the input character.

I don't know how to come up with recursive descent parser one. Textbook examples usually do not have such requirements for nonterminals.

Answer 1

You could try recursively popping off the front and the back, with a base case for checking if it’s a “+” when there’s only 3 characters left?

Answer 2

I think you don't actually need a recursive parser here as we can form our parser as

S->w+w' where + is in string itself and not have its actual meaning

• Here we have only one Symbol.
• Recursion is needed when we have multiple symbols and interrelated to each other. If you still want to make it recursive you can do it by

bool check(string S) {
    return recursive_check(S,0,S.size-1);
}

bool recursive_check(string S,int start,int end)
{
    if(end<0)
         return 0;
    if(S[start]=='+')
         return 1;
    if(S[start]==S[end])
         recursive_check(S,start+1,end-1);
    else
         return 0;
}