Search code examples
grammarbnf

BNF for comma separated sequence?


Can't come up with a BNF grammar for the sequence of characters (possibly empty), separated by comma, but not starting or ending with a comma,

So this is OK:

  <--- Empty sequence is ok!
A
A,B
A,B,C

This is NOT ok:

A,
,A
A,,B
AB

The empty case throws me off. What I got so far is:

<char-seq> ::= <empty> | <char> , <char-seq> | <char>

but this produces strings like A, :-(


Solution

  • The empty char sequence is what gives you the trouble. You need a rule that matches a non-empty sequence to be separate from the rule that matches both an empty and a non-empty one, like this:

    <char-seq> ::= <empty> | <non-empty-char-seq>
    <non-empty-char-seq> ::= <char> | <char> , <non-empty-char-seq>