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:

1. Check that the RE is syntactically correct
2. 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:

1. $abc|*.d. \qquad$ (empty)
2. $\underline{a}bc|*.d. \qquad N(a)$
3. $a\underline{b}c|*.d. \qquad N(a) N(b)$
4. $ab\underline{c}|*.d. \qquad N(a) N(b) N(c)$
5. $abc\underline{|}*.d. \qquad N(a) N(b|c)$
6. $abc|\!\underline{*}.d. \qquad N(a) N((b|c)^*)$
7. $abc|*\underline{.}d. \qquad N(a(b|c)^*)$
8. $abc|*.\underline{d}. \qquad N(a(b|c)^*) N(d)$
9. $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.

• Thank you for this! I didn't understand that they were pushing/popping NFAs. But where/how in this process is the program finding matching substrings in the larger text? I understand that it uses a push down stack but how does push down stack relate to the goal of the algorithm? – maddie Mar 10 '18 at 5:23
• The pushdown stack is used to construct the NFA. We then run the NFA on the input – this is the part that is used to match substrings. – Yuval Filmus Mar 10 '18 at 5:23