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: Adaptive LL(*) Parsing: The Power of Dynamic Analysis
Stan początkowy 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 i odpowiednie symbole nieterminalne. Na początku w mamy dwie początkowe konfiguracje oznaczone grubszą czcionką, dodajemy dla nich przejścia przez symbole nieterminalne A, więc stos z [] zmienia się na i 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 idziemy do a z idziemy do 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łaby 2.
{Przypisy}
Przypisy
Kategoria:Parsery