如何将正则表达式转换为NFA？

Question

Python中是否有模块可以将正则表达式转换为相应的NFA，还是必须从头构建代码(通过将regex从infix转换为后缀，然后实现汤普森算法以获得相应的NFA)？

在Python中可以从转换表中获取NFA的状态图吗？

Answer 1

regex=''.join(postfix)

keys=list(set(re.sub('[^A-Za-z0-9]+', '', regex)+'e'))

s=[];stack=[];start=0;end=1

counter=-1;c1=0;c2=0

for i in regex:
    if i in keys:
        counter=counter+1;c1=counter;counter=counter+1;c2=counter;
        s.append({});s.append({})
        stack.append([c1,c2])
        s[c1][i]=c2
    elif i=='*':
        r1,r2=stack.pop()
        counter=counter+1;c1=counter;counter=counter+1;c2=counter;
        s.append({});s.append({})
        stack.append([c1,c2])
        s[r2]['e']=(r1,c2);s[c1]['e']=(r1,c2)
        if start==r1:start=c1 
        if end==r2:end=c2 
    elif i=='.':
        r11,r12=stack.pop()
        r21,r22=stack.pop()
        stack.append([r21,r12])
        s[r22]['e']=r11
        if start==r11:start=r21 
        if end==r22:end=r12 
    else:
        counter=counter+1;c1=counter;counter=counter+1;c2=counter;
        s.append({});s.append({})
        r11,r12=stack.pop()
        r21,r22=stack.pop()
        stack.append([c1,c2])
        s[c1]['e']=(r21,r11); s[r12]['e']=c2; s[r22]['e']=c2
        if start==r11 or start==r21:start=c1 
        if end==r22 or end==r12:end=c2

print keys

print s

这是postfix之后的大部分代码示例。s包含转换表，键包含所有使用的终端，包括e。e用于Epsilon。

它完全基于汤普森算法。