Strona główna

Analizator syntaktyczny


Pobieranie 41.3 Kb.
Data18.06.2016
Rozmiar41.3 Kb.
Analizator syntaktyczny


Analizator syntaktyczny (parser) ma za zadanie dokonać rozbioru syntaktycznego tekstu źródłowego analizowanego programu. Analizator leksykalny (skaner) dokonuje zamiany tekstu wejściowego na ciąg tokenów. Nie zostaje przy tym zmieniona struktura syntaktyczna programu wejściowego. Parser pracuje na podstawie gramatyki syntaktycznej Gs, która na ogół jest gramatyką bezkontekstową. Od parsera oczekujemy odtworzenia wywodu i jakiegoś zanotowania tego wywodu. Najczęściej stosowanym sposobem notowania wyprowadzenia jest podanie ciągu numerów produkcji. Niekiedy równolegle z analizą syntaktyczną parser wykonuje pewne akcje semantyczne jak np. generowanie kodu pośredniego w postaci ONP, tetrad (n-tek), itd.


Działanie parsera:

We: TS* ( jest słowem nad alfabetem TS, TS jest zbiorem tokenów)

Wy: =p1...pi...pn (pi—numer produkcji)

lub err (błąd syntaktyczny)



Przykład:


GS=<{E,T,F},{id,+,*,(,)},P,E>

P:


  1. EE+T

  2. ET

  3. TT*F

  4. TF

  5. F(E)

  6. Fid



Analizowane słowo: (id+id)*id

Do zbudowania drzewa rozbioru syntakt. (podstawa konstrukcji kodu wynikowego) niezbędna jest wiadomość, że ciąg numerów produkcji związany jest z wywodem (tutaj) lewostronnym tworzonym metodą top-down



(2)

(3)

(4)

(5)

(1)

(2)

(4)

(6)

(4)

(6)

(6)

E

T


T*F

F*F

(E)*F

(E+T)*F

(T+T)*F

(F+T)*F

(id+T)*F

(id+F)*F

(id+id)*F

(id+id)* id acc

ciąg numerów produkcji


jest wyjściem z parsera






Generacja parsera:
We: gramatyka syntaktyczna GS=S,TS,PS,ZS> (oznaczana dalej G=)

Wy: algorytm parsera


Algorytm parsera musi być efektywny. Uniwersalny algorytm Earley’a ma dla gramatyki bezkontekstowej (bez ograniczeń na jednoznaczność) złożoność obliczeniową: czasową O(n3), pamięciową O(n2), zaś dla gramatyk jednoznacznych złożoność czasowa wynosi O(n2). Są to złożoności niedopuszczalne w praktyce. Studenci zechcą sobie także przypomnieć algorytm Cocke’a-Youngera-Kasamiego (CYK) i wiadomości o jego złożoności. Musimy się posługiwać algorytmami prostszymi, ale wiąże się to z zawężeniem klasy gramatyk.

Dla gramatyk LL(k) i LR(k) złożoność obliczeniowa algorytmu parsera wynosi:

czasowa O(n) oraz pamięciowa O(n).
Dalej rozpatrywane będą algorytmy parsingu dla gramatyk LL(k) i LR(k)





Na ogół stosowane są gramatyki:



  • LL(1)

  • LR(1) – oraz jej podklasy SLR(1) oraz LALR(1), dające możliwość znacznego uproszczenia algorytmu parsingu przy niewielkim ograniczeniu „możliwości” gramatyki.


Definicja zbiorów FIRST i FOLLOW


G = < N, T, P, Z >  GBK
FIRSTK () = {xT* | (*x  |x|=k)  (*x  |x|*}
Zbiór FIRSTK() jest zbiorem wszystkich terminalnych przedrostków długości k (lub mniejszej, jeżeli z  wyprowadza się łańcuch terminalny krótszy niż k) łańcuchów, które mogą być wyprowadzalne z 
FOLLOWK() = {xT*: (Z*  xFIRSTK(); ,,(NT)*}
Zbiór FOLLOWK() zawiera terminalne łańcuchy o długości k (lub mniejszej—patrz powyżej), które mogą pojawić się w wyprowadzeniach jako następniki . Uwaga: jeśli FOLLOWK() zawiera x, |x|Wyznaczanie FIRST1 dla gramatyki G=GBK
Wyznaczanie FIRST1(x) dla x(NT)

  1. if xT then FIRST1(x):={x};

  2. if (x)P then FIRST1(x):= FIRST1(x){};

  3. if xN and (xy1y2...yk)P then

begin

FIRST1(x):=FIRST1(x)(FIRST1(y1)\{})



for i:=2 to k do

if (FIRST1(y1))and...and(FIRST1(yi-1))

then FIRST1(x):=FIRST1(x)(FIRST1(yi)\{});

if (FIRST1(y1))and...and(FIRST1(yk)) then FIRST1(x):=FIRST1(x){}



end;

Aby wyznaczyć FIRST1(x) dla wszystkich X(NT) należy stosować reguły (1), (2) i (3) tak długo, aż nic nowego nie da się dołączyć do któregokolwiek zbioru FIRST1(x).


Wyznaczanie FIRST1(x1x2...xn)

FIRST1(x1x2xn):=FIRST1(x1)\{}



for i:=2 to k do

if (FIRST1(x1))andand(FIRST1(xi-1))then

FIRST1(x1xn):= FIRST1(x1xn)(FIRST1(xi)\{});

if (FIRST1(x1))andand(FIRST1(xn)) then FIRST1(x1xn):= FIRST1(x1xn){};
Wyznaczenie FOLLOW1 dla wszystkich AN

Stosować poniższe reguły (1), (2), (3) dopóty nic nowego nie może już zostać dodane do żadnego zbioru FOLLOW1.



  1. FOLLOW1(Z):=FOLLOW1(Z){$}

  2. if (AB)P then

FOLLOW1(B):=FOLLOW1(B)(FIRST1()\{})

  1. if (AB)P

or ((AB)P and (FIRST1()))

then FOLLOW1(B):=FOLLOW1(B)FOLLOW1(A);

Przykład:


  1. ETE’

  2. E’+TE’|

  3. TFT’

  4. T’*FT’|

  5. F(E)|id

FIRST1[+]={+}

FIRST1[*]={*}

FIRST1[(]={(}

FIRST1[)]={)}

FIRST1[id]={id}


FIRST1(E)={(, id} ETE’FT’E’(E)T’E’

ETE’FT’E’idT’E’

FIRST1(E’)={,+}

FIRST1(T)={(, id }

FIRST1(T’)={,*}

FIRST1(F)={(, id}


FOLLOW1(E)={$,)}

FOLLOW1(E’)={$,)}

FOLLOW1(T)={+,),$} ETE’T+TE’

FOLLOW1(T’)={+,),$}



FOLLOW1(F)={+,*,),$}


©snauka.pl 2016
wyślij wiadomość