Recursive in BNF grammar

Question

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
}

http://stackoverflow.com/questions/16165352/why-cant-a-ll-grammar-be-left-recursive — didierc, Jun 18 '14 at 02:07
It is not clear which of your symbols are tokens and which are non-terminals. If only B and C are tokens, then you need to either refactor the grammar or use more lookahead than you do. — n. m. could be an AI, Jun 18 '14 at 03:09
didierc: I will check out this. @n.m.: is `A : B | A '!'` more clear? — Jack, Jun 18 '14 at 03:19
For details on how to build a recursive descent parser, see http://stackoverflow.com/a/2336769/120163 — Ira Baxter, Jun 18 '14 at 03:20
... or restructure your parser. Write down several strings that belong to the language and see how your function would process them. — n. m. could be an AI, Jun 18 '14 at 03:20
Hm. Is B a token? If not, where are its rules? If yes... why are you calling it B? — n. m. could be an AI, Jun 18 '14 at 03:27
Take a look at Pratt parsing: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ — SK-logic, Jun 18 '14 at 06:20
I don't understand how the restructure would be performed... could you give an example from this grammar? `foo: '(' ')' | foo '[' ']'` (now I will really check the links) — Jack, Jun 18 '14 at 19:00
@IraBaxter: You answer solved my question. In special, how to deal with `L = A | L A ;` (exactly what I tried put in my question). If you post as answer here I will accept. Thanks!! — Jack, Jun 21 '14 at 19:03

score 2 · Accepted Answer · edited May 23 '17 at 11:56

2

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.

edited May 23 '17 at 11:56

Community

1
1

answered Jun 21 '14 at 21:49

Ira Baxter

93,541
22
172
341

Recursive in BNF grammar

1 Answers1