Tekst źródłowy strony 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 LL|parserów LL]] jest to, że mogą parsować mniejszą klasę języków niż [[Parser LR|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 [[Rekurencyjna sieć przejść|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, <math>\epsilon</math> 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:<syntaxhighlight lang="text">
 S->Ac
 S->Ad
 A->aA
 A->b
</syntaxhighlight>
Mamy dla niej dwie sieci ATN, po jednej dla każdego symbolu, dla S:
[[File:ATN for grammar nterm S.png|top|]]
:i dla A:
[[File:ATN for grammar nterm A.png|top|]]
===DFA===
Weźmy wejście: bc, czy mamy wybrać <code>S->Ac</code> czy <code>S->Ad</code>? 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: <ref>Adaptive LL(*) Parsing: The Power of Dynamic Analysis[https://www.antlr.org/papers/allstar-techreport.pdf]</ref>
:[[File:Dynamic DFA for LL grammar.png|top|]]

Stan początkowy <math>D_0</math> 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 <math>\epsilon</math> i odpowiednie symbole nieterminalne.
Na początku w <math>D_0</math> mamy dwie początkowe konfiguracje oznaczone grubszą czcionką, dodajemy dla nich przejścia przez symbole '''nieterminalne''' A, więc stos z [] zmienia się na <math>p_1</math> i <math>p_3</math> i idziemy do drugiego ATN. 
W ten sposób mamy zbiór konfiguracji. <br>
Następnie podglądamy symbol b: z ostatnich konfiguracji w zbiorze możemy pójść przez b: z <math>(p_{A,1},2,p_3)</math> idziemy do <math>(p_7,1,p_1)</math> a z <math>(p_{A,2},2,p_3)</math> idziemy do <math>(p'_A,1,p_1)</math><br>
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}

== Przypisy ==
{{Przypisy}}

[[Kategoria:Parsery]]