Thompson Regular Expression Search Algorithm 3rd Stage My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows:


Check that the RE is syntactically correct 
Convert RE to reverse polish form 


The paper states "the third stage is at its heart a pushdown stack." I don't get what that means. 

It seamlessly walks us through pushing and popping off the stack to translate the RE $a(b|c)^*d$ with CNODES and NNODES. 

But what is this for? I know that the purpose of the algorithm is to find all substrings in a given text that match the given RE, but I don't see how the third stage achieves this.
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.