爲什麼不能用正則表達式來描述遞歸結構？

有些人可以向我解釋爲什麼你不能使用正則表達式來描述遞歸結構。爲什麼不能用正則表達式來描述遞歸結構？

例如

2014-01-19 shua

這是正規語言正式定義的結果。見http://en.wikipedia.org/wiki/Regular_language –

@ p.s.w.g小心！並非所有在標籤「正則表達式」下運行的東西都等同於正規語言，許多東西都更加強大。 – delnan

@delnann雖然問題被標記爲「正則表達式」，並且沒有語言特定的問題，但是p.s.w.g'語句是適用的（並且在任何情況下都是完全準確的）。 –

因爲一個正則表達式（在正則語言的意義上，至少）對應於有限狀態機。你需要無數個狀態來跟蹤任意級別的嵌套。

2014-01-19 10:25:56

「正則表達式」不再意味着「有限狀態機器」，除非你想進入一個長時間，沒有結果的術語火焰戰爭，只有一半的編程人羣。即使是回溯到同構的休息，更不用說其他擴展。 – delnan

@delnan：我意識到這一點;）但除非進一步限定，我認爲「正則表達式」的意思是「正規語言」... –

這是我的問題，這個假設。根據我的經驗，大多數人使用「正則表達式」來表示「我的語言支持的任何語言」，在大多數情況下，這至少是回溯。 – delnan

即使正則表達式不能通過正式定義表達遞歸，但對於Perl和Ruby等語言，還有'正則表達式'implementations that support recursion。

另外對於python，支持遞歸的alternative regex implementation不在標準庫中。

但是，regular languages再次沒有遞歸結構，所以正式的正則表達式不能按定義表達遞歸結構。

2014-01-19 10:26:38

回答