from?graphviz?import?Digraph


stack?=?[]??#?儲存nfa的棧
flag?=?[]??#?判斷圖是否遍歷完全
symbol?=?（‘|‘?‘·‘?‘*‘?‘（‘?‘）‘）??#?符號元組
temp?=?[]??#?求閉包時判斷是否遍歷重復結點
_name?=?0??#?求當前結點的數字編號


class?State（object）:??#?nfa的起始和終止狀態
????“““docstring?for?State“““
????def?__init__（self?start?end）:
????????self.start?=?start
????????self.end?=?end


class?nfa（）:??#?nfa的每個狀態信息
????“““docstring?for?retonfa“““
????def?__init__（self）:
????????self.name?=?-1
????????self.next?=?[]
????????self.val?=?[]


def?Clear（）:??#?清空flag標志列表
????flag.clear（）


def?initnfa（val）:??#?初始化一個nfa
????global?_name
????start?=?nfa（）
????start.name?=?_name
????_name?=?_name?+?1
????end?=?nfa（）
????end.name?=?_name
????_name?=?_name?+?1
????start.next.append（end）
????start.val.append（val）
????stack.append（State（start?end））
????#?for?i?in?range（len（start.next））:
????#?????print（start.name?start.val[i]?start.next[i].name）
????#?print（start.name?end.name）


def?stnfa（op）:??#?構造nfa
????global?_name
????if?op?==?‘|‘:
????????start?=?nfa（）
????????start.name?=?_name
????????_name?=?_name?+?1
????????end?=?nfa（）
????????end.name?=?_name
????????_name?=?_name?+?1
????????start.next.append（stack[-2].start）
????????start.val.append（“null“）
????????start.next.append（stack[-1].start）
????????start.val.append（“null“）
????????stack[-2].end.next.append（end）
????????stack[-2].end.val.append（“null“）
????????stack[-1].end.next.append（end）
????????stack[-1].end.val.append（“null“）
????????stack.pop（）
????????stack.pop（）
????????stack.append（State（start?end））
????????#?printnfa（start）
????????#?print（“\n“）
????????flag.clear（）
????????#?for?i?in?range（len（start.next））:
????????#?????print（start.name?start.val[i]?start.next[i].name）
????elif?op?==?‘*‘:
????????start?=?nfa（）
????????start.name?=?_name
????????_name?=?_name?+?1
????????end?=?nfa（）
????????end.name?=?_name
????????_name?=?_name?+?1
????????start.next.append（stack[-1].start）
????????start.val.append（“null“）
????????stack[-1].end.next.append（stack[-1].start）
????????stack[-1].end.val.append（“null“）
????????stack[-1].end.next.append（end）
????????stack[-1].end.val.append（“null“）
????????start.next.append（end）
????????start.val.append（“null“）
????????stack.pop（）
????????stack.append（State（start?end））
????????#?printnfa（start）
????????#?print（“\n“）
????????flag.clear（）
????????#?for?i?in?range（len（start.next））:
????????#?????print（start.name?start.val[i]?start.next[i].name）
????elif?op?==?‘·‘:
????????start?=?nfa（）
????????start.name?=?_name
????????_name?=?_name?+?1
????????end?=?nfa（）
????????end.name?=?_name
????????_name?=?_name?+?1
????????start.next.append（stack[-2].start）
????????start.val.append（“null“）
????????stack[-2].end.next.append（stack[-1].start）
????????stack[-2].end.val.append（“null“）
????????stack[-1].end.next.append（end）
????????stack[-1].end.val.append（“null“）
????????stack.pop（）
????????stack.pop（）
????????stack.append（State（

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????12119??2018-10-27?11:04??re-dfa.py
?????文件?????????171??2018-10-27?11:48??readme.txt
?????文件???????15568??2018-10-27?11:44??retodfa.py