動機

超越NFA的regex，酷!!

從NFA開始

.(任一字元): transition |: 分岔到兩個state *: loop 或是 直接跳到下一個state +: ..* {n,}: <pat><pat>..(重複n-1次)<pat>+

\b: word boundry，可以把單字(字母與數字)從其他非單字字元的包圍中抽出來

re.findall(r'\b[0-9]+?\b',"~123 456* 567")

\B: not word boundry，就是不是word boundry的字元

re.findall(r'\B[0-9]+\B',"~123 456* 567")

?: 除了是0或1的外，還有一個用法是不要比對到底(Laziness)，像.*原本會把所有字元都吃掉，但變成.*?後就不會試著全部match，而是只match可以過的部分，其他交給別的pattern

從NFA到PDA

group (ptr): 把比對到的東西放到regex engine的變數(stack)中 (<pat>) named group: group多了名字 (?P<name><pat>) non-capturing group: pattern不放到regex engine的變數(stack)中 (?:<pat>)

atomic group(Once-only Subexp­ression): 會cut的group (?><pat>)

這個需要例子，像是a(?>bc|b)c去比對abbcdabcc 會先match到ab剩下的pattern是c剩下的string是dabcc，這會失敗，所以會retry

但，因為atomic group會cut，他會把已經比對過的string都忘掉，所以接下去是從bcdabcc， 最後match到abcc

back reference: 透過變數使用之前比對到的東西來比對 \n

re.search(r'(hello) \1 \S+', 'This is a hello hello world!')
re.search(r'(\'|\").*\1',"\"This is a \'string\'\"")

從PDA到Turing Machine

lookahead: 先往後(右)看如果match才繼續下去(如果是negtive，就是不match才繼續下去) (?=<pat>) (?!<pat>)

lookbehind: 先往前(左)看如果match才繼續下去(如果是negtive，就是不match才繼續下去) (?<=<pat>) (?<!<pat>)

re.search(r'(?<=cda).*(?=c)','abbcdabcc')
re.search(r'(?=cda).*','abbcdabcc')

Recursion: 再複製一次pattern，再跑一次match，在Turing Machine可以當成把指針移到pattern的開頭 ?n OR ?R

regex.search(r"^(\((?1)*\))(?1)*$", "()()")
regex.search(r"(\w)((?R)|(\w?))\1", "kayak")

還有condition，但暫時搞不懂怎麼用，先放著

Ref

great cheatsheet concepts in advanced regex Recursive Regular Expression