Kırmızı kiraz yemek size mavi hayaletleri yeme yeteneği verir. Türevlerin düzenli bir ifade eşleştirme algoritması oluşturmak için kullanılabileceği fikri neredeyse saçma. Bu algoritmanın nasıl çalıştığını ve Pac-Man ile nasıl bir ilişkisi olduğunu açıklayayım.

1964'te Brzozowski , Düzenli İfadelerin Türevleri ile ilgili ilk makaleyi yayınladı . Bu, açık ara en sevdiğim algoritmalardan biri. Düzenli ifadelerin türevlerini kullanarak, düzenli ifade eşleştirmesi yapmak için bir algoritma uygulayabiliriz. Bu algoritma çok:

• basit
• fonksiyonel
• kendi operatörlerinizle kolayca genişletilebilir

Bu yazıda size sadece iki saf fonksiyon ve bazı Pac-Man benzetmeleri kullanarak bir dizgeyi bir normal ifadeyle nasıl eşleştirebileceğimizi göstereceğim. Dilerseniz aynı materyali içerdiği için yazıyı okumak yerine aşağıdaki videoyu izleyebilirsiniz:

Normal İfadelerin Özeti

Öncelikle, aynı sayfada olduğumuzdan emin olmak için normal ifadeleri hızlıca gözden geçirelim. İfade , herhangi bir sayıda ' ve ' a(a|b)*ile devam eden bir ile başlayan bir dizeyle eşleşir .aab

• Dizi abeşleşecek a(a|b)*. Bunu yenilebilir mavi bir hayaletle göstereceğiz.
• Dize aynı zamanda bir ile başladığından ve birkaç ' ve ' tarafından takip edildiğinden aabbbade eşleşir .a(a|b)*aab
• Daha sonra , normal ifade herhangi bir ' ile eşleşmediğinden ve normal ifademiz herhangi bir alt dize eşleştirmesi yapmadığından, dize aceşleşmez . Bunu Pac-Man'i kovalayan kırmızı bir hayalet kullanarak göstereceğiz.a(a|b)*c
• Son olarak, bir ile başlamadığı için dize bade eşleşmez .a(a|b)*a

Algoritmaya Genel Bakış

Ayrıntılara girmeden önce, bu algoritmanın nasıl çalıştığına bir göz atalım. Sadece meyveyi normal ifadeyle eşleşen bir sırayla yerseniz hayaletleri yiyebileceğiniz tuhaf bir Pac-Man oyunu tasarladım. Pac-Man'imiz normal ifadeyi temsil eder aba*. Yemek için şu meyve dizisine sahiptir: bir elma, sonra bir muz ve sonra bir elma: aba.

1. Başladığımızda, hayalet bizi kovalıyor ve eşleştirmek için kalan normal ifademiz aba*.
2. İlk elmayı yiyoruz ve artık eşleştirmemiz gereken normal ifade ba*. Şimdiye kadar yediğimiz meyve olan elma normal ifadeyle eşleşmediği için hayalet hala bizi kovalıyor.
3. Sonra muzu yiyoruz. Daha sonra eşleştirmek için bıraktığımız normal ifade a*. Şimdi hayalet kaçmaya başlıyor çünkü teknik olarak abzaten eşleşiyor aba*.
4. Hayaleti yemeyi veya başka bir elma yemeyi deneyebiliriz, bu durumda eşleştirmek için kalan normal ifademiz hala olur a*. abaNormal ifadeyle de eşleştiği için hayalet hala kaçıyor aba*.

Burada iş başında olan bir işlev daha var. İşlev, hayaletin Pac-Man'i takip edip etmediğini veya Pac-Man'in zaten normal ifadeyle eşleşip eşleşmediğini ve hayaleti takip edip etmediğini kontrol eder. Bu işleve null yapılabilir işlev denir; Eşleşecek şekilde bırakılan normal ifadenin boş dizeyle eşleşip eşleşmediğini kontrol eder. Bunu yapabilir, çünkü eşleşmesi için bırakılan normal ifade boş dizeyle eşleşirse, yediği meyve zaten normal ifadeyi tatmin etmeye yetmiş olmalıdır.

Türev Eşleştirme Algoritması

Bu, türev eşleme algoritmasını yazmak için yalnızca iki işleve ihtiyacımız olduğu anlamına gelir:

1. türev fonksiyonu
2. null yapılabilir işlev

Zorunlu programcılar için Golang'da bir tane:

ve diğeri işlevsel programcılar için Haskell'de:

Bu iki işlev eşdeğerdir ve farklı programlama stillerinde yazılmıştır. Diğer dillerde sola katlama veya küçültme olarak da adlandırılan Haskell kodunda, foldlfor döngüsünün işini sizin yerinize yapar. Ayrıca, Haskell'de, parametreleri işlevlere iletmek için virgüllere ihtiyacımız yoktur; Fonksiyon uygulaması, fonksiyonel bir programlama dilinde en yaygın işlem olduğundan, parametreleri sınırlandırmak için boşluk kullanırız.

Şimdi, null yapılabilir ve türev işlevlerinin nasıl uygulanacağını daha derinlemesine inceleyelim.

Pac-Man Kökeni Hikaye Arasöz

Ama bunu yapmadan önce, Pac-Man'in köken hikayesini hiç merak ettiniz mi bilmiyorum. Pac-Man'in içine düştüğü ve Pac-Man'in hayalet yeme gücü kazanmasıyla sonuçlanan bir nükleer atık varili olmadığını iddia ediyorum. Mantık çok daha basit.

Pac-Man bir meyvedir! Pac-Man diğer meyveleri yediğinde, Pac-Man bir yamyam oluyor. Yani bir hayalet tarafından kovalanırsanız, biraz insan eti yemelisiniz ve hayalet en azından geçici olarak sizden kaçmaya başlamalıdır. Şimdi, bunu kendim denemedim ama mantık sağlam görünüyor.

Bu, zombilerin neden her zaman insanları kovaladığını açıklıyor. David Attenborough'un bir zamanlar dediği gibi:

“Bizi kovalayan zombiler, göremediğimiz hayaletler tarafından kovalanıyorlar. Zombiler insan etimizin bir kısmını yedikten sonra, onların havayı çiğnemek gibi garip bir davranış sergilediklerini göreceksiniz, bu zombi daha önce onu kovalayan hayaleti yiyor.”

Temel Operatörler

Null yapılabilir ve türev işlevlerinin uygulanması, önce düzenli ifadelerimizde bulunan temel işleçleri tanımlamamızı gerektirir.

Normal bir ifadeyi bir dizi diziyi açıklamak gibi düşünebiliriz.

• Bu, boş kümenin hiçbir dizeyle eşleşmeyen bir işleci temsil ettiği anlamına gelir.
• Boş dize, yalnızca boş dizeyle eşleşen tek bir dizenin tekil kümesini temsil eder.
• Karakter ayrıca yalnızca tek karakterle eşleşen tekil bir kümeyi temsil eder a.
• orDaha sonra , concatenationve gibi işleçleri kullanarak bu temel düzenli ifadeleri birleştirebiliriz Kleene star; burada rve sbirleştirdiğimiz iki normal ifade ifadesini temsil eder.

Null yapılabilir işlev

Nullable işleviyle başlayabiliriz. Bazı örneklere bakalım ve bu işlevin nasıl uygulandığına dair fikir edinmek için bu normal ifadelerden hangisinin boş dizeyle eşleştiğini bulalım.

• a*sıfır veya daha fazlası sıfır içerdiğinden boş dizeyle eşleşir.
• (a*|b)veya öğesinin sol tarafı boş dizeyle eşleştiği için boş dizeyle eşleşir.
• abyalnızca dizeyle eşleştiği için boş dizeyle eşleşmezab
• ab*ab*ile başlayan bir dizi gerektirdiğinden boş dizeyle de eşleşmez.a
• (a|b)boş dizeyle eşleşmez, çünkü __ öğesinin ne solu ne de sağ tarafı orboş dizeyle eşleşmez.

İşte null yapılabilir işlevin uygulanması. Sol taraf, işleve iletilen değerleri temsil eder ve sağ taraf, bu durumda işlevin uygulanmasını temsil eder. Kırmızı hayaletler yanlışı, mavi hayaletler ise doğruyu temsil eder:

• Boş küme, herhangi bir dizi ile eşleşmediği için boş dizi ile eşleşmez.
• Boş dize, yalnızca boş dizeyle eşleştiği için boş dizeyle eşleşir.
• Karakter a, yalnızca karakterle eşleştiği için boş dizeyle eşleşmez a.
• Eğer bir mantığımız varsa or, her iki tarafı da kontrol etmeliyiz. Bunlardan herhangi biri boş dizeyle eşleşirse, mantıksal or, boş dizeyle eşleşir.
• Of concatenationiki normal ifadenin boş dizeyle eşleşmesi için her ikisinin de boş dizeyle eşleşmesi gerekir.
• Ve son olarak, eğer elimizde zero or morebir şey varsa, o zaman bu sıfırı içerir, yani her zaman boş dizgeyle eşleşir.

1. En iyi operatörümüz, orbu, sol ve sağ tarafların sıfırlanabilirliğini kontrol etmemiz gerektiği anlamına gelir: bve a*.
2. bSol taraftaki karakterin nullable olmadığını kontrol edip görüyoruz : false.
3. Sonra kontrol a*edip sağ taraftakinin null yapılabilir olduğunu görüyoruz: true.
4. Şimdi geri döndük falseve onları truealabiliriz .ortrue

Null yapılabilir egzersizler

Uygulamayı gözden geçirmeye çalışın ve aşağıdaki normal ifadelerin geçersiz olup olmadığını kontrol edin. Cevabınızı kontrol etmek için üzerlerine tıklayabilirsiniz:

1. a
2. a*(b*|∅)
3. εa
4. ∅*
5. (∅|b)*(abc|ε)

Fonksiyonun uygulanmasına bakmadan önce türev örneklerine bakalım. Burada, tamamı karaktere göre birkaç normal ifadenin türevini alacağız a:

• Bir pple a*yedikten sonra eşleşmesi için kalan normal ifade still'dir .aa*
• Göreceli türevi ab*, çünkü zaten öneki aeşleştirdik .b*a
• (a|b)bgöre türevi . a_b
• b|(a*b)göre türevi . a_ a*bSol beşleşmedi, bu yüzden onu atabildik ve sağdaki 'ler atarafından tüketildi .zero or more a
• Sonra, elimizde ab*, bu biraz zor. Elmayı yedikten sonra eşleşmesi için kalan normal ifade b(ab)*. Sadece ile eşleştiğimiz için a, en az bir tane daha görmeyi bekliyoruz b.

• Boş kümenin türevi her zaman boş kümedir. Boş küme hiçbir şeyle eşleşmediğinden kurtarmanın bir yolu yoktur.
• Boş dizgenin herhangi bir karaktere ilişkin türevi boş kümedir. Bir karakterle eşleşmeyi beklemiyordu. Yalnızca boş dizeyle eşleşir.
• Tek bir karakterin benzer bir karaktere türevi (bu durumda, apple) boş dizedir, çünkü kendisiyle eşleştikten sonra, eşleşmesi gereken tek şey boş dizedir.
• Bir karakterin eşit olmayan farklı bir karaktere, bu durumda banana'ya göre türevi, belirli karakteri eşleştirmediğimiz için boş kümedir.
• Bir orifadenin ortürevi, türevlerinkidir. Sorunu basitçe çocuklarına indirir.
• İfadenin türevi concat, ilk ifadeyi atlayıp atlayamayacağını dikkate almalıdır. Yalnızca ilk ifade boş dizeyle eşleşirse ve null yapılabilirse ilk ifadeyi atlayabilir. Yani yaptığımız ilk şey bunu kontrol etmek. rİfade null yapılamazken ilk ifadeyi atlayamadığı durumu düşünelim . O zaman türev, birinci ifadenin concatenatedikinci ifadeyle türevidir s. İlk regex'i atlayabilirsek, sadece ikinci ifadenin türevi olan bir alternatif düşünmeliyiz. O zaman , atlama ve atlamama şeklindeki oriki alternatifi kullanabilir ve sonuç olarak bunu geri verebiliriz.rr
• Son olarak, staroperatörümüz var. Bir ifadeyle sıfır veya daha fazla kez eşleşir. Bir karakter geçirdiğimiz için, bu sıfır durum değil. Bu nedenle, durumu dikkate one or morealmalıyız. Bu, ifadenin içindeki türevi almamız gerektiği anlamına gelir ve ifade starile concatenatetekrar zero or moreifade eder.

Türev örneği 1

(ab)*'nin ' ye göre türevini alalım a.

(ab)*bir ifadedir, bu nedenle kurala zero or morebakarız . zero or moreBunun, içindeki ifadenin türevini almayı gerektirdiğini görüyoruz star.

Bu ve . concatenation_ Böylece sol tarafın null olup olmadığını ve karakterin null olup olmadığını kontrol ederiz . Bu, onu atlayamayacağımız anlamına gelir. 'ye göre türevi almalıyız . Ama bu boş dizedir, bu yüzden sağ taraftaki boş dizeyi alırsak, ki bu , elde ederiz .abaaaconcatenatebb

Şimdi, ’ye geri dönüyoruz , hatırlayalım, ’nin göre zero or moretürevini aldık ve a’yı bulduk . Şimdi bunu tekrar ile birleştirebiliriz ve elde ederiz .abab(ab)*b(ab)*

Türev örneği 2

(a*ba)'nin ' ye göre türevini alalım b.

• a*ile birleştirilir, babu nedenle birleştirme kuralına bir göz atalım.
• Sol tarafın a*null olup olmadığını kontrol ediyoruz, ki öyle. Bu, onu atlayabileceğimiz anlamına gelir, bu da oriki türevi oluşturmamız gerektiği anlamına gelir.
• Eşleşmediği için sol taraf a*eşleşmez b.
• Neyse ki bir alternatifimiz var ba. ve ba'ye göre türevi .ba

Burada bazı detayları atlamışım. İşlevi kendiniz gözden geçirerek çalışmamı kontrol etmeyi bir alıştırma olarak düşünün.

Türev alıştırmaları

Uygulamayı gözden geçirmeye çalışın ve aşağıdaki düzenli ifadelerin türevlerinin b. Cevabınızı kontrol etmek için üzerlerine tıklayabilirsiniz:

1. εb
2. b*(b|c)
3. a*(b|c)
4. bεb
5. ∅*b

Umarım artık kırmızı kiraz yemenin size neden mavi hayaletleri yeme yeteneği verdiğini ve türev algoritmasını kullanarak bir düzenli ifade eşleyiciyi nasıl uygulayacağınızı anlamışsınızdır.

Burada temel çalışma algoritmasını ele aldık, ancak bu algoritmayı çok küçük ayarlarla daha da iyi hale getirmenin birçok yolu var. Bu gönderide, basitleştirme kurallarını açıklamadan kullanarak hile yaptık ve geçiştirdik; bu, alıştırmaları incelerseniz özellikle bariz hale gelecektir. Tembel bir şekilde verimli bir otomat oluşturmak için not almayı nasıl kullanabileceğinizi de tartışmadık.

notAlgoritmayı , gibi yeni operatörleri içerecek şekilde kolayca genişletebilir interleaveve hatta Bağlamdan Bağımsız Dil Bilgilerini destekleyebiliriz. Bir sonraki makalede bu konuların bazılarından bahsedeceğim .

Bu arada, bu algoritmayı en rahat olduğunuz bir programlama dilinde uygulamanızı görmek isterim. Lütfen yorumlarda bana bir bağlantı gönderin.

Teşekkürler

• Brink van der Merwe , bana bu algoritmayı açıklamak için zaman ayırdığı için.

• Brzozowski, Janusz A. "Düzenli ifadelerin türevleri." ACM Dergisi (JACM) 11.4 (1964): 481–494.
• Owens, Scott, John Reppy ve Aaron Turon. "Düzenli ifade türevleri yeniden incelendi." Journal of Functional Programming 19.2 (2009): 173–190.