Regular Expression 100% cpu - please help

[Gareth James via .NET 247]

I have an expression that when run uses 100% cpu for over 1minute.
I can change the expression so this does not happen, but couldsome one explain why this happens so that I don't do it again
expression -->
Departing:</td>.*?</span>(?<departi ngAirportName>. *?)\(
(?<airportCode> \w+)\).*?<li>
(?<departingCit y>[\w\s]+),\s*
(?<departingCou ntry>[\w\s]+).*?
(?<departingTim eHours>\d+):
(?<departingTim eMins>\d+).*?Ar riving:.*?</span>
(?<arrivalAirpo rtName>.*?)\(
(?<arrivelAirpo rtCode>\w+)\).* ?<li>
(?<arrivalCity>[\w\s]+),\s*
(?<arrivalCount ry>[\w\s]+).*?
(?<arrivalTimeH ours>\d+):
(?<arrivalTimeM ins>\d+).*?href =".*?\(
(?<linkURL>.*?) \).*?>
(?<carrier>[\w\s]+)\(
(?<flightNumber >.*?)\).*?
text to search -->
l10 bb2"><span class="textBold ">Wed 16 March 05</span>, 1stop(s)</td>
</tr>
<tr class="h32 dotsbottom canvas">
<td class="text l10">Duration: </td>
<td class="textBold l10">14h00</td>
</tr>
<tr height="60">
<td class="text l10 t15 vtop">Departing :</td>
<td class="text l10 t15 vtop">
<ul class="list">
<li>
<span class="bold">
</span>
Newcastle Int'l (NCL),</li><li>Newcastl e, United Kingdom
</li>
<li>
<span class="bold">12 :05</span> Wed
</li>
</ul>
</td>
</tr>
<tr height="60">
<td class="text l10 t15 vtop">Arriving: </td>
<td class="text l10 t15 vtop">
<ul class="list">
<li>
<span class="bold">
Terminal 1,
</span>
Heathrow (LHR),</li><li>London, United Kingdom
</li>
<li>
<span class="bold">13 :20</span> Wed
</li>
</ul>
</td>
</tr>
<tr>
<td class="textBold l10 t10 b10 vtop"><imgsrc='/images/en/FE/BE/Tailfin/smBA.gif' alt="tailfin" width="30"heigh t="25" alt="" /></td>
<td class="text l10 t10 b10">
<ul class="list">
<li>
Non-stop
</li>
<li>
<ahref="javascr ipt:popupWithNo Return('/otpbvpl/Jsp/opodo/FlifoInfoServle t?BV_SessionID= @@@@1016786011. 1110564120@@@@& BV_EngineID=ccd eaddediigiijcef ecenhdhhldfnk.0 &locale=en_GB&F LIGHT_NUMBER=13 27&AIRLINE_CODE =BA&B_DATE=2005 03161205', 'opodo', 700, 450)"class="lin k">British Airways (BA 1327) ></a>
</li>
<li>
Airplane type - 320
</li>
<li>
Economy restricted
</li>
<li>
<script type="text/javascript" language="JavaS cript">
// work around for netscape 7.0.1/2 encoded characters in link
var eticketURL ='http://www.opodo.co.uk :80/otpbvpl/Global/Page/logObs_FS.jsp?l ocale=en_GB&Fra meSetRequired=Y es&sLoc=https%3 A%2F%2Fopodouk. custhelp.com%2F cgi-bin%2Fopodouk.c fg%2Fphp%2Fendu ser%2Fstd_alp.p hp%3Fp_prod_lvl 1%3D1%26p_prod_ lvl2%3D30&sURLT ype=RightNow';
document.write( '<ahref="javasc ript:popupWithN oReturn(eticket URL,\\'faq\\',7 50,600)" class="link">e-ticket available ></a>');
</script>
</li>
<li>
</li>
</ul>
</td>
</tr>
<tr class="h32">
<td class="textBold l10 beigeBG dotstop bb2"colspan="2" >Connection:</td>
</tr>
<tr height="152">
<td class="text l10 t10 b10 beigeBG dotsbottom vtop">
<ul class="list">
<li>

</li>
<li>

</li>
<li>

</li>
<li>

</li>
</ul>
</td>
<td class="text l10 t10 b10 beigeBG dotsbottom vtop"width="100 %">
<ul class="list">
<li><span class="bold">13 :20</span> Wed - <spanclass="bol d">14:35</span> Wed</li>
<li>
Change plane
</li>
<li class="pt10">
Stop-over duration: 1h15
</li>
</ul>
</td>
</tr>
<tr height="60">
<td class="text l10 t15 vtop">Departing :</td>
<td class="text l10 t15 vtop">
<ul class="list">
<li>
<span class="bold">
Terminal 1,
</span>
Heathrow (LHR),</li><li>London, United Kingdom
</li>
<li>
<span class="bold">14 :35</span> Wed
</li>
</ul>
</td>
</tr>
<tr height="60">
<td class="text l10 t15 vtop">Arriving: </td>
<td class="text l10 t15 vtop">
<ul class="list">
<li>
<span class="bold">
Terminal 1,
</span>
Narita (NRT),</li><li>Tokyo, Japan
</li>
<li>
<span class="bold">11 :05</span> Thu
</li>
</ul>
</td>
</tr>

<tr>
<td class="textBold l10 t10 b10 vtop"><imgsrc='/images/en/FE/BE/Tailfin/smBA.gif' alt="tailfin" width="30"heigh t="25" alt="" /></td>
<td class="text l10 t10 b10">
<ul class="list">
<li>
Non-stop
</li>
<li>
<ahref="javascr ipt:popupWithNo Return('/otpbvpl/Jsp/opodo/FlifoInfoServle t?BV_SessionID= @@@@1016786011. 1110564120@@@@& BV_EngineID=ccd eaddediigiijcef ecenhdhhldfnk.0 &locale=en_GB&F LIGHT_NUMBER=7& AIRLINE_CODE=BA &B_DATE=2005031 61435', 'opodo', 700, 450)"class="lin k">British Airways (BA 7) ></a>
</li>
<li>
Airplane type - 744

</li>
<li>
World Traveller Plus
</li>
<li>
<script type="text/javascript" language="JavaS cript">
// work around for netscape 7.0.1/2 encoded characters in link
var eticketURL ='http://www.opodo.co.uk :80/otpbvpl/Global/Page/logObs_FS.jsp?l ocale=en_GB&Fra meSetRequired=Y es&sLoc=https%3 A%2F%2Fopodouk. custhelp.com%2F cgi-bin%2Fopodouk.c fg%2Fphp%2Fendu ser%2Fstd_alp.p hp%3Fp_prod_lvl 1%3D1%26p_prod_ lvl2%3D30&sURLT ype=RightNow';
document.write( '<ahref="javasc ript:popupWithN oReturn(eticket URL,\\'faq\\',7 50,600)" class="link">e-ticket available ></a>');
</script>
</li>
<li>
</li>
</ul>
</td>
</tr>

--------------------------------
From: Gareth James

-----------------------
Posted by a user from .NET 247 (http://www.dotnet247.com/)

<Id>OM9NFlkZgka V6dNmUKo5Ag==</Id>

[Niki Estner]

"Gareth James via .NET 247" <an*******@dotn et247.com> wrote in
news:ev******** ******@TK2MSFTN GP10.phx.gbl...

I have an expression that when run uses 100% cpu for over 1 minute.
I can change the expression so this does not happen, but could some one
explain why this > happens so that I don't do it again

I just entered your expression and your sample string into expresso, and it
didn't take a second to run it. I guess it takes forever on *other* input
string, am I right? e.g. if the expression can't find a match, right?

I'm not 100% certain, but I think things like this : "(...[\w\s]+).*?" will
make it take forever: The [\w\s]+ part will first attempt to match all
word/space characters that follow (like "United Kingdom"), then ".*?" will
eat up any number of characters until the next subexpression matches. Now,
if any subexpression after this one doesn't match, the regex will have to
backtrack: It'll match "United Kingdo" for [\w\s]+, and try all the
subexpressions after this one again, and so on. Now, if you have more than
one expression of that kind, every possible combination will be tried, which
will take some time...

If you can, don't use ".*" or ".*?" at all, because they often lead to much
more possible combinations than you really want. Use some more suitable
character class if there is one. Also, you can (I think) forbid backtracking
on many of those subexpressions: use a greedy subexpression like
(?>[\w\s]+).
or
(?>Departing:</td>.*?</span>(?<departi ngAirportName>. *?)\()
This way the engine won't look at these subexpressions once it has found a
match for them.

Niki