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

Question

Python中是否有可用于将正则表达式转换为相应NFA的模块,或者我是否必须从头开始构建代码(通过将正则表达式从中缀转换为后缀,然后实现Thompson的算法以获得相应的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。

它完全基于汤普森算法。