regex實現(xiàn)背后的理論

解答動態(tài)

• 

  這不是實施的問題。不幸的是，不同的解析方法具有相似的名稱。
  NFAs和DFAs（有限狀態(tài)機）只能識別常規(guī)語言。正則表達式是一種指定正則語言的方法，它們可以被編譯成有效的nfa或dfa來識別該語言。這些都是在本科CS課程中教授的。
  Perl中所謂的“regexes”及其許多模仿者的名字聽起來像“regular expression”的縮寫，它們在語法上類似于sed和awk的正則表達式，但它們不是正則表達式。它們實際上是回溯解析器的規(guī)范。回溯解析器并不局限于識別常規(guī)語言。（regex這個名字是拉里·沃爾的錯。他慎重地決定不稱它們?yōu)椤罢齽t表達式”，因為他知道它們不是，但他應(yīng)該發(fā)明一個完全不同的名稱。）
  您不需要基于NFA/DFA的正則表達式匹配的侏羅紀實現(xiàn)；流行語言可以使用現(xiàn)代維護的庫。但是它們?nèi)鄙貾erl風(fēng)格regex的許多特性，而且它們也沒有提供太多的交換。它們當(dāng)然有更好的最壞情況性能，但是回溯解析器的病態(tài)最壞情況可以通過修改regex來修復(fù)，而不會失去回溯的額外靈活性。他顯然想讓你相信，regex庫的作者對正規(guī)語言的理論一無所知，如果他們剛剛學(xué)習(xí)了標準的本科CS課程，那么他們將以一種不同的方式實現(xiàn)他們的庫，并使它們變得更快。那是假的。這樣實現(xiàn)Perl風(fēng)格的正則表達式是不可能的，他知道這一點。Perl風(fēng)格正則表達式的流行在很大程度上可能是由于其靈活的特性集遠遠超出了任何真正的正則表達式庫中可用的特性集。關(guān)鍵的引語是一：大部分實際上，Perl中的正則表達式匹配已經(jīng)足夠快了。不過，如圖所示，可以編寫Perl非常慢地匹配的所謂“病態(tài)”正則表達式。相反，對于Thompson NFA實現(xiàn)來說，沒有病理性的正則表達式。
  在后面的文章中，Cox給出了與實際應(yīng)用相關(guān)的示例世界：
  示例包括使用（.*）（.*）（.*）（.*）（.*）拆分五個空格分隔的字段，或者在不首先列出常見情況的情況下使用替換項。
  
• End