1. ev
  2. Soru-cevap
  3. Bir RegEx motoru nasıl çalışır?

Bir RegEx motoru nasıl çalışır?

2010-09-01 16 views
27

Düzenli İfadeler öğrenirken, altta yatan motorun nasıl çalıştığını merak etmiştim. Muhtemelen daha spesifik olarak, nasıl değerlendirdiği, öncelik verdiği ve ifadeyi nasıl ayrıştırdığı hakkında daha fazla bilgi edinmek isterim. RegEx motorunun benim için bir kara kutu olduğunu hissediyorum ve gerçekten deşifre etmekten keyif alacağım.Bir RegEx motoru nasıl çalışır?

Bu yüzden, RegEx motor teorisini tartışan bazı büyük kaynaklar olup olmadığını sormak istiyorum.

* Not: Sadece bir motoru inşa etmekle ilgilenmiyorum, sadece iç işleyişini öğreniyorum.

kaynak

2010-09-01 Robb

+1

o konuya odaklanmış değil gerçi harika bir kitap, her regex motoru nasıl davranacağını ile uğraşan birkaç bölüm var. (motorun detaylarını analiz etmekten ziyade pratik bir yol olsa da) – NorthGuard

+0

Aslında bu kitabın etrafında dolaşıyordum ama bu bölümleri bilmiyordum. Teşekkürler! – Robb

+1

Mükemmel bir sanat eseri: [RegEx nasıl çalışır] (http://perl.plover.com/Regex/article.html) – PHPst

cevap

32

İki temel regex motoru sınıfı vardır.

  1. sonlu durum otomatı dayalı olanlar. Bunlar genellikle en hızlı olanlardır. Bir state machine yapılandırarak ve karakterleri giriş dizesinden besleyerek çalışırlar. Bu gibi motorlarda bazı daha gelişmiş özellikleri uygulamak imkansız değilse zor. FSA göre motorların

    Örnekler:

    • Posix/GNU

      ERE/örneğin grep, sed ve awk gibi en Unix programları, kullanılır BRE —.
    • Re2 — Automata tabanlı yönteme daha fazla güç vermeye çalışmak için nispeten yeni bir proje.
       

  2. olanlar geri izleme dayalı. Bunlar genellikle modeli makine talimatlarına benzeyen bayt koduna derler. Motor daha sonra kodu yürütür, talimattan eğitime atlar. Bir talimat başarısız olduğunda, daha sonra girişi eşleştirmek için başka bir yol bulmak için geri izler. Geri izleme dayalı motorların

    Örnekler:

    • Perl — orijinal. Bu türdeki diğer çoğu motor, Perl dilinde regeeks işlevlerini çoğaltmaya çalışır.
    • PCRE — En başarılı uygulama. Bu kütüphane en yaygın kullanılan uygulamadır. Bazıları "Regular" olarak kabul edilemeyen zengin bir özellikler kümesine sahiptir.
    • Python, Ruby, Java, .NET — Diğer uygulamalar Daha fazla açıklamaya niyetim yok. Daha fazla bilgi için

:

beni, bir şey üzerinde genişletmek Yorum yazmak istiyorum. Normal İfadeleri Mastering

kaynak

2010-09-02 11:17:15

+0

Görünen linkler ile benim için bazı işlerim var gibi görünüyor ama sanırım bu aradığım şey daha çok. Dahası, satın alınabilecek gerçek bir kitabı biliyorsanız, bu harika olurdu. – Robb

+0

Konuyla ilgili pek çok kitap okumadım, ama sevdiğim biri Michael Sipser tarafından "Hesaplama Teorisine Giriş". Sadece Düzenli İfadeler değil, Turing Makinelerine ve NP-tamamlığına, vb. –

İlgili konular

 İlgili konular