Derleyici Tasarımı - Normal İfadeler

Sözcük analizcisinin, eldeki dile ait olan yalnızca sınırlı bir dizi geçerli dizge / simge / sözcük birimi taraması ve tanımlaması gerekir. Dil kuralları tarafından tanımlanan kalıbı arar.

Düzenli ifadeler, sonlu sembol dizileri için bir model tanımlayarak sonlu dilleri ifade etme yeteneğine sahiptir. Normal ifadelerle tanımlanan dilbilgisi şu şekilde bilinir:regular grammar. Normal gramer tarafından tanımlanan dil şu şekilde bilinir:regular language.

Düzenli ifade, kalıpları belirlemek için önemli bir gösterimdir. Her desen bir dizi dizeyle eşleşir, bu nedenle normal ifadeler bir dizi diziye ad görevi görür. Programlama dili belirteçleri normal diller tarafından tanımlanabilir. Normal ifadelerin belirtimi, yinelemeli tanımlamaya bir örnektir. Normal dillerin anlaşılması kolaydır ve verimli bir şekilde uygulanır.

Düzenli ifadeleri eşdeğer formlara dönüştürmek için kullanılabilen, düzenli ifadelerin uyduğu bir dizi cebirsel yasa vardır.

Operasyonlar

Diller üzerindeki çeşitli işlemler şunlardır:

  • İki dilin birliği L ve M olarak yazılır

    LUM = {s | s L'de veya s M'de}

  • L ve M olmak üzere iki dilin birleştirilmesi şu şekilde yazılır:

    LM = {st | s L'dir ve t M'dir}

  • L dilinin Kleene Kapanması şu şekilde yazılır:

    L * = L dilinin sıfır veya daha fazla oluşumu.

Notasyonlar

R ve s, L (r) ve L (s) dillerini belirten normal ifadeler ise, o zaman

  • Union : (r) | (s), L (r) UL (s) 'yi ifade eden düzenli bir ifadedir

  • Concatenation : (r) (s), L (r) L (s) anlamına gelen normal bir ifadedir

  • Kleene closure : (r) *, (L (r)) * anlamına gelen normal bir ifadedir *

  • (r), L (r) 'yi ifade eden normal bir ifadedir

Öncelik ve İlişkilendirme

  • *, birleştirme (.) ve | (boru işareti) ilişkisel bırakılır
  • * en yüksek önceliğe sahiptir
  • Birleştirme (.) İkinci en yüksek önceliğe sahiptir.
  • | (boru işareti) hepsinden daha düşük önceliğe sahiptir.

Normal ifadede bir dilin geçerli belirteçlerini temsil etme

X bir normal ifadeyse, o zaman:

  • x * sıfır veya daha fazla x oluşumu anlamına gelir.

    yani, {e, x, xx, xxx, xxxx,…} oluşturabilir

  • x +, x'in bir veya daha fazla oluşumu anlamına gelir.

    yani, {x, xx, xxx, xxxx…} veya xx * oluşturabilir

  • x? en fazla bir x oluşumu anlamına gelir

    yani, {x} veya {e} oluşturabilir.

  • [az], İngilizce'nin tümü küçük harfli alfabelerdir.

    [AZ], İngilizce'nin tümü büyük harfli alfabelerdir.

    [0-9] matematikte kullanılan tüm doğal rakamlardır.

Normal ifadeler kullanarak sembollerin oluşumunu temsil etme

letter = [a - z] veya [A - Z]

digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 veya [0-9]

işaret = [+ | -]

Normal ifadeler kullanarak dil belirteçlerini temsil etme

Ondalık = (işaret) ? (basamak) +

Tanımlayıcı = (harf) (harf | rakam) *

Sözcüksel analizörle geriye kalan tek sorun, bir dilin anahtar kelime kalıplarını belirlemede kullanılan düzenli ifadenin geçerliliğinin nasıl doğrulanacağıdır. Kabul gören bir çözüm, doğrulama için sonlu otomat kullanmaktır.