# Changeset 3411 for docs

Ignore:
Timestamp:
Jul 26, 2013, 9:28:33 AM (6 years ago)
Message:

Added Match Star description

Location:
docs/Working/re
Files:
4 edited

### Legend:

Unmodified
 r3156 This is BibTeX, Version 0.99c (TeX Live 2009/Debian) The top-level auxiliary file: re-main.aux This is BibTeX, Version 0.99dThe top-level auxiliary file: re-main.aux The style file: acm.bst Database file #1: reference.bib Warning--empty institution in abou-assaleh2004 Warning--empty journal in kleene1951 You've used 15 entries, 2253 wiz_defined-function locations, 617 strings with 6165 characters, and the built_in function-call counts, 4876 in all, are: = -- 462 > -- 215 < -- 0 + -- 92 - -- 74 * -- 347 := -- 786 add.period$-- 44 call.type$ -- 15 change.case$-- 82 chr.to.int$ -- 0 cite$-- 17 duplicate$ -- 204 empty$-- 414 format.name$ -- 74 if$-- 1032 int.to.chr$ -- 0 int.to.str$-- 15 missing$ -- 14 newline$-- 76 num.names$ -- 30 pop$-- 102 preamble$ -- 1 purify$-- 67 quote$ -- 0 skip$-- 130 stack$ -- 0 substring$-- 253 swap$ -- 54 text.length$-- 0 text.prefix$ -- 0 top$-- 0 type$ -- 58 warning$-- 2 while$ -- 49 width$-- 17 write$ -- 150 (There were 2 warnings)
 r3156 %Source: http://en.wikipedia.org/wiki/Backtracking Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions. %Backtracking is a general algorithm for finding all solutions to some computational problem, %that incrementally builds candidates to the solutions. Match Star takes a marker bitstream and a character class bitstream as input.  It returns all positions that can be reached by advancing the marker bitstream zero or more times through the character class bitstream. Figure one illustrates the Match Star method.  The second and third rows are the input bitstreams: the initial marker position bitstream and the character class bitstream derived from the source data. In the first operation ($T_0$), marker positions that cannot be advanced are temporarily removed from consideration by masking off marker positions that aren't character class positions using bitwise logic.  Next, the temporary marker bitstream is added to the character class bitstream.  $T_1$ has 1s in three types of positions.  There will be a 1 immediately following a block of character class positions that spanned one or more marker positions, at any character class positions that weren't affected by the addition (and are not part of the desired output), and at any marker position that wasn't the first in its block of character class positions.  Any character class positions that have a 0 in $T_1$ were affected by the addition and are part of the desired output.  These positions are obtained and the undesired 1 bits are removed by XORing with the character class stream. $T_2$ is now only missing marker positions that were removed in the first step as well as marker positions that were 1s in $T_1$.  The output marker stream is obtained by ORing $T_2$ with the initial marker stream. \begin{figure}[tbh] \begin{center} \begin{tabular}{cr}\\ source data & \verb--142578---125-231-----127--5394---94761205-\\ $M_0$ & \verb.......1......1..1..1...1.............1..1..\\ $D =$\verb:[0-9]: & \verb..111111...111.111.....111..1111...11111111.\\ $T_0 = M_0 \wedge D$ & \verb.......1.........1......1.............1..1..\\ $T_1 = T_0 + D$ & \verb.1.........1111.......1..1..1111..1...1...1.\\ $T_2 = T_1 \oplus D$ & \verb.1111111......1111....111.........1111.111..\\ $M_1 = T_2 \, | \, M_0$ & \verb.1111111......1111..1.111.........11111111.. \end{tabular} \end{center} \caption{Match Star} \label{fig:scan1} \end{figure} \section{Compiler Technology}