/usr/share/doc/racket/guide/Backtracking.html is in racket-doc 6.1-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"/><title>9.8 Backtracking</title><link rel="stylesheet" type="text/css" href="../scribble.css" title="default"/><link rel="stylesheet" type="text/css" href="../racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-style.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../manual-racket.css" title="default"/><link rel="stylesheet" type="text/css" href="../doc-site.css" title="default"/><script type="text/javascript" src="../scribble-common.js"></script><script type="text/javascript" src="../manual-racket.js"></script><script type="text/javascript" src="../manual-racket.js"></script><script type="text/javascript" src="../doc-site.js"></script><script type="text/javascript" src="../local-redirect/local-redirect.js"></script><script type="text/javascript" src="../local-redirect/local-user-redirect.js"></script><!--[if IE 6]><style type="text/css">.SIEHidden { overflow: hidden; }</style><![endif]--></head><body id="doc-racket-lang-org"><div class="tocset"><div class="tocview"><div class="tocviewlist tocviewlisttopspace"><div class="tocviewtitle"><table cellspacing="0" cellpadding="0"><tr><td style="width: 1em;"><a href="javascript:void(0);" title="Expand/Collapse" class="tocviewtoggle" onclick="TocviewToggle(this,"tocview_0");">►</a></td><td></td><td><a href="index.html" class="tocviewlink" data-pltdoc="x"><span style="font-weight: bold">The Racket Guide</span></a></td></tr></table></div><div class="tocviewsublisttop" style="display: none;" id="tocview_0"><table cellspacing="0" cellpadding="0"><tr><td align="right">1 </td><td><a href="intro.html" class="tocviewlink" data-pltdoc="x">Welcome to Racket</a></td></tr><tr><td align="right">2 </td><td><a href="to-scheme.html" class="tocviewlink" data-pltdoc="x">Racket Essentials</a></td></tr><tr><td align="right">3 </td><td><a href="datatypes.html" class="tocviewlink" data-pltdoc="x">Built-<wbr></wbr>In Datatypes</a></td></tr><tr><td align="right">4 </td><td><a href="scheme-forms.html" class="tocviewlink" data-pltdoc="x">Expressions and Definitions</a></td></tr><tr><td align="right">5 </td><td><a href="define-struct.html" class="tocviewlink" data-pltdoc="x">Programmer-<wbr></wbr>Defined Datatypes</a></td></tr><tr><td align="right">6 </td><td><a href="modules.html" class="tocviewlink" data-pltdoc="x">Modules</a></td></tr><tr><td align="right">7 </td><td><a href="contracts.html" class="tocviewlink" data-pltdoc="x">Contracts</a></td></tr><tr><td align="right">8 </td><td><a href="i_o.html" class="tocviewlink" data-pltdoc="x">Input and Output</a></td></tr><tr><td align="right">9 </td><td><a href="regexp.html" class="tocviewselflink" data-pltdoc="x">Regular Expressions</a></td></tr><tr><td align="right">10 </td><td><a href="control.html" class="tocviewlink" data-pltdoc="x">Exceptions and Control</a></td></tr><tr><td align="right">11 </td><td><a href="for.html" class="tocviewlink" data-pltdoc="x">Iterations and Comprehensions</a></td></tr><tr><td align="right">12 </td><td><a href="match.html" class="tocviewlink" data-pltdoc="x">Pattern Matching</a></td></tr><tr><td align="right">13 </td><td><a href="classes.html" class="tocviewlink" data-pltdoc="x">Classes and Objects</a></td></tr><tr><td align="right">14 </td><td><a href="units.html" class="tocviewlink" data-pltdoc="x">Units (Components)</a></td></tr><tr><td align="right">15 </td><td><a href="reflection.html" class="tocviewlink" data-pltdoc="x">Reflection and Dynamic Evaluation</a></td></tr><tr><td align="right">16 </td><td><a href="macros.html" class="tocviewlink" data-pltdoc="x">Macros</a></td></tr><tr><td align="right">17 </td><td><a href="languages.html" class="tocviewlink" data-pltdoc="x">Creating Languages</a></td></tr><tr><td align="right">18 </td><td><a href="concurrency.html" class="tocviewlink" data-pltdoc="x">Concurrency and Synchronization</a></td></tr><tr><td align="right">19 </td><td><a href="performance.html" class="tocviewlink" data-pltdoc="x">Performance</a></td></tr><tr><td align="right">20 </td><td><a href="parallelism.html" class="tocviewlink" data-pltdoc="x">Parallelism</a></td></tr><tr><td align="right">21 </td><td><a href="running.html" class="tocviewlink" data-pltdoc="x">Running and Creating Executables</a></td></tr><tr><td align="right">22 </td><td><a href="More_Libraries.html" class="tocviewlink" data-pltdoc="x">More Libraries</a></td></tr><tr><td align="right">23 </td><td><a href="dialects.html" class="tocviewlink" data-pltdoc="x">Dialects of Racket and Scheme</a></td></tr><tr><td align="right">24 </td><td><a href="other-editors.html" class="tocviewlink" data-pltdoc="x">Command-<wbr></wbr>Line Tools and Your Editor of Choice</a></td></tr><tr><td align="right"></td><td><a href="doc-bibliography.html" class="tocviewlink" data-pltdoc="x">Bibliography</a></td></tr><tr><td align="right"></td><td><a href="doc-index.html" class="tocviewlink" data-pltdoc="x">Index</a></td></tr></table></div></div><div class="tocviewlist"><table cellspacing="0" cellpadding="0"><tr><td style="width: 1em;"><a href="javascript:void(0);" title="Expand/Collapse" class="tocviewtoggle" onclick="TocviewToggle(this,"tocview_1");">▼</a></td><td>9 </td><td><a href="regexp.html" class="tocviewlink" data-pltdoc="x">Regular Expressions</a></td></tr></table><div class="tocviewsublistbottom" style="display: block;" id="tocview_1"><table cellspacing="0" cellpadding="0"><tr><td align="right">9.1 </td><td><a href="regexp-intro.html" class="tocviewlink" data-pltdoc="x">Writing Regexp Patterns</a></td></tr><tr><td align="right">9.2 </td><td><a href="regexp-match.html" class="tocviewlink" data-pltdoc="x">Matching Regexp Patterns</a></td></tr><tr><td align="right">9.3 </td><td><a href="regexp-assert.html" class="tocviewlink" data-pltdoc="x">Basic Assertions</a></td></tr><tr><td align="right">9.4 </td><td><a href="regexp-chars.html" class="tocviewlink" data-pltdoc="x">Characters and Character Classes</a></td></tr><tr><td align="right">9.5 </td><td><a href="regexp-quant.html" class="tocviewlink" data-pltdoc="x">Quantifiers</a></td></tr><tr><td align="right">9.6 </td><td><a href="regexp-clusters.html" class="tocviewlink" data-pltdoc="x">Clusters</a></td></tr><tr><td align="right">9.7 </td><td><a href="regexp-alternation.html" class="tocviewlink" data-pltdoc="x">Alternation</a></td></tr><tr><td align="right">9.8 </td><td><a href="" class="tocviewselflink" data-pltdoc="x">Backtracking</a></td></tr><tr><td align="right">9.9 </td><td><a href="Looking_Ahead_and_Behind.html" class="tocviewlink" data-pltdoc="x">Looking Ahead and Behind</a></td></tr><tr><td align="right">9.10 </td><td><a href="An_Extended_Example.html" class="tocviewlink" data-pltdoc="x">An Extended Example</a></td></tr></table></div></div></div></div><div class="maincolumn"><div class="main"><div class="navsettop"><span class="navleft"><form class="searchform"><input class="searchbox" style="color: #888;" type="text" value="...search manuals..." title="Enter a search string to search the manuals" onkeypress="return DoSearchKey(event, this, "6.1", "../");" onfocus="this.style.color="black"; this.style.textAlign="left"; if (this.value == "...search manuals...") this.value="";" onblur="if (this.value.match(/^ *$/)) { this.style.color="#888"; this.style.textAlign="center"; this.value="...search manuals..."; }"/></form> <a href="../index.html" title="up to the documentation top" data-pltdoc="x" onclick="return GotoPLTRoot("6.1");">top</a></span><span class="navright"> <a href="regexp-alternation.html" title="backward to "9.7 Alternation"" data-pltdoc="x">← prev</a> <a href="regexp.html" title="up to "9 Regular Expressions"" data-pltdoc="x">up</a> <a href="Looking_Ahead_and_Behind.html" title="forward to "9.9 Looking Ahead and Behind"" data-pltdoc="x">next →</a></span> </div><h4 x-source-module="(lib "scribblings/guide/guide.scrbl")" x-part-tag=""Backtracking"">9.8<tt> </tt><a name="(part._.Backtracking)"></a>Backtracking</h4><p>We’ve already seen that greedy quantifiers match the maximal number of
times, but the overriding priority is that the overall match succeed.
Consider</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=regexp.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._regexp-match%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">regexp-match</a></span><span class="hspace"> </span><span class="RktVal">#rx"a*a"</span><span class="hspace"> </span><span class="RktVal">"aaaa"</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">'("aaaa")</span></p></td></tr></table></blockquote><p>The regexp consists of two subregexps: <span class="RktInBG"><span class="hspace"></span><span class="RktIn">a*</span><span class="hspace"></span></span> followed by
<span class="RktInBG"><span class="hspace"></span><span class="RktIn">a</span><span class="hspace"></span></span>. The subregexp <span class="RktInBG"><span class="hspace"></span><span class="RktIn">a*</span><span class="hspace"></span></span> cannot be allowed to match
all four <span class="RktInBG"><span class="hspace"></span><span class="RktIn">a</span><span class="hspace"></span></span>’s in the text string <span class="RktSym">aaaa</span>, even though
<span class="RktInBG"><span class="hspace"></span><span class="RktIn">*</span><span class="hspace"></span></span> is a greedy quantifier. It may match only the first
three, leaving the last one for the second subregexp. This ensures
that the full regexp matches successfully.</p><p>The regexp matcher accomplishes this via a process called
<a name="(tech._backtracking)"></a><span style="font-style: italic">backtracking</span>. The matcher tentatively allows the greedy
quantifier to match all four <span class="RktInBG"><span class="hspace"></span><span class="RktIn">a</span><span class="hspace"></span></span>’s, but then when it becomes
clear that the overall match is in jeopardy, it <span style="font-style: italic">backtracks</span> to a
less greedy match of three <span class="RktInBG"><span class="hspace"></span><span class="RktIn">a</span><span class="hspace"></span></span>’s. If even this fails, as in
the call</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=regexp.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._regexp-match%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">regexp-match</a></span><span class="hspace"> </span><span class="RktVal">#rx"a*aa"</span><span class="hspace"> </span><span class="RktVal">"aaaa"</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">'("aaaa")</span></p></td></tr></table></blockquote><p>the matcher backtracks even further. Overall failure is conceded
only when all possible backtracking has been tried with no success.</p><p>Backtracking is not restricted to greedy quantifiers.
Nongreedy quantifiers match as few instances as
possible, and progressively backtrack to more and more
instances in order to attain an overall match. There
is backtracking in alternation too, as the more
rightward alternates are tried when locally successful
leftward ones fail to yield an overall match.</p><p>Sometimes it is efficient to disable backtracking. For example, we
may wish to commit to a choice, or we know that trying alternatives is
fruitless. A nonbacktracking regexp is enclosed in
<span class="RktInBG"><span class="hspace"></span><span class="RktIn">(?></span><span class="hspace"></span></span>...<span class="RktInBG"><span class="hspace"></span><span class="RktIn">)</span><span class="hspace"></span></span>.</p><blockquote class="SCodeFlow"><table cellspacing="0" cellpadding="0" class="RktBlk"><tr><td><span class="stt">> </span><span class="RktPn">(</span><span class="RktSym"><a href="http://download.racket-lang.org/docs/6.1/html/local-redirect/index.html?doc=reference&rel=regexp.html%23%2528def._%2528%2528quote._%7E23%7E25kernel%2529._regexp-match%2529%2529&version=6.1" class="RktValLink Sq" data-pltdoc="x">regexp-match</a></span><span class="hspace"> </span><span class="RktVal">#rx"(?>a+)."</span><span class="hspace"> </span><span class="RktVal">"aaaa"</span><span class="RktPn">)</span></td></tr><tr><td><p><span class="RktRes">#f</span></p></td></tr></table></blockquote><p>In this call, the subregexp <span class="RktInBG"><span class="hspace"></span><span class="RktIn">?>a+</span><span class="hspace"></span></span> greedily matches all four
<span class="RktInBG"><span class="hspace"></span><span class="RktIn">a</span><span class="hspace"></span></span>’s, and is denied the opportunity to backtrack. So, the
overall match is denied. The effect of the regexp is therefore to
match one or more <span class="RktInBG"><span class="hspace"></span><span class="RktIn">a</span><span class="hspace"></span></span>’s followed by something that is
definitely non-<span class="RktInBG"><span class="hspace"></span><span class="RktIn">a</span><span class="hspace"></span></span>.</p><div class="navsetbottom"><span class="navleft"><form class="searchform"><input class="searchbox" style="color: #888;" type="text" value="...search manuals..." title="Enter a search string to search the manuals" onkeypress="return DoSearchKey(event, this, "6.1", "../");" onfocus="this.style.color="black"; this.style.textAlign="left"; if (this.value == "...search manuals...") this.value="";" onblur="if (this.value.match(/^ *$/)) { this.style.color="#888"; this.style.textAlign="center"; this.value="...search manuals..."; }"/></form> <a href="../index.html" title="up to the documentation top" data-pltdoc="x" onclick="return GotoPLTRoot("6.1");">top</a></span><span class="navright"> <a href="regexp-alternation.html" title="backward to "9.7 Alternation"" data-pltdoc="x">← prev</a> <a href="regexp.html" title="up to "9 Regular Expressions"" data-pltdoc="x">up</a> <a href="Looking_Ahead_and_Behind.html" title="forward to "9.9 Looking Ahead and Behind"" data-pltdoc="x">next →</a></span> </div></div></div><div id="contextindicator"> </div></body></html>
|