如何構建基於給定的正則表達式

Question

我試圖找出如何基於給定的正則表達式來構建一個CFG（上下文無關文法）一個CFG。 例如，（AB）*（A | B） 我覺得這是一種算法穿過去，卻是讓人有些困惑。 這是我走到這一步：

S->aAB; 
    A->aAb|empty; 
    B->a|b; 

這是否正確？ 任何幫助，將不勝感激。

Answer 1

構建CFG三部分，每部分爲a，(ab)*和(a|b)。

爲(a|b)，你有B -> a | b權。

(ab)*將意味着像ab，abab，ababab等字符串。所以A -> abA | empty將是正確的生產。

因此，完整的語法變爲：

S -> aAB 
A -> abA | empty 
B -> a | b 

注：A -> aAb | empty會得到像ab，aabb，aaabbb等，這是不是一個regular language，而不可能代表regular expression字符串。

Answer 2

的另一種方式構造的上下文無關文法對給定正則表達式是：

1. 構建其接受的語言相同的正則表達式的有限狀態機。在狀態機的狀態，並且其具有的形式X -> t Y的用於每個狀態的規則：
2. 創建一個語法其端子是那些在正則表達式的字母表，它的非端子（1到或對應1）在終端符號t上從狀態X轉換到狀態Y。如果您的CFG符號允許，每個最終狀態F都會得到一個形式爲F -> epsilon的規則。如果您的CFG符號不允許這樣的規則，則對於從狀態X至最終狀態F.每個轉變上端子t，產生規則X -> t（除了規則已經描述X -> t F）。其結果是常規的語法中，上下文無關文法的是服從每個右手側具有至多一個非末端的附加約束。

對於給出的例子，假設我們構建以下FSA（接受相同的語言正則表達式的很多）：

由此看來，這是簡單的推導以下常規語法：

S -> a A1 
A1 -> a A2 
A2 -> b B3 
B3 -> a A2 
B3 -> a A4 
B3 -> b B5 
A1 -> a A4 
A1 -> b B5 
A4 -> epsilon 
B5 -> epsilon 
epsilon -> 

或者，如果我們不想用空右側規則，丟棄語法的最後三個規則，並添加：

A1 -> a 
A1 -> b 
B3 -> a 
B3 -> b 

與其他方法相比，這種方法的缺點是所產生的語法是更詳細的比它需要的是，人和的優勢，該推導可以完全機械的，這意味着它更容易得到正確而不必努力思考。