(lastlist字段在运行时使用，我们会在下一节介绍)
依照Thompson的论文，接下去需要将中缀的正则表达式转化为后缀的正则表达式，再从后缀的正则表达式转化为NFA。在其后缀表达式中，新增加一个操作符dot(.)，用来表示连接。函数re2post将一个中缀表达式a(bb)+a转化为等价的后缀表达式abb.+.a.。（在这里，需要区分现实中正则表达式的操作符dot(.)。在现实中，我们会使用dot(.)来表示某个字符，但是在这里我们用来表示连接。在实际工作中，我们也许直接使用中缀表达式来转为NFA，但是，这种后缀表达式的版本也十分便捷，并且也是最符合Thompson的论文的。）
当程序扫描后缀表达式时，它会维护一个栈，栈中会存储NFA片段。普通的字符会产生一个新的NFA片段，然后入栈。遇到操作符则会将栈中的片段pop出，然后组合成一个新的片段再入栈。例如，在处理abb之后，栈中的内容是a,b,b的片段，遇到了dot(.)之后，就会弹出两个b片段，然后组合成一个bb片段重新压入栈中。NFA片段的结构如下： struct Frag { State *start; Ptrlist *out; }; 其中start指针指向片段的开始状态，out指针指向一个指针链表，指针链表中指针分别指向其他的State*指针。当然指针链表中的指针现在还没有指向具体的内容，我们称其为悬挂的指针，这些指针形象地表示了NFA片段中的空箭头。 一些辅助函数如下： Ptrlist *list1(State **outp); Ptrlist *append(Ptrlist *l1, Ptrlist *l2); void patch(Ptrlist *l, State *s); list1函数创建一个新只包含outp指针的指针链表。append函数将两个链表连接起来。patch函数为上面提到的悬挂的指针赋值，让l中悬挂的指针指向状态s：它会设置l链表中所有的指针指向s。 有了这些工具，我们的程序只是通过一个简单的循环体来依次处理每个后缀表达式中的字符。最终，栈里只剩下最后一个片段，将这个片段与matchstate进行patch，说明最终的状态为终结状态，即完成了转化。 State* post2nfa(char *postfix) { char *p; Frag stack[1000], *stackp, e1, e2, e; State *s; #define push(s) *stackp++ = s #define pop() *--stackp stackp = stack; for(p=postfix; *p; p++){ switch(*p){ /* compilation cases, described below */ } } e = pop(); patch(e.out, &matchstate); return e.start; } 一些片段情况如下：
单个字符：
default: s = state(*p, NULL, NULL); push(frag(s, list1(&s->out)); break;连接：
case '.': e2 = pop(); e1 = pop(); patch(e1.out, e2.start); push(frag(e1.start, e2.out)); break;合并：
case '|': e2 = pop(); e1 = pop(); s = state(Split, e1.start, e2.start); push(frag(s, append(e1.out, e2.out))); break;?：
case '?': e = pop(); s = state(Split, e.start, NULL); push(frag(s, append(e.out, list1(&s->out1)))); break;*：
case '*': e = pop(); s = state(Split, e.start, NULL); patch(e.out, s); push(frag(s, list1(&s->out1))); break;+：
case '+': e = pop(); s = state(Split, e.start, NULL); patch(e.out, s); push(frag(e.start, list1(&s->out1))); break;