Parser LL(*)

Parser LL(*) to lewostronny parser z podglądem dowolnej liczby symboli.

Parsery lewostronne mają tę zaletę w porównaniu z prawostronnymi, że produkcje mogą być w naturalny sposób przestawione w kodzie jako funkcje rekurencyjne. Zwykle jednak wadą prostych parserów LL jest to, że mogą parsować mniejszą klasę języków niż parsery LR jak np. LALR. Dotyczy to parserów LL bez podglądu czy z podglądem jednego symbolu, jednak obecnie rozwijane są parsery LL(*) umożliwiające podgląd dowolnej ilości symboli w razie potrzeby. Taki parser użyty jest w narzędziu ANTLR.

Algorytm tworzenia parsera LL(*)

Dla zadanej gramatyki budujemy grafy ATN. W ten sposób że węzeł startowy grafu jest oznaczony nazwą symbolu nieterminalnego, przechodzi się do innego węzła poprzez krawędzie oznaczone symbolami terminalnymi, $\epsilon$ lub symbolami nieterminalnymi. Gdy używamy do przejścia symbolu nieterminalnego, wkładamy na stos docelowy węzeł grafu, i przechodzimy do sieci ATN dla tego symbolu nieterminalnego.

Przykładowa prosta gramatyka:

 S->Ac
 S->Ad
 A->aA
 A->b

Mamy dla niej dwie sieci ATN, po jednej dla każdego symbolu, dla S:

i dla A:

DFA

Weźmy wejście: bc, czy mamy wybrać S->Ac czy S->Ad? To nie jest gramatyka LL(1). Należy użyć predykcji. Tworzymy automat DFA w ten sposób że każdy jego stan jest zbiorem konfiguracji, gdzie konfiguracja to węzeł ATN, numer produkcji którą mamy wybrać w początkowym stanie oraz stos. Wygląda to tak:

Stan początkowy $D_{0}$ jest zbiorem wszystkich stanów ATNów osiągalnych ze stanu początkowego bez konsumpcji żadnego symbolu terminalnego, jedynie przez dojście do innych stanów ATN przez $\epsilon$ i odpowiednie symbole nieterminalne. Na początku w $D_{0}$ mamy dwie początkowe konfiguracje oznaczone grubszą czcionką, dodajemy dla nich przejścia przez symbole nieterminalne A, więc stos z [] zmienia się na $p_{1}$ i $p_{3}$ i idziemy do drugiego ATN. W ten sposób mamy zbiór konfiguracji.
Następnie podglądamy symbol b: z ostatnich konfiguracji w zbiorze możemy pójść przez b: z $(p_{A,1},2,p_{3})$ idziemy do $(p_{7},1,p_{1})$ a z $(p_{A,2},2,p_{3})$ idziemy do $(p'_{A},1,p_{1})$
Patrzymy, że nadal w zbiorze konfiguracji występują numery 1 i 2 numerów produkcji ze stanu bazowego predykcji. Czyli podglądamy jeszcze jeden symbol c i mamy już wybór produkcji numer 1, a dla d była by 2.

{Przypisy}