python - 正規表現を NFA に変換するにはどうすればよいですか?

Question

正規表現を対応する NFA に変換するために Python で使用できるモジュールはありますか、またはコードを最初から作成する必要がありますか (正規表現をインフィックスからポストフィックスに変換し、トンプソンのアルゴリズムを実装して対応する 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ます。

トンプソンのアルゴリズムに完全に基づいています。