Sol birleştirici bir işleç, yukarıdan aşağı LL (1) ayrıştırıcılarının anlayabileceği şekilde ifade edilebilir mi?

Question

Bir hesap makinesi dili için bir LL (1) yukarıdan aşağı çözümleyici kullanmaya çalışıyordum. Sadece sayıları toplamanıza, çıkarmamıza, bölmemize ve çarpmamıza izin verir. Parantez yok. Bu dilbilgisi bir LL (1) ayrıştırıcı için uygun değildir gibi

S -> A 

A -> B + A 
    | B - A 
    | B 

B -> int * B 
    | int/B 
    | int 

, bunu biraz değiştirmek zorunda:

S -> A 

A -> B A' 
A'-> + A 
    | - A 
    | λ 

B -> int B' 
B'-> * B 
    |/B 
    | λ 

sorun şimdi dilbilgisi için ilişkisel kalmaması olduğunu Gösterilen 4 operatör ve buna ihtiyacım var. Bu problem nasıl çözülür? Bunu başarmak bile mümkün mü?

Answer 1

Yinelemeyi yinelemeli olarak değiştirerek sol ilişkiyi alabilirsiniz. Aşağıdaki sıralama-türkodu kodu, sadece basitlik için değerleri doğrudan hesaplar, ancak aynı yöntemi kullanarak bir ayrıştırma ağacı oluşturabilirsiniz.

function A() { 
    val = B(); 
    t = peek(); 
    while (t=='+' || t=='-') { 
    match(t); 
    val1 = B(); 
    if (t=='+') 
     val = val + val1; 
    else 
     val = val - val1; 
    t = peek(); 
    } 
    return(val) 
} 

peek() yemekten sonraki belirteci döndürür

ve match() sonraki jetonu yiyor. B() için de aynısını yaparsın.