這個上下文無關文法是一個正則表達式嗎？

Question

我有一個語法定義如下：

A -> aA*b | empty_string 

是A正則表達式？我很困惑如何解釋一個BNF語法。

Answer 1

A似乎是一個BNF語法規則。我不確定你爲什麼會把這與正則表達式混淆起來。你有困惑是因爲它有一個*嗎？所有具有*的內容都不是正則表達式。

Answer 2

不，這個問題實際上並不涉及正則表達式。上下文無關語法指定不能用正則表達式描述的語言。

這裏，A是非終端;也就是說，這是一個必須由生產規則擴展的標誌。鑑於您只有一條規則，它也是您的開始符號 - 此語法中的任何生產必須以A開頭。

生產規則是

(1) A -> aA*b | 
(2)   empty_string 

a和b是終端符號 - 他們是在語言的字母，且不能擴展。當你在左邊沒有更多的非終結者時，你就完成了。

因此，該語言指定的是類似平衡圓括號的字，除了a和b而不是(和)。

例如，您可能會產生ab如下：

A -> aA*b (using 1) 
aAb -> ab (using 2) 

同樣的，你可能會產生aabb：

A -> aA*b (1) 
aAb -> aaA*bb (1) 
aaAbb -> aabb (2) 

甚至aababb：

A -> aA*b 
aA*b -> aabA*b: 
aaba*b -> aababA*b: 
aababA*b: -> aababb 

明白了嗎？明星符號可能有點令人困惑，因爲你已經在正則表達式中看到它，但實際上它在那裏做着同樣的事情。它被稱爲Kleene-closure，它代表了所有可以用0或更多A s製作的單詞。

Answer 3

正則表達式生成正則語言，可以使用狀態機進行分析。

BNF語法是上下文無關文法，其產生上下文無關語言，並且可以用推解析下自動機（堆機）

上下文無關文法所能做的一切常規語法可以和更多。