Context-free grammar with at least one Kleene star

Question

I'm trying to create the context free grammar which generates all regular expressions over {a,b} with at least one Kleene star. What I've done so far is this:

S ::= A + S | A
A ::= B . A | B
B ::= T | B* | (S)
T ::= a | b | eps

I suppose this can generate all regular expressions, but what I can't get my head around is how to define it so that at least one Kleene star needs to be in that expression.

Answer 1

The problem is typical of state machines, in which there is an initial state, and a "pass" state. The solution is to have right-hand sides corresponding to each state. I'll use the number 2 for the rules that represent the passing states.

S  ::= S2

S2 ::= A + S2 | A2 + S1 | A2
A2 ::= B2 . A | B . A2 | B2
B2 ::= B* | (S2)

S1 ::= A + S1 | A
A  ::= B . A | B
B  ::= T | B* | (S1)
T  ::= a | b | eps

Passing expressions are defined in terms of passing subexpressions. Thus, the grammar will always generate a closure either on the left or the right side of an expression.