Parsery LL
Języki formalne i automaty
Dr in\
. Janusz Majewski
Katedra Informatyki
Zadanie analizy generacyjnej
(zstępującej, top-down)
Odtworzenie wywodu lewostronnego metodÄ… top-down
Istota gramatyki i parsera LL(k)
Jeśli odpowiedz
na ka\
dorazowe
pierwszy
pytanie:  KtórÄ… produkcjÄ™ A ²
od lewej
zastosować?  jest zawsze
nieterminal
jednoznaczna, gramatyka jest
klasy LL(k)
} analizowany łańcuch
ju\
wyprowadzone podglądana część wejścia (na ogół k=1)
Nierekurencyjny analizator
top-down
Konfiguracja parsera LL
Konfiguracja: (#XXZY, bbb$, 3122)
nieprzeczytana
stos wyjście
część wejścia
Krok  pop
Krok  pop
Krok  wyprowadzenia
ABb
Krok  wyprowadzenia
ABb
Projektowanie tablicy parsera LL
Mając przekształconą
1) E TE
gramatykę języka oraz
2) E +TE
wyznaczone (dla
3) E µ
symboli nieterminalnych
4) T FT
tej gramatyki) zbiory
5) T *FT
FIRST1 i FOLLOW1
6) T µ
mo\
emy przystąpić do
7) F (E)
projektowania tablicy
8) F id
parsera LL.
Tablica parsera
FIRST FOLLOW
id + * ( ) $
E (, id $, )
E +, µ $, )
T (, id +, $, )
T *, µ +, $, )
F (, id *, +, $, )
Tablica parsera
FIRST FOLLOW
id + * ( ) $
ETE ETE
E (, id $, )
(1) (1)
E +, µ $, )
T (, id +, $, )
T *, µ +, $, )
F (, id *, +, $, )
Tablica parsera
FIRST FOLLOW
id + * ( ) $
ETE ETE
E (, id $, )
(1) (1)
E +, µ $, )
TFT TFT
T (, id +, $, )
(4) (4)
T *, µ +, $, )
F (, id *, +, $, )
Tablica parsera
FIRST FOLLOW
id + * ( ) $
ETE ETE
E (, id $, )
(1) (1)
E +, µ $, )
TFT TFT
T (, id +, $, )
(4) (4)
T *, µ +, $, )
Fid F(E)
F (, id *, +, $, )
(8) (7)
Tablica parsera
FIRST FOLLOW
id + * ( ) $
ETE ETE
E (, id $, )
(1) (1)
E +, µ $, )
TFT TFT
T (, id +, $, )
(4) (4)
T *FT
T *, µ +, $, )
(5)
Fid F(E)
F (, id *, +, $, )
(8) (7)
Tablica parsera
FIRST FOLLOW
id + * ( ) $
ETE ETE
E (, id $, )
(1) (1)
E +, µ $, )
TFT TFT
T (, id +, $, )
(4) (4)
T µ T *FT T µ T µ
µ µ µ
µ µ µ
µ µ µ
T *, µ +, $, )
(6) (5) (6) (6)
Fid F(E)
F (, id *, +, $, )
(8) (7)
Tablica parsera
FIRST FOLLOW
id + * ( ) $
ETE ETE
E (, id $, )
(1) (1)
E +TE E µ E µ
µ µ
µ µ
µ µ
E +, µ $, )
(2) (3) (3)
TFT TFT
T (, id +, $, )
(4) (4)
T µ T *FT T µ T µ
T *, µ +, $, )
(6) (5) (6) (6)
Fid F(E)
F (, id *, +, $, )
(8) (7)
Symulacja działania parsera LL
Stos Wejście Wyjście
E id+id$ µ
E T id+id$ 1
E T F id+id$ 14
E T id id+id$ 148
E T +id$ 148
E +id$ 1486
E T+ +id$ 14862
E T id$ 14862
E T F id$ 148624
E T id id$ 1486248
E T $ 1486248
E $ 14862486
µ $ 148624863
akceptacja