Các dẫn xuất của biểu thức chính quy được giải thích bằng cách sử dụng Pac-Man
Ăn anh đào đỏ cho bạn khả năng ăn ma xanh. Ý tưởng rằng các công cụ phái sinh có thể được sử dụng để tạo ra một thuật toán đối sánh biểu thức chính quy gần như là vô lý. Hãy để tôi giải thích cách thuật toán này hoạt động và cách nó liên quan đến Pac-Man.
Năm 1964, Brzozowski xuất bản bài báo đầu tiên về Đạo hàm của biểu thức chính quy . Đây là một trong những thuật toán yêu thích của tôi. Sử dụng các dẫn xuất của biểu thức chính quy, chúng ta có thể thực hiện một thuật toán để khớp biểu thức chính quy. Thuật toán này rất:
- giản dị
- chức năng
- dễ dàng mở rộng với các toán tử của riêng bạn
Trong bài viết này, tôi sẽ chỉ cho bạn cách chúng ta có thể khớp một chuỗi với một biểu thức chính quy chỉ bằng cách sử dụng hai hàm thuần túy và một số phép loại suy Pac-Man. Nếu thích, bạn có thể xem video sau thay vì đọc bài viết vì nó đề cập đến cùng một nội dung:
Tóm tắt các biểu thức chính quy
Trước tiên, hãy xem xét nhanh các biểu thức chính quy để đảm bảo rằng chúng ta đang ở trên cùng một trang. Biểu thức a(a|b)*
khớp với một chuỗi bắt đầu bằng một a
, theo sau là bất kỳ số a
's và b
's nào.
- Chuỗi
ab
sẽ khớpa(a|b)*
. Chúng tôi sẽ chỉ ra điều này với một con ma màu xanh ăn được. - Chuỗi
aabbba
cũng khớpa(a|b)*
vì nó bắt đầu bằng mộta
và theo sau là một sốa
's vàb
's. - Tiếp theo, chuỗi
ac
không khớpa(a|b)*
, vì biểu thức chính quy không khớp với bất kỳc
's nào và biểu thức chính quy của chúng tôi không thực hiện bất kỳ khớp chuỗi con nào. Chúng tôi sẽ chỉ ra điều này bằng cách sử dụng một con ma màu đỏ đang đuổi theo Pac-Man. - Cuối cùng, chuỗi
ba
cũng không khớpa(a|b)*
vì nó không bắt đầu bằng phần mở rộnga
.
Tổng quan về thuật toán
Trước khi đi sâu vào chi tiết, chúng ta hãy tìm hiểu tổng quan về cách thức hoạt động của thuật toán này. Tôi đã nghĩ ra một trò chơi Pac-Man kỳ lạ, trong đó bạn chỉ có thể ăn thịt những con ma nếu bạn ăn trái cây theo trình tự khớp với biểu thức chính quy. Pac-Man của chúng tôi đại diện cho regex aba*
. Nó có chuỗi trái cây sau đây để ăn: một quả táo, sau đó là một quả chuối, rồi một quả táo: aba
.
- Khi chúng tôi bắt đầu, con ma đang đuổi theo chúng tôi và biểu thức chính quy mà chúng tôi còn lại để khớp là
aba*
. - Chúng ta ăn quả táo đầu tiên và biểu thức chính quy mà chúng ta còn lại để so khớp là
ba*
. Con ma vẫn đang đuổi theo chúng tôi kể từ khi trái cây mà chúng tôi đã ăn cho đến nay, quả táo, không khớp với biểu thức chính quy. - Tiếp theo, chúng tôi ăn chuối. Biểu thức chính quy mà chúng ta còn lại để khớp là
a*
. Bây giờ con ma bắt đầu bỏ chạy vì về mặt kỹ thuật, nóab
đã khớp vớiaba*
. - Chúng ta có thể thử ăn con ma hoặc ăn một quả táo khác, trong trường hợp đó, biểu thức chính quy mà chúng ta còn lại để so khớp vẫn là
a*
. Con ma vẫn đang bỏ chạy vìaba
nó cũng khớp với biểu thức chính quyaba*
.
Có thêm một chức năng tại nơi làm việc ở đây. Hàm kiểm tra xem con ma đang đuổi theo Pac-Man hay liệu Pac-Man đã khớp với biểu thức chính quy và đang đuổi theo con ma. Chức năng này được gọi là chức năng nullable; nó kiểm tra xem biểu thức chính quy còn lại có khớp với chuỗi rỗng hay không. Nó có thể làm điều đó bởi vì nếu regex còn lại để khớp, khớp với chuỗi trống, thì trái cây mà nó đã ăn phải đã đủ để đáp ứng regex.
Thuật toán so khớp phái sinh
Điều đó có nghĩa là chúng ta chỉ cần hai hàm để viết thuật toán so khớp đạo hàm:
- hàm đạo hàm
- chức năng nullable
Một trong Golang cho các lập trình viên cấp bách:
và một cái khác trong Haskell dành cho các lập trình viên chức năng:
Hai hàm này tương đương nhau và chỉ được viết theo các kiểu lập trình khác nhau. Trong mã Haskell, foldl
còn được gọi là fold left hoặc reduce trong các ngôn ngữ khác, thực hiện công việc của vòng lặp for cho bạn. Ngoài ra, trong Haskell, chúng ta không cần dấu phẩy để truyền tham số cho hàm; vì ứng dụng chức năng là hoạt động phổ biến nhất trong ngôn ngữ lập trình chức năng, nên chúng tôi sử dụng khoảng trắng để phân định các tham số.
Bây giờ, hãy tìm hiểu sâu hơn về cách triển khai các hàm vô hiệu và đạo hàm.
Lạc đề câu chuyện nguồn gốc Pac-Man
Nhưng trước khi chúng ta làm điều đó, tôi không biết bạn đã bao giờ thắc mắc về câu chuyện nguồn gốc của Pac-Man chưa. Tôi cho rằng không có thùng chất thải hạt nhân nào mà Pac-Man rơi vào, dẫn đến việc Pac-Man có được sức mạnh ăn thịt ma. Logic đơn giản hơn nhiều.
Pac-Man là một loại trái cây! Khi Pac-Man ăn trái cây khác, Pac-Man đang ăn thịt đồng loại. Vì vậy, nếu bạn từng bị ma đuổi, bạn phải ăn một ít thịt người, và ít nhất là tạm thời, con ma sẽ bắt đầu chạy trốn khỏi bạn. Bây giờ, tôi chưa thử điều này, nhưng logic có vẻ hợp lý.
Điều này giải thích tại sao zombie luôn săn đuổi con người. Như David Attenborough đã từng nói:
“Những thây ma đang đuổi theo chúng ta, chính chúng cũng đang bị truy đuổi bởi những bóng ma mà chúng ta không thể nhìn thấy. Sau khi thây ma ăn một ít thịt người của chúng ta, bạn sẽ thấy chúng có hành vi kỳ lạ là nhai không khí, đây là thây ma đang ăn thịt con ma đã đuổi theo nó trước đó.”
toán tử cơ bản
Việc triển khai các hàm nullable và hàm phái sinh trước tiên yêu cầu chúng ta xác định các toán tử cơ bản có sẵn trong các biểu thức chính quy của chúng ta.
Chúng ta có thể nghĩ về một biểu thức chính quy như mô tả một tập hợp các chuỗi.
- Điều này có nghĩa là tập rỗng đại diện cho một toán tử không khớp với chuỗi nào.
- Chuỗi trống đại diện cho một tập hợp đơn của một chuỗi duy nhất chỉ khớp với chuỗi trống.
- Ký tự này cũng đại diện cho một tập hợp đơn chỉ khớp với ký tự đơn
a
. - Sau đó, chúng ta có thể kết hợp các biểu thức chính quy cơ sở này bằng cách sử dụng các toán tử như:
or
,concatenation
andKleene star
, wherer
vàs
đại diện cho hai biểu thức biểu thức chính quy mà chúng ta đang kết hợp.
Chức năng Nullable
Chúng ta có thể bắt đầu với chức năng nullable. Hãy xem xét một số ví dụ và tìm ra biểu thức chính quy nào khớp với chuỗi trống để hiểu rõ hơn về cách thực hiện chức năng này.
a*
khớp với chuỗi trống vì 0 hoặc nhiều hơn bao gồm 0.(a*|b)
khớp với chuỗi rỗng vì phía bên trái của hoặc khớp với chuỗi rỗng.ab
không khớp với chuỗi rỗng, vì nó chỉ khớp với chuỗiab
ab*
cũng không khớp với chuỗi rỗng, vìab*
yêu cầu một chuỗi bắt đầu bằng mộta
(a|b)
không khớp với chuỗi rỗng, vì cả bên trái và bên phải của chuỗi đềuor
không khớp với chuỗi rỗng.
Đây là việc thực hiện chức năng nullable. Phía bên trái đại diện cho các giá trị được truyền vào hàm và phía bên phải đại diện cho việc triển khai hàm trong trường hợp đó. Bóng ma màu đỏ đại diện cho sai và bóng ma màu xanh đại diện cho sự thật:
- Tập hợp trống không khớp với chuỗi rỗng vì nó không khớp với bất kỳ chuỗi nào.
- Chuỗi rỗng khớp với chuỗi rỗng vì nó chỉ khớp với chuỗi rỗng.
- Ký tự
a
không khớp với chuỗi trống vì nó chỉ khớp với ký tựa
. - Nếu chúng ta có logic
or
, chúng ta phải kiểm tra cả hai bên. Nếu một trong hai khớp với chuỗi rỗng, thì logicor
khớp với chuỗi rỗng. - Để
concatenation
hai biểu thức chính quy khớp với chuỗi trống, cả hai phải khớp với chuỗi trống. - Và cuối cùng, nếu chúng ta có
zero or more
một cái gì đó, thì cái đó bao gồm số 0, có nghĩa là nó luôn khớp với chuỗi rỗng.
- Toán tử hàng đầu của chúng tôi là
or
điều này có nghĩa là chúng tôi phải kiểm tra tính vô hiệu của các bên trái và bên phải:b
vàa*
. - Chúng tôi kiểm tra và thấy rằng ký tự
b
ở phía bên trái không phải là nullable:false
. - Sau đó, chúng tôi kiểm tra và thấy rằng
a*
phía bên phải là nullable:true
. - Bây giờ chúng tôi đã trở lại
false
vàtrue
chúng tôi có thểor
giúp họ có đượctrue
.
Nullable bài tập
Hãy thử xem qua quá trình triển khai và kiểm tra xem các biểu thức chính quy sau có thể vô hiệu hóa không. Bạn có thể nhấp vào chúng để kiểm tra câu trả lời của mình:
- một
- a*(b*|∅)
- εa
- ∅*
- (∅|b)*(abc|ε)
Trước khi xem cách thực hiện hàm, chúng ta hãy xem các ví dụ về đạo hàm. Ở đây chúng ta sẽ lấy đạo hàm của một vài biểu thức chính quy, tất cả đều liên quan đến ký tự a
:
- Biểu thức chính quy còn lại để khớp sau khi
a*
đã ăn một quảa
táo vẫn làa*
. - Đạo hàm của
ab*
with đối vớia
làb*
, vì chúng ta đã khớp với tiền tốa
. - Đạo hàm của
(a|b)b
đối vớia
làb
. - Đạo hàm của
b|(a*b)
đối vớia
làa*b
. Cái bên tráib
không khớp, vì vậy chúng tôi có thể vứt nó đi và cái bêna
phải đã bị tiêu thụzero or more
a
. - Tiếp theo, chúng ta có
ab*
, cái này hơi phức tạp. Sau khi nó ăn quả táo, biểu thức chính quy còn lại để khớp làb(ab)*
. Vì chúng tôi chỉ khớp vớia
, nên chúng tôi hy vọng sẽ thấy ít nhất một cái nữab
.
- Đạo hàm của tập rỗng luôn là tập rỗng. Không có cách nào để phục hồi vì tập trống không khớp với bất kỳ thứ gì.
- Đạo hàm của chuỗi rỗng liên quan đến bất kỳ ký tự nào là tập rỗng. Nó không mong đợi để phù hợp với một nhân vật. Nó sẽ chỉ khớp với chuỗi trống.
- Đạo hàm của một ký tự đơn với một ký tự tương tự (trong trường hợp này là quả
a
táo) là một chuỗi rỗng vì sau khi nó khớp với chính nó, tất cả những gì còn lại để khớp là chuỗi rỗng. - Đạo hàm của một ký tự đối với một ký tự khác không bằng nhau, trong trường hợp này là
b
anana, là tập rỗng vì chúng ta chưa so khớp ký tự cụ thể. - Đạo hàm của một
or
biểu thức làor
đạo hàm của các đạo hàm. Nó chỉ đơn giản là đẩy vấn đề xuống con của nó. - Đạo hàm của
concat
biểu thức phải xem xét liệu nó có thể bỏ qua biểu thức đầu tiên hay không. Nó chỉ có thể bỏ qua biểu thức đầu tiên nếu biểu thức đầu tiên khớp với chuỗi rỗng và không có giá trị. Vì vậy, điều đầu tiên chúng tôi làm là kiểm tra điều này. Hãy nghĩ về trường hợp nó không thể bỏ qua biểu thức đầu tiên khi biểu thứcr
không thể rỗng. Khi đó đạo hàm là đạo hàm của biểu thức thứ nhấtconcatenated
với biểu thức thứ hais
. Nếu chúng ta có thể bỏ qua biểu thức chính quy đầu tiên, thì chúng ta phải xem xét một phương án thay thế chỉ là đạo hàm của biểu thức thứ hai. Sau đó, chúng tôi có thể cóor
hai lựa chọn thay thế là bỏ quar
và không bỏ quar
và kết quả là trả về kết quả đó. - Cuối cùng, chúng ta có
star
toán tử. Nó khớp với một biểu thức không hoặc nhiều lần. Vì chúng tôi đang được chuyển một ký tự, đây không phải là trường hợp không. Vì vậy, chúng ta phải xem xét cácone or more
trường hợp. Điều này có nghĩa là chúng ta phải lấy đạo hàm của biểu thức bên trongstar
vàconcatenate
nó một lần nữa vớizero or more
biểu thức.
Ví dụ phái sinh 1
Hãy lấy đạo hàm của (ab)*
đối với a
.
(ab)*
là một zero or more
biểu thức, vì vậy chúng tôi tìm đến zero or more
quy tắc. Chúng tôi thấy điều này đòi hỏi phải lấy đạo hàm của biểu thức bên trong star
.
Đây là concatenation
của a
và b
. Vì vậy, chúng tôi kiểm tra xem bên trái có phải là nullable hay không và ký tự a
không phải là nullable. Điều này có nghĩa là chúng ta không thể bỏ qua nó. Chúng ta phải lấy đạo hàm của a
đối với a
. Nhưng đó là chuỗi rỗng, vì vậy nếu chúng ta concatenate
nhập chuỗi rỗng ở bên phải, là b
, chúng ta sẽ nhận được b
.
Bây giờ, chúng tôi quay lại với zero or more
, hãy nhớ rằng chúng tôi đã lấy đạo hàm của ab
đối với a
và nhận lại a b
. Bây giờ chúng ta có thể nối nó với (ab)*
một lần nữa và chúng ta nhận được b(ab)*
.
Ví dụ phái sinh 2
Hãy lấy đạo hàm của (a*ba)
đối với b
.
a*
được nối vớiba
vì vậy chúng ta hãy xem quy tắc nối.- Chúng tôi kiểm tra xem bên trái có phải
a*
là nullable hay không. Điều này có nghĩa là chúng ta có thể bỏ qua nó, điều đó cũng có nghĩa là chúng ta phải tạo mộtor
trong hai đạo hàm. - Phía bên trái kết thúc không khớp, vì
a*
không khớpb
. - May mắn thay, chúng tôi có một giải pháp thay thế là
ba
. Đạo hàm củaba
đối vớib
là vàa
.
Tôi đã bỏ qua một số chi tiết ở đây. Hãy coi đó là một bài tập để kiểm tra công việc của tôi bằng cách tự mình xem qua chức năng.
bài tập đạo hàm
Hãy thử xem qua cách triển khai và kiểm tra xem đạo hàm của các biểu thức chính quy sau đây đối với b
. Bạn có thể nhấp vào chúng để kiểm tra câu trả lời của mình:
- εb
- b*(b|c)
- a*(b|c)
- bεb
- ∅*b
Tôi hy vọng bây giờ bạn đã hiểu tại sao ăn quả anh đào màu đỏ lại cho bạn khả năng ăn những con ma màu xanh lam và cách triển khai trình so khớp biểu thức chính quy bằng thuật toán đạo hàm.
Chúng tôi đã đề cập đến thuật toán hoạt động cơ bản ở đây, nhưng có nhiều cách để làm cho thuật toán này thậm chí còn tốt hơn với những chỉnh sửa rất nhỏ. Chúng tôi đã gian lận và che đậy các quy tắc đơn giản hóa trong bài đăng này, sử dụng chúng mà không giải thích chúng, điều này sẽ trở nên đặc biệt rõ ràng nếu bạn xem qua các bài tập. Chúng tôi cũng chưa thảo luận về cách bạn có thể sử dụng tính năng ghi nhớ để xây dựng một máy tự động hiệu quả một cách uể oải.
Chúng tôi cũng có thể dễ dàng mở rộng thuật toán để bao gồm các toán tử mới như, not
và interleave
thậm chí hỗ trợ Ngữ pháp phi ngữ cảnh. Tôi sẽ thảo luận về một số chủ đề này trong bài viết tiếp theo .
Trong thời gian chờ đợi, tôi rất muốn thấy bạn triển khai thuật toán này bằng ngôn ngữ lập trình mà bạn cảm thấy thoải mái nhất. Xin vui lòng gửi cho tôi một liên kết trong các ý kiến.
Cảm ơn bạn
- Brink van der Merwe vì đã dành thời gian giải thích thuật toán này cho tôi.
- Brzozowski, Janusz A. “Các dẫn xuất của biểu thức chính quy.” Tạp chí ACM (JACM) 11.4 (1964): 481–494.
- Owens, Scott, John Reppy và Aaron Turon. “Các dẫn xuất của biểu thức chính quy đã được kiểm tra lại.” Tạp chí Lập trình hàm 19.2 (2009): 173–190.