Pythonの正規表現

「朔最新版」に寄せられたネタ。 http://～が10回以上現れたらスパムと判定するような正規表現を書くとき、 (.+? http\:\/\/){10}.+? と書くとCPU負荷がすごいことになります。 (http://.+){10} と書くと普通です。

.+ が左側にあるのが駄目なのかな。 BNFだと左再帰とか右再帰とかあって、うまく書かないと無限ループに陥るんですけど、正規表現でもそんな感じの問題があるんですね。原理的にはBNFの話とは違うと思いますが。