Limbaje formale şi translatoare (Compilatoare)

1

1. Analiza sintactică predictivă

2. Analiza sintactică descendentă cu reveniri

3. Analiza sintactică prin coborâre recursivă

4. Maşina abstractă de analiză predictivă

5. Analiza sintactică LL(1)

6. Maşina abstractă de analiză LL(1)

2

Analiza sintactică predictivă poate fi modelată prin intermediul unui automat finit cu stivă care lucrează asupra unui şir de intrare.

AF

Si

St

isi

ist

LIFO

Si – şirul de intrare (conţine atomii lexicali obţinuţi în urma etapei de analiză lexicală) isi – indice pentru Si St – stiva (acces LIFO) ist – vârful stivei

3

Analiza sintactică predictivă pleacă de la notiunea de

derivare stânga:

S => w1 => … => wn,

unde wi = xiAI, wi+1 = xiiI,

cu proprietatea A -> i P,

iar xi * şi I (VN)*

4

Algoritmul analizei sintactice predictive pentru un limbaj definit printr-o gramatică generatoare este:

1. Analiza sintactică porneşte de la simbolul de start S, care este introdus în stivă.

2. Se face expandarea vârfului stivei, alegând convenabil o regulă de producţie.

3. Dacă în vârful stivei apare un terminal, acesta este comparat cu simbolul curent din şirul de intrare. Dacă cele două simboluri sunt egale, atunci vârful stivei este scos şi se avansează în şirul de intrare. Altfel, se semnalează eroare.

4. La sfârşit, dacă stiva este goală şi s-a ajuns la sfârşitul şirului de intrare, atunci acesta este corect. Altfel nu este corect.

5

Procedura de analiza este

sf = false

repeta

daca (st(ist))(st(ist)=si(isi))

atunci ist <- ist - 1

isi <- isi + 1

ori st(ist) VN

atunci expandez varful stivei cu o productie

având în vedere şi simbolul curent

din şirul de intrare

ori (st(ist)=ε) (si(isi)= ε)

atunci succes

sf <- true

altfel eroare

sf <- true

pana sf sf

6

Ex:

Fie gramatica generatoare pentru care mulţimea regulilor de producţie este:

Şi fie propoziţia:

Funcţionarea automatului de analiză sintactică predictivă va fi:

7

8

Modelul matematic este automatul finit cu stiva

AP = <Q, , , f, q0, z0, F> unde

Q - multimea de stari,

- alfabetul automatului,

- alfabetul stivei,

z0 - simbolul initial al stivei,

q0 - stare initiala,

F - multimea de stari finale,

f - functia de tranzitie

f : Q x ( Σ U{ ε }) x --> P (Q x *)

- unde P este o multime de perechi

9

Starea automatului

(q, x, ), qQ, x *, *

Tranziţie

(q1, ax, z) ├ (q2, x, ) <=> (q2, ) f(q1, a, z)

Un sir w * este acceptat de către automat

• după criteriul stării vide (q0, w, z0) ├ (q, ε, ε)

• criteriul starii finale (q0, w, z0) ├ (q, ε, ), q F

10

Fie gramatica :

E -> E + T | T

T -> T * F | F

F -> i | (E)

Neterminale : VN = {E, T, F}

Terminale : = {+, *, (, ), i}

11

Automatul de analiză sintactică predictivă:

Q = {q}

= {+, *, (, ), i}

= {E, T, F, +, *, (, ), i}

z0 = E

q0 = q

F =

AP = < {q}, {+, *, (, ), i}, {E, T, F, +, *, (, ), i} , f , q , E , >

f(q, a, a) = (q, ε) ,

f(q, ε, A) = (q, ) , oricare A-> P

f(q, ε, E) = {(q, E+T), (q, T)}

f(q, ε, T) = {(q, T*F), (q, F)}

f(q, ε, F) = {(q,i), q, (E)}

12

Pentru analiza propozitiei i*i+i evolutia automatului este :

(q, i*i+i , E) ├ (q, i*i+i , E+T) ├ (q, i , T)

├ (q, i*i+i , T+T) ├ (q, i , F)

├ (q, i*i+i , T*F+T) ├ (q, i , i)

├ (q, i*i+i , F*F+T) ├ (q, ε, ε)

├ (q, i*i+i , i*F+T)

├ (q, *i+i , *F+T)

├ (q, i+i , F+T)

├ (q, i+i , i+T)

├ (q, +i , +T)

13

Pentru a putea utiliza analiza sintactică predictivă, gramatica generatoare a limbajului ţintă trebuie să îndeplinească condiţiile:

1. Nu se foloseşte recursivitate stânga în regulile de producţie: nu există niciun neterminal A astfel încât A=+>Aα.

Îndeplinirea acestei condiţii asigură faptul că stiva nu se va extinde la infinit, având în vedere că se foloseşte derivarea stânga pentru înlocuirea neterminalelor.

2. Pentru orice neterminal, părţile drepte ale producţiilor sale încep diferit: Nu există două producţii A->αβ şi A->αγ, cu αdiferit de ε.

Această condiţie asigură identificarea uşoară a regulii de producţie care trebuie folosită pentru a expanda un neterminal din vârful stivei, pe baza simbolului curent din şirul de intrare.

14

Eliminarea recursivităţii stânga:

Dacă există reguli de producţie care folosesc recursivitatea stânga, de exemplu:

A->Aα, A->β

Atunci introducem un nou neterminal A’ şi înlocuim regulile în cauză cu:

A->βA’, A’->αA’, A’->ε

Ex:

15

Dacă nu este îndeplinită a doua condiţie, şi gramatica conţine, de exemplu, regulile:

A->αβ, A->αγ

Atunci introducem un nou neterminal A’ şi înlocuim regulile în cauză cu:

A-> αA’, A’->β, A’->γ

Ex:

16

Două exemple mai complexe:

1. Primul exemplu:

A -> Ac

A -> Aa

A -> b

Solutia este

A->bA'

A'->aA'

A'->cA'

A->epsilon

Dupa cum observati a mai aparut o tranzitie pentru A'. Acum avem cate o tranzitie pentru A', pentru fiecare regula a lui A care are recursivitate stanga.

17

Al doilea exemplu:

A -> ab

A -> ac

A -> Aa

Mai întâi se rezolvă problema primelor doua reguli de producţie, obținând:

A->Aa

A -> aA'

A'->b

A'->c

Apoi pentru primele doua reguli de producție aplicam transformarea pentru eliminarea recursivității stânga:

A->aA'A''

A''->aA''

A''->epsilon

A'->b

A'->c

18

Exerciţiu:

Fie gramatica:

Analizaţi sintactic propoziţia:

19

Analiza sintactică prin coborâre recursivă constituie o implementare deterministă a analizei sintactice predictive.

AF

Si

St1 St2

isi

ist2 ist1

Si – şirul de intrare (conţine atomii lexicali obţinuţi în urma etapei de analiză lexicală) isi – indice pentru Si St1 – stiva (acces LIFO) cu frunzele arborelui sintactic ist1 – vârful stivei St1 St2 – stiva de retur Ist2 – vârful stivei St2

20

Configuraţia automatului finit este data de: (s, i, , ),

Unde:

s - starea automatului finit, care poate fi:

◦ - q (stare normala),

◦ - b (stare de revenire),

◦ - e (stare de eroare),

◦ - t (stare de true)

j - indicele sirurului de intrare j1 j2…jn

- şirul din stiva St2, formată din simboluri deja recunoscute în şirul de intrare şi din indicii regulilor de producţie utilizate în derivări

β - şirul din stiva St1, formată din simboluri încă neexpandate

21

(1) stare initiala (q, 1, ε, S)

(2) expandarea (q, j, , A) ├ (q, j, A1, 1) , unde A1: A -> 1 este prima producţie pentru neterminalul A din vârful stivei St1 (A va fi expandat conform primei alternative)

(3) avans (q, j, , a) ├ (q, j+1, a, ), cand în varful stivei St1 se află un terminal identic cu cel din poziţia curentă (j) a şirului de intrare

(4) necoincidenta (q, j, , i) ├ (b, j, , i), cand în vârful stivei St1 se află un terminal care nu este identic cu cel din poziţia curenta (j) a şirului de intrare

(5) revenire in starea de intrare

(5.1) (b, j, i, ) ├ (b, j-1, , i), când în vârful stivei St2 se află un terminal; pasul 5.1 se repetă atâta timp cât se află un terminal în vârful stivei St2

(5.2) (b, j, Ai, i) ├ (q, j, Ai+1, i+1) , se sare la pasul 3

(5.3) (b, j, An, n) ├ (b, j, , A) , se sare la pasul 5.1

(6) esec (b, j, , S) ├ (e, j, , S)

(7) succes (q, n+1, , ε) ├ (t, n+1, , ε)

22

Ex:

Fie gramatica:

(S1) S -> Ab

(S2) S -> Ac

(A1) A -> a

(A2) A -> bAB

(B1) B -> a

Analizaţi propoziţia w *:

1. w = bbaaab

2. w= bbaabab

Starea initiala : (q, 1, ε, S)

23

├ (2) (q, 1, S1, Ab) //expandare (2)

├ (2) (q, 1, S1A1, ab) //st2(ist2)si(isi)

├ (4) (b,1,S1A1, ab) //necoincidenta (4)

├ (5.2) (q, 1, S1A2, bABb) //back (5)

├ (3) (q, 2, S1A2b, ABb) //avans (3)

├ (2) (q, 2, S1A2bA1, aBb) //expandare A1 -> a

├ (4) (b, 2, S1A2bA1, aBb) //necoincidenta

├ (5.2) (q, 2, S1A2bA2, bABBb) //revenire (back)

24

├ (3) (q, 3, S1A2bA2b, ABBb) //avans

├ (2) (q, 3, S1A2bA2bA1, aBBb) //expandare

├ (3) (q, 4, S1A2bA2bA1a, BBb) //avans

├ (2) (q, 4, S1A2bA2bA1aB1, aBb) //expandare

├ (3) (q, 5, S1A2bA2bA1aB1a, Bb) //avans

├ (2) (q, 5, S1A2bA2bA1aB1aB1, ab) //expandare

├ (3) (q, 6, S1A2bA2bA1aB1aB1a, b) //avans

├ (3) (q, 7, S1A2bA2bA1aB1aB1ab, $) //avans

├ (7) (q, 7, S1A2bA2bA1aB1aB1ab, ) //succes

25

Pentru a putea utiliza analiza sintactică cu reveniri, gramatica generatoare a limbajului ţintă trebuie să îndeplinească numai prima condiţie dintre cele cerute pentru analiza sintactică predictivă.

26

Este o implementare a analizei sintactice predictive.

Fiecare neterminal devine un nume de funcţie.

Funcţia pentru un anumit neterminal este responsabilă să verifice dacă se poate găsi la începutul şirului de intrare o derivare care porneşte de la acest neterminal.

Dacă nu este posibil, funcţia trebuie să sară peste ceea ce a găsit şi să semnaleze o eroare.

Există o funcţie principală care lansează funcţia pentru simbolul de start şi verifică dacă intrarea este vidă.

Există o funcţie next care face un avans cu o poziţie în şirul de intrare.

27

Exemplificăm construcţia funcţiilor necesare analizei sintactice prin coborâre recursivă pentru gramatica:

28

29

30

31

32

Exerciţii:

1. Scrieţi funcţiile pentru neterminalele T şi T’ pentru gramatica anterioară

2. Analizaţi propoziţia “(id)”, reprezentând stările stivei de apeluri.

33

Pentru a putea utiliza analiza sintactică prin coborâre recursivă, gramatica generatoare a limbajului ţintă trebuie să îndeplinească aceleaşi condiţii ca şi pentru analiza sintactică predictivă.

34

Structura maşinii de analiză predictivă

MP

Procesor

SI

ISI

ISO

SO ST

VS IMP

35

Procesorul este unitatea centrală virtuală care interpretează programele

şi le execută.

SI este şirul de intrare cu indicele ISI care marchează poziţia

caracterului curent de analizat.

SO este şirul de ieşire cu indicele ISO care marchează ultimul

caracter introdus sir.

ST este o memorie de tip stivă, cu VS vârful stivei

MP este memoria program, accesibilă doar la citire, cu IMP indicele

instrucţiunii curente.

Procesorul citeste programele din MP şi le executa la fel ca şi

procesorul oricărui calculator real. El poate citi un caracter din SI,

poate scrie un caracter în SO şi poate scrie sau citi din varful stivei ST.

36

MAP recunoaşte şi execută patru instrucţiuni:

1.Instructiunea de test (V)

2.Instructiunea de apel cu revenire (A)

3. Instrucţiunea adevărat (T)

4. Instrucţiunea fals (F)

37

1.Instructiunea de test:

V(a),E1,E2

Instrucţiunea de test face verificarea coincidenţei dintre simbolul curent din

SI şi caracterul indicat între paranteze, adică a.

In caz de identitate se scrie caracterul a în şirul SO, se avanseaza în SI şi se

continuă execuţia cu instrucţiunea E1.

În caz contrar se continuă execuţia cu instrucţiunea E2.

Dacă câmpurile E1 si E2 sunt vide, execuţia se continuă cu următoarea instrucţiune din

MP.

E1 şi E2 pot fi etichete ale unor instrucţiuni din MP, sau pot fi una dintre instrucţiunile T

şi F.

38

2.Instructiunea de apel cu revenire

A(E),E1,E2

Permite executia secvenţei de program de la eticheta E.

Înainte de execuţia primei instrucţiuni de la eticheta E, se salvează starea maşinii de

analiză, adică tripletul (ISI,ISO,IMP) în ST.

Daca returul din secvenţă se face cu instrucţiunea adevarat (T), se va executa în

continuare instructiunea E1.

Dacă returul din secvenţă se face cu instrucţiunea fals (F), se va executa în

continuare instrucţiunea E2.

Dacă câmpurile E1 si E2 sunt vide, execuţia se continuă cu următoarea instrucţiune

din MP.

E1 şi E2 pot fi etichete ale unor instrucţiuni din MP, sau pot fi una dintre

instrucţiunile T şi F.

39

Algoritmul MAP este urmatorul:

ISI, ISO,ISt,IMP0

repeta

daca MP(IMP)=A

atunci *A

altfel *V

40

Instrucţiunea V:

k=1

daca MP(IMP+1)=SI(ISI)

atunci

ISIISI+1

SO(ISO)MP(IMP+1)

ISOISO+1

K1IMP+2

altfel

K1IMP+3

41

Continuare instrucţiunea V:

repeta pana cand k=0

daca MP(K1)=blank

atunci IMP=IMP+4 ; k=0

altfel

daca MP(K1) =T

atunci *T

altfel

daca MP(K1)=F

atunci *F

altfel IMP=MP(K1); k=0

42

Instrucţiunea A :

ST(VS)=ISI,ISO,IMP

VS=VS+3

IMPMP(IMP+1)

Instrucţiunea F :

daca VS=0 atunci *esec

altfel IMP=ST(VS)

ISO=ST(VS)

ISI=ST(VS)

K1=IMP+3

• VS=VS-3

•

43

Instrucţiunea T :

daca VS != 0 atunci

IMP=ST(VS)

VS=VS-3

SO(ISO)=MP(IMP+1)

ISO=ISO+1

K1=IMP+2

altfel (daca VS=0) atunci

daca SI(ISI-1) = ε

atunci *succes

altfel *eşec

• •

44

Ex:

Se consideră gramatica:

X Y

Y Z+W

Y Z*W

Y Z

Z -W

Z W

W a

W (Y)

Scrieţi programul de analiză pentru maşina de analiză predictivă.

Analizaţi propoziţia: a+(-a)

45

+ * - a ( )

X Y Y Y

Y Z+W Z*W Z

Z+W Z*W Z

Z+W Z*W Z

Z -W W W

W a (Y)

46

0 X: A(Y) , , F

4 : V(ε) ,T , F

8 Y: A(Z) , , F

12 : V(+) ,Y1,

16 : V() ,Y1, T

20 Y1: A(W), T , F

24 Z: V(-) , ,

28 : A(W), T , F

32 W: V(a) , T ,

36 : V( ( ), , F

40 : A(Y) , , F

44 : V( ) ), T , F

47

SI ISI ISO IMP SO ST

a+(-a)$ 0 0 0 -

a+(-a)$ 0 0 0 - (0,0,0)

a+(-a)$ 0 0 8 - (0,0,0)(0,0,8)

a+(-a)$ 0 0 24 - (0,0,0)(0,0,8)

a+(-a)$ 0 0 28 - (0,0,0)(0,0,8)(0,0,28)

a+(-a)$ 0 0 32 - (0,0,0)(0,0,8)(0,0,28)

a+(-a)$ 1 2 28 aw (0,0,0)(0,0,8)

a+(-a)$ 1 3 8 awz (0,0,0)

a+(-a)$ 1 3 12 awz (0,0,0)

48

SI ISI ISO IMP SO ST

a+(-a)$ 2 4 20 awz+ (0,0,0)

a+(-a)$ 2 4 32 awz+ (0,0,0)(2,2,20)

a+(-a)$ 2 4 36 awz+ (0,0,0)(2,2,20)

a+(-a)$ 3 5 40 awz+( (0,0,0)(2,2,20)

a+(-a)$ 3 5 8 awz+( (0,0,0)(2,2,20)(3,3,40)

a+(-a)$ 3 5 24 awz+( (0,0,0)(2,2,20)(3,3,40)(3,3,8)

a+(-a)$ 4 6 28 awz+(- (0,0,0)(2,2,20)(3,3,40)(3,3,8)

a+(-a)$ 4 6 32 awz+(-(0,0,0)(2,2,20)(3,3,40)(3,3,8)

(4,4,28)

a+(-a)$ 5 8 28 awz+(-aw (0,0,0)(2,2,20)(3,3,40)(3,3,8)

49

SI ISI ISO IMP SO ST

a+(-a)$ 5 9 8 awz+(-awz (0,0,0)(2,2,20)(3,3,40)

a+(-a)$ 5 9 12 awz+(-awz (0,0,0)(2,2,20)(3,3,40)

a+(-a)$ 5 9 16 awz+(-awz (0,0,0)(2,2,20)(3,3,40)

a+(-a)$ 5 10 40 awz+(-awzy (0,0,0)(2,2,20)

a+(-a)$ 6 11 20 awz+(-awzy) (0,0,0)

a+(-a)$ 6 12 0 awz+(-awzy)w -

a+(-a)$ 6 13 4 awz+(-awzy)wy -

50

Analiza LL(k) este un tip de analiză sintactică descendentă care analizează intrarea de la stânga la dreapta (Left to right) şi construieşte o derivare stânga pentru aceasta (Leftmost derivation). De aici denumirea de LL.

Analiza se numeşte LL(k) deoarece în cadrul acesteia decizia de a folosi o anumită producţie pentru a expanda un neterminal se ia după inspectarea în avans a unui număr de k simboluri (atomi lexicali) din şirul de intrare. În consecinţă, analiza nu foloseşte reveniri (backtracking).

Dacă pentru o anumită gramatică generatoare G se poate defini un analizator LL(k), atunci gramatica se numeşte gramatică LL(k). Limbajul definit printr-o astfel de gramatică se numeşte limbaj LL(k).

Cele mai răspândite sunt gramaticile LL(1): analizatorul trebuie să inspecteze doar următorul simbol (atom lexical) din şirul de intrare pentru a putea lua deciziile de analiză.

51

Fie gramatica: 1.1 S->aSAc 1.2 S-> ε 2.1 A->bA

2.1 A-> ε

aabcc

(q, 0, S)├ (q, 0, aSAc)├ (q, 1, SAc) ├ (q, 1, aSAcAc)

├ (q, 2, SAcAc) ├ (q, 2, AcAc) ├ (q, 2, bAcAc) ├

(q, 3, AcAc) ├ (q, 3, cAc) ├ (q, 4, Ac) ├ (q, 4, c) ├ (q, 5, ε)

a b C

S 1.1 sau 1.2 1.1 sau 1.2 1.1 sau 1.2

A 2.1 sau 2.2 2.1 sau 2.2 2.1 sau 2.2

52

Pentru a putea defini un analizator LL(1) pentru o anumită gramatică generatoare G, aceasta trebuie să fie o gramatică LL(1).

Condiţiile necesare şi suficiente pentru ca o gramatică independentă de context să fie o gramatică LL(1) sunt:

AVN , A 1| 2| 3…| n

1. FIRST+ (i) FIRST+ (j) = ,

i j

2. FOLLOW+ (A) FIRST+ (j) = ,

i pentru care i * ε şi j

53

FIRST+(i )={ a | i * a }

Dacă i * ε, atunci trebuie să ţinem cont de ceea ce urmează după A.

FOLLOW+(A)={ a | S * xAY; aFIRST+ (Y), x *}

În cazul metodei LL1 se analizează în avans un singur atom lexical.

54

În gramaticile LL1 nu este permisă recursivitatea stânga.

Demonstratie:

Presupunem A 1| 2| 3…| n .

Presupunem existenţa recursivităţii stânga.

1 * A atunci A * 1* A * 2

FIRST+ (1) FIRST+ (A) FIRST+ (2)

Daca 2 =ε FIRST+ () FIRST+ (2 ) FIRST+ (1)

FIRST+ () FOLLOW(A)

FIRST+ (1) FOLLOW(A)

Deci, dacă gramatica foloseşte recursivitate stânga pentru definirea producţiilor, ea nu îndeplineşte condiţiile necesare şi suficiente pentru a fi o gramatică LL1 şi deci nici nu poate fi construit pentru ea un analizator LL1.

55

Fie gramatica:

E E + T | T

T T F | F

F a | (E)

Gramatica foloseşte recursivitate stânga; ca urmare, trebuie să o modificăm:

1. E TE1 6. T1 ε

2. E1 +TE1 7. F (E)

3. E1 ε 8. F a

4. T FT1

5. T1 FT1

56

Calculăm mulţimile:

D1 = FIRST+ (TE1) = FIRST+ (F) = { ( , a }

D2 = FIRST+ (+TE1) = { +}

D3 = FOLLOW+ (E1) = FOLLOW+ (E) = { ) }

D4 = FIRST+ (FT1) = FIRST+ (F) = { ( , a }

D5 = FIRST+ (*FT1) = { }

D6 = FOLLOW+ (T1) = FOLLOW+ (T) = FIRST+ (E1) FOLLOW+ (E) D6 = { + } { ) }= { +, ) }

D7 = FIRST+ ( (E) ) = { ( }

D8 = FIRST+ ( a ) = { a }

57

Verificăm condiţiile pentru ca gramatica să fie

o gramatică LL1:

D2 D3 =

D5 D6 =

D7 D8 =

Rezultă că gramatica este o gramatică LL1.

58

Pe baza mulţimilor FIRST şi FOLLOW calculate, se generează tabela de analiză sintactică.

Pe baza tabelei de analiză sintactică se poate implementa un analizor sintactic determinist cu structura:

w x

SI

a

Automat finit

ISO

SO

VS

ISI

59

Pe baza mulţimilor FIRST şi FOLLOW calculate, se generează tabela de analiză sintactică astfel:

Simbolul $ reprezintă terminatorul de şir pentru şirul de intrare (SI).

VN

{ $ }

{ $ }

P - pop – scoate un simbol din stivă şi

înaintează în SI

A - accept – propoziţia este corectă

E - error – propoziţia este incorectă

R n - replace – se înlocuieşte VS cu

partea dreaptă a producţiei n, după care se

scrie n în SO

60

Algoritmul de construcţie al tabelei de analiză sintactică este:

Pentru fiecare regulă Rn: A->α

Instrucţiune repetitivă (actualize linie neterminal A) ◦ Pentru fiecare terminal din FIRST+(α), completează celula

din tabelă corepunzătoare coloanei terminalului cu R n

◦ Dacă α =>* ε, atunci pentru fiecare terminal din FOLLOW+(A), completează celula din tabelă corespunzătoare coloanei terminalului respectiv cu R n

Sfârşit instrucţiune repetitivă

61

Pentru exemplul anterior, tabela de analiză sintactică este (celulele goale reprezintă E):

a ( ) + $

E 1 1

E1 3 2 3

T 4 4

T1 6 6 5 6

F 8 7

a P

( P

) P

+ P

P

$ A

62

Algoritm

sf false

repeta pana cand sf = true

daca St(VS) şi St(VS)=SI(ISI) atunci pop şi ISI = ISI + 1

◦ sau St(VS) şi St(VS) =! SI(ISI) atunci error

◦ sau St(VS)=AVN atunci replace n şi SO(ISO) = n şi

ISO = ISO + 1

◦ sau St(VS) = SI(ISI) = $ atunci accept

◦ sf true

altfel error

sf true

63

Modelul matematic al acestui tip de analiză rămâne automatul finit cu stivă, aşa cum a fost definit pe slide-ul al 9-lea, la care se adaugă un element în plus, şi anume şirul de ieşire.

Funcţia de tranziţie:

f(q, a, a) = {(q, ε)} pop

f(q, $, $) = {(a, ε)} accept

f(q, b, A) = {(q, )} replace A b conform tabelei de analiză sintactică

f(q, i, x) = {(e, ε)} error

64

Configuraţia automatului la un moment dat este dată de: (S, x, , y)

S = starea automatului

x = şirul de intrare rămas de analizat

= stiva

y = şirul de iesire, format din indicii producţiilor utilizate în derivări

Stări posibile:

(q, ax, a , y) (q, x, , y) pop

(q, ax, A, y) (q, x, , yi) replace i, conform tabelei de analiză

(q, $, $, y) (a, ε, ε, y) accept

(q, x, i, y) (e, ε, ε, y) error

65

Ex: a a + a

(q,aa+a$, E$, ε) r (q,aa+a$ ,TE1$ ,1) r

r(q,aa+a$, FT1E1$,14) r (q,aa+a$,aT1E1$,148) p

p(q,a+a$,T1E1$,148) r (q,a+a$ ,FT1E1$,1485) p

p(q,a+a$,FT1E1$,1485) r (q,a+a$,aT1E1$,14858)p

p (q,+a$,aT1E1$,14858)r (q,+a$,E1$,148586) r

r(q,+a$,+TE1$,1485862) p (q,a$,TE1$,1485862) r

r(q,a$,FT1E1$,14858624) r (q,a$,aT1E1$,148586248) p

p(q,$,T1E1$,148586248) r(q,$,E1$,1485862486) r

r (q,$,$,14858624863) a (a,$,$,14858624863)

66

<instructiune > -> if <expr-logica> then (<instructiune >) I1

I1 -> else <instructiune >

I1 -> ε

<instructiune > -> repeat <instructiune > until <expr-logica>

<instructiune > -> <factor> := <factor>

<expr-logica> -> <factor> E1

E1 -> < <factor>

E1 -> <= <factor>

<factor> -> i F1

F1 -> (<lista>)

F1 -> ε

<lista > -> i L1

L1 -> , <lista>

L1 -> ε

67

FIRST+ { if } FIRST+ { else } FOLLOW+ { ) until $} FIRST+ { repeat } FIRST+ { i } FIRST+ { i } FIRST+ { < } FIRST+ { <= } FIRST+ { i } FIRST+ { ( }

FOLLOW+(F1) = FOLLOW+(<factor>) = { := } U First(E1) = {:= < <=} U FOLLOW+(E1) U FOLLOW+(<instructiune>) ◦ (pentru ca factor apare ca ultim element al productiilor I -> F := F, deci fallow de F este

Fallow de I) ◦ E1 -> < F, deci fallow de F este Fallow de E1

{ := < <= then ) until $ } FIRST+ { i } FIRST+ { , } FOLLOW+ { ) }

68

(<instructiune>$, propozitia de intrare)

În calculul mulţimilor FIRST şi FOLLOW se merge în adâncime până la nivelul maxim posibil.

69

Structura maşinii de analiză LL(1) corespunde cu structura maşinii de analiză predictivă.

Setul de instrucţiuni al procesorului acestei maşini este format din:

check(a) L – verifică dacă simbolul curent din şirul de intrare este terminalul a; dacă da, se continuă execuţia cu instrucţiunea de la eticheta L; dacă nu se contiuă execuţia cu instrucţiunea următoare

call A – apel cu revenire la eticheta A return – revenire dintr-un call pop - avansare în şirul de intrare accept – încheiere execuţie program, propoziţia este

corectă error - încheiere execuţie program, propoziţia este

incorectă

70

Ex:

Fie gramatica: E→E+T

E→T

T→TF

T→F

F→a

F→a(L)

F→(E)

L→E

L→E,L

• Să se modifice gramatica astfel încât să se obţină o gramatică LL(1).

• Să se construiască tabela de analiză sintactică LL(1).

• Să se construiască automatul de analiză sintactică LL(1).

• Să se scrie programul pentru maşina abstractă de analiză LL(1) pentru gramatica obţinuită.

71

72

73

74

75

76

77

78

Ex: Fie gramatica:

E E+T | E-T | T

T T*F | T/F | F

F a | a(L) | (E)

L E | E,L

a. Sa se modifice gramatica astfel încât să se obţină o gramatică LL(1).

b. Să se scrie programul maşinii abstracte de analiză predictivă LL(1) pentru gramatica obţinută.

79

http://homedir.jct.ac.il/~rafi/formcomp.pdf

http://inst.eecs.berkeley.edu/~cs164/sp10/notes/notes.pdf

http://facultate.regielive.ro/cursuri/calculatoare/limbaje_formale_si_translatoare-59028.html

80