Thompson Regular Expression Search Algorithm 3rd Stage
Let's take the example from the paper: $a(b|c)^*d$. This is first translated into RPN: "$abc|*.d.$". This is compiled into (essentially) an NFA by using a stack. Upon reading a symbol $\sigma$, we push to the stack an NFA for $\sigma$, which we will denote by $N(\sigma)$. Upon reading $*$, we pop an NFA $N(r)$ for the regular expression $r$ from the stack and push $N(r^*)$, an NFA for $r^*$. Upon reading a binary operand $\circ$, we pop two NFAs $N(r_1),N(r_2)$ and push $N(r_1 \circ r_2)$, an NFA for $r_1 \circ r_2$.

Here are the different stages. At each stage, we underline the character being processed, and the resulting stack after processing it, where the top-of-stack is to the right:


$abc|*.d. \qquad $ (empty)
$\underline{a}bc|*.d. \qquad N(a)$
$a\underline{b}c|*.d. \qquad N(a) N(b)$
$ab\underline{c}|*.d. \qquad N(a) N(b) N(c)$
$abc\underline{|}*.d. \qquad N(a) N(b|c)$
$abc|\!\underline{*}.d. \qquad N(a) N((b|c)^*)$
$abc|*\underline{.}d. \qquad N(a(b|c)^*)$
$abc|*.\underline{d}. \qquad N(a(b|c)^*) N(d)$
$abc|*.d\underline{.} \qquad N(a(b|c)^*d)$


Nowadays the regular expression will be parsed into a tree, and the translation process will proceed recursively. If the tree is processed in the correct order (DFS), then this would be completely equivalent to the algorithm described by Thompson.

Either way, having constructed an NFA for the input regular expression, we run it on the input text. This is the part in which we actually search the input text.