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


Wyszukiwarka

Podobne podstrony:
WFiIS 12 Parsery LR
11 (311)
ZADANIE (11)
Psychologia 27 11 2012
359 11 (2)
11
PJU zagadnienia III WLS 10 11
Wybrane przepisy IAAF 10 11
06 11 09 (28)
info Gios PDF Splitter And Merger 1 11

więcej podobnych podstron