"Left factoring" bir dilbilgisinin çözümlenmesini kolaylaştırmak için kullanılan bir derleyici tasarım tekniğidir. Özellikle, bu teknik, bir çözümleyicinin (parser) aynı giriş dizisi için birden fazla ayrıştırma yolunu denemesi gereken durumları ortadan kaldırmak için kullanılır. Bu, özellikle geriye dönük (backtracking) çözümleyiciler için faydalıdır ve çoğunlukla LL(1) çözümleyicilerin kullanımında önemlidir.

Left Factoring Nasıl Yapılır?

Bir dilbilgisindeki left factoring işlemi, birden fazla üretim kuralının aynı sembollerle başlaması durumunda yapılır. Örneğin, aşağıdaki gibi bir dilbilgisi düşünelim:

A → αβ₁ | αβ₂

Burada, A üretim kuralı α ile başlayan iki alternatife sahiptir. Bu durum çözümleyicide kararsızlığa yol açabilir. Left factoring teknik ile bu iki kural şöyle yeniden düzenlenebilir:

A → αA'

A' → β₁ | β₂

Bu şekilde, çözümleyici ilk olarak α ile başlayıp başlamadığını kontrol eder ve eğer öyleyse, hangi yolu takip edeceğine A' üzerinden karar verir. Bu, çözümleyicinin karar verme sürecini basitleştirir ve performansını artırır.

Bir dilbilgisinde left factoring uygulamak için bir Python örneği verebilirim. Diyelim ki, aşağıdaki üretim kurallarına sahip basit bir dilbilgimiz var:

A → "if" E "then" A "else" A | "if" E "then" A

Bu durumda, A üretimi, "if" kelimesi ile başlayan iki alternatife sahip ve bu durum çözümleyici için kararsızlık yaratabilir. Left factoring tekniğini kullanarak bu durumu çözebiliriz.

İlk olarak, Python'da basit bir yapı kurarak bu dilbilgisi kurallarını temsil edelim ve ardından left factoring uygulayalım:

# Dilbilgisi kurallarını temsil etmek için bir sınıf
class Grammar:
    def __init__(self):
        self.rules = {}

    def add_rule(self, non_terminal, productions):
        self.rules[non_terminal] = productions

    def left_factor(self):
        new_rules = {}
        for non_terminal, productions in self.rules.items():
            if len(productions) > 1:
                common_prefix = self.find_common_prefix(productions)
                if common_prefix:
                    # Left factoring uygula
                    new_non_terminal = non_terminal + "'"
                    new_productions = [prod[len(common_prefix):] if prod != common_prefix else 'ε' for prod in productions]
                    new_rules[non_terminal] = [common_prefix + new_non_terminal]
                    new_rules[new_non_terminal] = new_productions
                else:
                    new_rules[non_terminal] = productions
            else:
                new_rules[non_terminal] = productions
        self.rules = new_rules

    def find_common_prefix(self, productions):
        # En kısa üretimi bul
        min_length_prod = min(productions, key=len)
        for i in range(len(min_length_prod)):
            current_char = min_length_prod[i]
            for prod in productions:
                if not prod.startswith(min_length_prod[:i + 1]):
                    return min_length_prod[:i]
        return min_length_prod

    def display_rules(self):
        for non_terminal, productions in self.rules.items():
            print(f"{non_terminal} -> {' | '.join(productions)}")

# Dilbilgisi kurallarını oluştur
grammar = Grammar()
grammar.add_rule('A', ['if E then A else A', 'if E then A'])

# Dilbilgisini görüntüle
print("Original Grammar:")
grammar.display_rules()

# Left factoring uygula
grammar.left_factor()

# Yeniden düzenlenmiş dilbilgisini görüntüle
print("\nLeft Factored Grammar:")
grammar.display_rules()

Bu örnekte, Grammar sınıfı dilbilgisinin kurallarını saklar ve left factoring uygular. left_factor metodu, her bir üretim kuralını inceler, ortak bir önek bulur ve dilbilgisini buna göre yeniden düzenler. find_common_prefix fonksiyonu, verilen üretimler arasında ortak olan en uzun öneki bulmaya çalışır.