Czy lewy operator asocjacyjny może być wyrażony w taki sposób, aby zrozumieć parsery LL (1)?

Question

Próbowałem zaimplementować parser topologii LL (1) dla języka kalkulatora. Pozwala nam tylko sumować, odejmować, dzielić i mnożyć liczby. Bez nawiasów.

S -> A 

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

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

Ponieważ gramatyka nie nadaje się do LL (1) parser, musiałem go zmienić sporo:

S -> A 

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

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

Problem polega na tym, że teraz gramatyka nie jest wiązanie lewe dla 4 pokazano operatorów, i potrzebuję, żeby tak było. Jak rozwiązać ten problem? Czy można to osiągnąć?

Answer 1

Możesz uzyskać lewostronność, zastępując rekurencję za pomocą iteracji. Poniższy sort-pseudocode bezpośrednio oblicza wartości tylko dla prostoty, ale można wygenerować drzewo analizowania przy użyciu tej samej metody.

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

gdzie peek() zwraca następny znak bez jedzenia i match() zjada następny token. Zrobiłbyś to samo dla B().