如何將正則表達式轉換爲NFA？

Question

Python中是否有任何模塊可用於將正則表達式轉換爲對應的NFA， 還是必須從頭開始構建代碼（將正則表達式從中綴轉換爲後綴，然後實現Thompson's Algorithm以獲取相應的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。

它完全基於Thompson's Algorithm。