Search code examples
crecursioncompiler-constructionbnfrecursive-descent

Recursive in BNF grammar

Well, I'm not sure how I should write a function using recursive descent parse to parse a grammer like the below. Actually, I'm not sure if I was doing right it...

BNF:

 A : B | A '!'
 B : '[' ']'

pseudo-code:

f()
{
   if(tok is B) 
      parse_b();
      return somethingB
   else if(????) how will I know if it's start of A or I don't need to?
      x = f();
      parse_c();
      return somethingA
}

I was doing this (no check to determine if it's an A but I feel there's something wrong with it):

f()
{
   if(tok is B) 
      parse_b();
      return somethingB
   else
      x = f();
      parse_c();
      return somethingA
}
Solution

  • See my SO answer to another similar question on details on how to build a recursive descent parser.

    In particular it addresses the structure of the parser, and how you can pretty much derive it by inspecting your grammar rules, including handling lists.