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

该问题是典型的状态机，其中存在初始状态和“通过”状态。解决方案是让每个状态对应的右侧。我将使用数字 2 表示通过状态的规则。

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

传递表达式是根据传递子表达式定义的。因此，语法总是会在表达式的左侧或右侧生成一个闭包。