Bir metinde e-posta adresi bulmak, log dosyasından hata kodu çekmek ya da bir form alanının yalnızca rakam kabul etmesini sağlamak için yazdığımız .*, +, ? ve köşeli parantezler ilk bakışta mütevazı araçlardır. Fakat bu semboller, bilgisayar biliminin en zarif fikirlerinden birine açılan kapıdır: Her desen aynı türden değildir; her dili aynı güçte bir makine tanıyamaz. Regex yazarken aslında, çoğu zaman fark etmeden, Chomsky Hiyerarşisi denen matematiksel bir karmaşıklık merdiveninde dolaşırız.
Desen aramak mı, dil tanımlamak mı?
Regex çoğu geliştiricinin zihninde bir “metin bulma aracı”dır. Oysa kuramsal açıdan düzenli ifade, bir dili tanımlar: Kabul edilecek tüm karakter dizilerinin kümesini. Örneğin ab*, önce bir a, ardından sıfır veya daha fazla b içeren dizileri tanımlar: a, ab, abbb gibi. Bu küçük ifade, sonsuz sayıda olası metni birkaç sembolle tarif eder. Gücü tam da buradadır: Sonlu bir tariften sonsuz bir davranış üretmek.
Chomsky Hiyerarşisi dilleri dört ana katmanda sınıflandırır. En altta düzenli diller vardır. Bunlar sonlu otomatlarla tanınabilir: Geçmiş hakkında sınırlı bilgi tutan, belirli durumlar arasında geçiş yapan küçük makineler. Bir e-posta alanında belirli karakterlerin geçip geçmediğini denetlemek veya bir log satırının biçimini sınıflandırmak gibi görevlerde bu model son derece etkilidir. Regex motorlarının hızlı olmasının temel nedeni de çoğu zaman budur: Sorunu sınırlı bellekle çözebilirler.
Parantezler dengelenince oyun değişir
Ancak bazı desenler, yalnızca sonlu sayıda durumla yakalanamaz. Klasik örnek dengeli parantezlerdir: (), (()) ve (()()) geçerli olsun; fakat ())( olmasın. Burada makinenin açılan her parantezi hatırlaması gerekir. Kaç tane açıldıysa, o kadar kapanış beklenir. Bu görev bir sayaçtan da fazlasını, yığın benzeri bir belleği gerektirir. İşte bu noktada bağlamdan bağımsız diller ve yığıtlı otomatlar sahneye çıkar.
Programlama dillerinin sözdizimi bu yüzden yalnızca “klasik regex” ile güvenilir biçimde çözülemez. İç içe fonksiyon çağrıları, bloklar, parantezler ve ifadeler, yapısal ilişki taşır. Bir derleyicinin ayrıştırıcısı sadece karakterleri sırayla görmez; onların hiyerarşik mimarisini kurar. Kod, düz bir metin değildir. İçinde başka yapılar taşıyan, katmanlı bir nesnedir.
Hiyerarşinin daha üstünde bağlama duyarlı diller ve teorik olarak Turing makinelerinin tanıyabildiği genel diller bulunur. Bu katmanlarda kurallar, çevredeki sembollere veya sınırsız hesaplama adımlarına bağlı olabilir. Pratik yazılım mühendisliğinde her problemi bu en güçlü seviyeye taşımak cazip görünse de bu çoğu zaman kötü bir fikirdir. Daha güçlü ifade gücü, daha zor analiz, daha yüksek maliyet ve daha fazla hata olasılığı demektir.
“Regex” sözcüğünün küçük tuzağı
Burada önemli bir ayrım vardır: Günlük hayatta regex dediğimiz araçların bazıları, kuramsal düzenli ifadelerden daha güçlü özellikler sunar. Geri başvurular, örneğin (\w+)\s+\1 ile aynı kelimenin tekrarını aramak, klasik düzenli dillerin sınırını aşabilir. Bazı motorlar özyinelemeli kalıplar veya koşullar da destekler. Yani bir programlama dilindeki “regex”, her zaman matematik dersindeki regex değildir.
Bu güç artışı bedelsiz gelmez. Özellikle geri izlemeli motorlarda kötü tasarlanmış kalıplar, masum görünen bir girişte olağanüstü uzun süre çalışabilir. Buna katastrofik geri izleme denir. Çözüm, daha karmaşık bir desen yazmak değil; çoğu zaman problemi doğru katmana bölmektir: Önce regex ile biçimi ayıkla, sonra ayrıştırıcıyla yapıyı doğrula, en son uygulama mantığıyla anlamı denetle.
Chomsky Hiyerarşisi bize yalnızca dilleri sınıflandırmayı öğretmez; araç seçmenin ahlakını da öğretir. Bir çekiçle her şeyi çivi saymak yerine, metnin gerçekten ne istediğini sormayı önerir. Bazen bir yıldız işareti yeterlidir. Bazen bir yığın gerekir. Bazen de aradığınız şey metindeki desen değil, metnin taşıdığı yapıdır.