Search code examples
expressionbnfrepeat

BNF repeating sequence of characters

How do I find a sequence of 3 or more "a" followed by the same number of "b" with a BNF expression?

I know that

{<letter>} or {<letter> | <digit>}

are used for repetitive items occuring zero or more times but I don't know how to get the number of times "a" has repeated to make sure "b" repeats the same number of times

Solution

  • Something like this:

    <valid-string> ::= "aaa" <ab> "bbb"
<ab>           ::= "a" <ab> "b" | ""

    This starts off with three a and three b to take care of the minimum requirement. Then it allows the insertion of a and b at the same time (keeping the amount the same) while repeating itself in the middle of the string.