Dilbilgisi kurallarında kullanılan left recursion ve right recursion, dilbilgisi kurallarının nasıl yazıldığına bağlı olarak, ayrıştırma işlemlerinde farklı zorluklar ve çözüm yöntemleri gerektiren iki farklı yapıdır. Bu yapılar, özellikle derleyici tasarımında ve çözümleyicilerin (parser) nasıl implemente edildiği konusunda önemlidir.

Left Recursion

Bir dilbilgisi kuralı kendisini doğrudan veya dolaylı olarak kendi üretimlerinin en soluna çağırıyorsa, bu left recursion olarak adlandırılır. Yani bir dilbilgisi kuralı A için;

A → Aα | β

şeklinde bir yapı söz konusu olduğunda, burada A kendisini takip eden başka simgelerle (α) yeniden çağırmaktadır. β ise left recursion alternatifsiz kuralını temsil eder. Left recursion, özellikle LL çözümleyiciler için problem oluşturur çünkü bu tür çözümleyiciler girişi soldan sağa doğru okur ve sürekli kendini çağıran bir kurala rastladıklarında sonsuz bir döngüye girebilirler.

Örnek:

A → A "if" | "true"

Right Recursion

Right recursion ise, bir dilbilgisi kuralının kendisini doğrudan veya dolaylı olarak kendi üretimlerinin en sağına çağırması durumudur. Bu durumda, kural genellikle daha fazla girdi okunmasını gerektirir ve çözümleyici girdinin sonuna doğru ilerledikçe recursion gerçekleşir.

A → αA | β

Bu yapıda, A kendisini takip eden başka simgelerle (α) yeniden çağırmakta fakat bu sefer çağrı üretimin sonunda yer almaktadır. Right recursion LR çözümleyiciler için daha uygun olabilir çünkü bu çözümleyiciler girişi sağdan sola doğru işler.

Örnek:

A → "if" A | "true"

Çözüm Yöntemleri

Left recursion, LL çözümleyiciler için uygun değildir ve bu tür recursion'ı kaldırmak gerekir. Bu genellikle recursion'ı right recursion'a dönüştürmek ya da iterative bir yapı kullanarak çözümlemekle mümkündür. Right recursion ise, daha çok stack kullanımını arttırabilir, bu da performans ve hafıza kullanımı açısından dezavantaj yaratabilir. Ancak, genellikle LR çözümleyiciler için daha doğal bir yapı sunar.

Her iki recursion türü de, dil tasarımı ve çözümleyici implementasyonu sırasında dikkate alınması gereken önemli faktörlerdir.