是否有常規語言來表示正則表達式？

具體來說，我注意到正則表達式本身的語言並不經常。所以，我不能使用正則表達式來解析給定的正則表達式。由於正則表達式本身的語言沒有上下文，因此我需要使用解析器。是否有常規語言來表示正則表達式？

是否有任何方式可以表示正則表達式的方式，結果字符串可以使用正則表達式進行分析？

注意：我的問題不是關於是否有正則表達式來匹配正則表達式的當前語法，而是正如我們現在所知道的那樣是否存在正則表達式的「表示」（可能並不像我們所知他們如今天），可以使用正則表達式進行分析。另外，請有人刪除dup，因爲它不是dup。我在問完全不同的東西。我已經知道當前正則表達式的語言是不正規的（這是我如何開始我的原始問題）。

來源

2013-10-23 dhruvbird

先寫* *「所有可能的正則表達式集」*（這是你的輸入語言）。 **否**，在正式語言中，您無法編寫正則表達式來驗證「正則表達式」。因爲「所有可能的正則表達式的集合」都是完整的CFL，所以我們不能爲CFL編寫正則表達式。 –

我的問題不是關於是否有正則表達式來匹配正則表達式的當前語法，而是正如我們今天所知道的那樣是否存在正則表達式的「表示」（可能不像我們今天所瞭解的那樣整齊）可以使用正則表達式進行分析。另外，請有人刪除dup，因爲它不是dup。我在問完全不同的東西。 – dhruvbird

是的，您可以將問題標記爲請求重新打開。（如果你注意到還有重新打開的按鈕） –

答案可能是NO。

正如您已經指出的那樣，所有可能的正則表達式本身並不是一個常規集合。任何TRUE正則表達式（不擴展）可以轉換爲有限自動機（FA）。如果正則表達式可以用自己可以解析的形式表示，那麼FA也可以通過正則表達式進行解析。

但據我所知，這是不可能的。 RE本身可以簡化爲三種基本操作（根據Dragon Book）：

級聯： ab
交替：例如， a|b
kleen closure：例如a*

的KLEEN閉合可以匹配的字符數限制的，但它無法知道多少字符相匹配。只是想這樣的情況：你想連續匹配3個a s。那麼相應的正則表達式是/aaa/。但是如果你想要比賽4,5,6 ... a s？只有一個RE的解析器無法知道a的確切數量。所以它沒有給予任意表達式的正確匹配。但是，RE解析器必須匹配無限不同形式的RE。根據你的表情，正則表達式不能匹配所有的可能性。（可能這就是爲什麼在詞法分析中使用RE的原因）RE中的每個字符都是一個標記（不包括那些轉義字符）。但是爲了解析RE，無論它是如何轉換的，都必須面對NFA/DFA/TREE ...... RE本身無法解析的所有等效結構。

來源

2013-10-23 07:17:05

你也可以添加RE使用圓括號，並且使用RE不能驗證圓括號的平衡（如果非常conman example = a^n b^n） –

是否有常規語言來表示正則表達式？

回答

相關問題