iT邦幫忙

2022 iThome 鐵人賽

DAY 22
0
自我挑戰組

寫程式帶給我的無形快樂系列 第 22

吃下 Regular Expressions 翻譯年糕 (Regex Engine)

  • 分享至 

  • xImage
  •  

Regex的執行,主要是靠 Regex Engine 在運作

當我們使用 exec 或是 testRegular expression engine 會開始搜尋我們給的文本

從文本的第一個字元前的位置最後一個字元後的位置,一個一個去和 Expression 做比對
直到 找到匹配的字元或是 已經搜尋到最後一個字元 才會停止


狀態機

狀態機 (State Machine) 是一種描述行為的模型,由有限的狀態組成,也可以被稱作為 有限狀態機 (Finite-state-machine)

狀態機 會讀取一組輸入值,並依據這些輸入值更改成不同的狀態

狀態圖中:
圓圈 代表可能的狀態
箭號 表示狀態之間的轉換

從數學的角度看, Regex 就是一個狀態機概念

『 狀態機: 表示有限個狀態以及在這些狀態之間的轉移和動作等行為的數學模型 』

『 所有的 Regex 都可以用狀態機來表示!』

重點: 狀態轉移 移動到下一個狀態


狀態機有兩種類型:

  • 確定有限狀態機 (deterministic finite state machine)
  • 非確定有限狀態 (non-deterministic finite state machine)

確定有限狀態機

只允許一種可能的轉換

deterministic finite state machine
給定 X --> 狀態改為 2
給定 Y --> 狀態改為 3

非確定有限狀態機

一個輸入可以有多種狀態

non-deterministic finite state machine
給定 X --> 狀態可以不變或是改為 2


『 Regex 會判斷接收到的事件是否滿足,如果滿足則移動到下一個狀態,直到整個狀態機滿足為止。 』


運作

透過視覺化的圖像可以更理解 Regex 的運作

Regexper

輸入 JavaScript 使用的 Regex (只支援 JS 寫法!)

看看幾個量詞相關的範例:

/\d?/ 數字可有可無
demo-1

/\d+/ 數字出現至少一次以上
demo-2

/\d{1,2}/ 數字出現一次~二次
demo-2

再看看之前的時間格式(HH:mm HH-mm)的例子 : /\d\d[:-]\d\d/
time format


Debuggex

支援 JavaScript Python PCRE ,更能理解 位置是怎麼移動進行比對的概念

範例: Result 的區塊可以使用游標左右移動,搭配狀態圖一起看
demo-debuggex
Start 為搜尋文本的起始位置

  1. Start 位置為基準點,將右側字元一一和 Pattern 做比對
  2. Position 移到最後一個字元之後,Start 再往右一格
  3. 再從這個新 Start 為基準點,將右側字元一一和 Pattern 做比對

反覆這個流程,直到 Start 也移到最後一個位置

遇到難以閱讀的 Regex,都很推薦用狀態機圖看看的它的運作!


快樂泉源

終於,翻譯年糕最後一口

忘記是在哪裏看到的一句話

『 當資料量龐大且形式規律時,Regular Expressions 特別顯得有效益 』
(每當卡關或是糾結時,就會想起這段話)

對我來說,這也是寫程式的精髓

我們都是一群整理資料,尋找其規則的人
規則找出,就可以對大筆資料進行套用

也反映出工程師特性
不會重複性的做同一件事,能一鍵簡化就簡化,甚至也不用一鍵,定時讓它執行更好 (^_^)


參考資源

如何有邏輯的釐清事物的狀態?學習 FSM 有限狀態機
文本分析基礎-正規表達式(RegExp)
Intro to Regular Expressions (RegEx) via State Diagrams
什麼是「狀態機」?
Regular Expressions
正規表達式教學,使用狀態機輔助說明
Regular Expression (JavaScript) 學習筆記 (1) - 原理篇 (上)


上一篇
吃下 Regular Expressions 翻譯年糕 (環顧四周)
下一篇
[雜談] 斜槓斜起來,當自己的設計師 (上)
系列文
寫程式帶給我的無形快樂30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言