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.
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.