帶有至少一個Kleene星號的上下文無關文法

Question

我正在嘗試創建上下文無關語法，該語法通過至少一個Kleene星號在{a，b}上生成所有正則表達式。什麼我迄今所做的是：

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

我想這可以生成所有的正則表達式，但我不能讓我的周圍頭是如何使至少一個Kleene星需要定義它在那個表達中。

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 

傳遞表達式是通過傳遞子表達式來定義的。因此，語法將始終在表達式的左側或右側生成閉包。