Search code examples
bnf

Empty string as base case in BNF recursion?

I'm writing a small grammar as an exercise for class and my professor didn't really get too specific with what qualifies a legal BNF expression in terms.

The BNF grammar is supposed to recognize strings in this form: AB, AABB, AAABBB, A...B... (general form: AnBn)

So, what I got up to was writing:

<S> --> A<S>B | ""

My simple yes/no question is whether or not this is legal in BNF, and if not why?

<...> represents a non-terminal, I have no idea if that's convention or what not

Solution

  • Yes, this is acceptable BNF. You can see an example of this on the Wikipedia entry in the example about US postal addresses.

    Typically, though, I've seen the empty string represented as ε.