Un operatore associativo sinistro può essere espresso in modo tale che i parser LL (1) dall'alto verso il basso possano comprendere?

Question

Stavo cercando di implementare un parser LL (1) dall'alto verso il basso per una lingua della calcolatrice. Ci consente solo di sommare, sottrarre, dividere e moltiplicare i numeri. Nessuna parentesi.

S -> A 

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

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

Poiché questa grammatica non è adatto a un LL (1) parser, ho dovuto cambiare un bel po ':

S -> A 

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

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

Il problema è che ora la grammatica non è lasciato associativa per il 4 operatori mostrati, e ho bisogno che sia così. Come risolvere questo problema? È persino possibile farlo?

Answer 1

È possibile ottenere l'associatività a sinistra sostituendo la ricorsione con iterazione. Il seguente tipo di pseudocodice calcola direttamente i valori solo per semplicità, ma è possibile generare un albero di analisi usando lo stesso metodo.

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) 
} 

dove peek() restituisce il token successivo senza mangiare, e match() mangia il token successivo. Faresti la stessa cosa per B().