Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice
Acasa » scoala » matematica
Analiza sintactica

Analiza sintactica


Analiza sintactica

Toate gramaticile cu care vom lucra in acest sunt independente de context; de aceea nu vom mai specifica explicit acest lucru.

Fie G=(VN,VT,S,P) o gramatica (independenta de context).

Analiza sintacticǎ constǎ in urmatoarele:

se dǎ ;

se cere sǎ se determine dacǎ wIL(G) si, in caz afirmativ, sǎ se determine productiile care trebuie aplicate pentru a obtine o derivare stangǎ a lui w din S



Observatie. Daca productiile au numere de ordine, sirul numerelor de ordine ale productiilor ce trebuie aplicate este numit sintaxa stanga a lui w. Ea este importanta, deoarece pe baza ei se poate construi usor arborele de derivare asociat lui w

Vom folosi urmatoarele conventii de notatii:

a,b,c, I VT

A,B,C, I VN

x,y,z,u,v,w,I

a b g I

si se va specifica explicit cand ele sunt incǎlcate.

In continuare considerǎm cǎ in G nu apar neterminale 'nefolositoare', adica:

din orice neterminal deriva un cuvant format numai din terminale (neterminalul este observabil);

pentru orice neterminal exista o derivare din S in care apare acel neterminal (neterminalul este accesibil).

Stim ca pentru orice gramatica independenta de context exista una echivalenta de acelasi tip, in care nu apar neterminale nefolositoare, deci presupunerea facuta nu este restrictiva.

De asemenea, toate derivarile care vor aparea in continuare sunt derivari stangi (stim ca existenta unei derivari este echivalenta cu existenta unei derivari stangi).

In sfarsit, inchiderea tranzitiva si reflexiva a relatiei de derivare T va fi notata tot prin T, pentru a nu incarca scrierea.

Definim doua functii cu care vom lucra in continuare.

j : (VN VT)* P(VT (prin P am notat multimea partilor), data de:

j a

Functia j mai poarta numele FIRST

Caz particular: pentru j a , unde a este prima literǎ din a (dacǎ a l) sau este l (dacǎ a l

Definitia functiei j se poate extinde la multimi de cuvinte din . Pentru definim: j(L)=

Definim functia prin:

Definitie. G este o gramaticǎ LL(1) dacǎ:

adicǎ, dat fiind un cuvant wAa si un terminal a, existǎ cel mult o productie (cu A in membrul stang) care se poate aplica astfel incat in final sǎ se obtinǎ un cuvant format din terminale in care imediat dupǎ w sǎ aparǎ a.

Teoremǎ. G este de tip LL(1) distincte, avem .

Fie

Cum , conform ipotezei, avem: .

Dar

, deci . Contradictie.

T Fie distincte.

Presupunem cǎ .

Dacǎ a I VT avem patru situatii:

deci

w,a cu (nu existǎ neterminale nefolositoare)

T . Contradictie.

2)

adicǎ , deci

cu si

T b g. Contradictie.

3)

Se face la fel ca la 2).

4)

Deci cu cu

T b g Contradictie.

Dacǎ a = l

Atunci avem

si deci w, a cu si , adicǎ .

T b g Contradictie.

l l

Corolar. G este LL(1) , pentru i j; daca .

Traducatorul sintactic

Este asemǎnǎtor unui automat push-down. Are insǎ in plus o bandǎ de iesire si functioneazǎ pe baza unui tabel de analizǎ sintacticǎ conform unui algoritm sintactic.


Dacǎ G este o gramaticǎ LL(1), atunci:

pe banda de intrare apar cuvinte ;

pe banda de iesire apar siruri formate din numerele de ordine ale productiilor din gramaticǎ;

in memoria pushdown apar cuvinte de forma $ cu .

Prin configuratie intelegem un triplet (x, a p unde:

este cuvantul care a mai rǎmas de citit de pe banda de intrare;

a este cuvantul din memoria p.d.;

p este sirul aflat pe banda de iesire.

Configuratia initialǎ este (w, S$, l unde w este cuvantul care trebuie analizat sintactic.

Trecerea de la o configuratie la alta este datǎ de algoritmul sintactic pe baza tabelului de analizǎ sintacticǎ

Tabelul de analizǎ sintacticǎ

Tabelul de analiza sintactica este o functie M definita pe .

Pentru gramaticile de tipul LL(1) vom defini acest tabel conform regulilor:

Fie . Definim pentru . Dacǎ in plus , definim .

SALT

DA

In rest, =NU.

Observatie: Fie . Atunci

Aceastǎ observatie aratǎ, pe baza corolarului precedent, cǎ functia M este bine definitǎ.

M

a

b

l

S

aAS,1

b,2

A

a,3

bSA,4

a

SALT

b

SALT

DA

Exemplu

1)

2)

3)

4)

Algoritmul sintactic

Pentru gramaticile LL(1) definim urmǎtorul algoritm sintactic:

1) | dacǎ , adicǎ

2) | , ceea ce corespunde situatiei SALT

3) Algoritmul se terminǎ dacǎ:

3.1) se ajunge la ; se aplicǎ deci DA

3.2) se ajunge la cu NU.

Exemplu. Pentru gramatica de mai sus:

| |

| (bbab,bSAS$, (bab,SAS$,

| (bab,bAS$, (ab,AS$,

| (ab,aS$, (b,S$,

| (b,b$, l

deci w=abbabIL(G) si sintaxa sa stanga este p

Fie acum un tabel de analizǎ sintacticǎ M oarecare si fie A un algoritm sintactic construit pe baza acestui tabel. Atunci pentru definim


,dacǎ |

nedefinit , in caz contrar

  Definitie. Algoritmul si tabelul sunt corecte dacǎ:

1) |

2) Dacǎ da, .

Definitie. Algoritmul A este corect dacǎ :

1)

Dacǎ A(w) = p atunci p este sintaxa stangǎ a lui w (adicǎ ).

Definitie. Tabelul M este corect dacǎ algoritmul construit pe baza lui este corect.

Remarcǎm cǎ in cazul unui tabel si a unui algoritm corecte, algoritmul se opreste intr-una dintre situatiile:

w I L(G), adicǎ w este "corect sintactic"; in acelasi timp este furnizatǎ sintaxa lui;

w L(G), adicǎ w "nu este corect sintactic"; in aceastǎ situatie va trebui produs un mesaj de eroare.

Teoremǎ. Algoritmul sintactic si tabelul de analizǎ sintacticǎ definite mai sus pentru gramaticile LL(1) sunt corecte

Demonstratia cuprinde doi pasi.

  Aratam mai intai ca din (xy, S$, l (y, a p rezulta :

Demonstratia se face prin inductie dupǎ numǎrul n de schimbǎri de configuratie.

Pentru n = 1

(xy, S$, l (y, a p implicǎ x = l p = i, M(S, j(y)) = (a, i) unde

. Rezultǎ .

  n n+1

n

 
(xy, S$, l (ay, b p (y, a p , unde aI VT . Implicǎ x = x'a.

 

n

 
Conform ipotezei de inductie, din (x'(ay), S$, l (ay, b p ) rezultǎ .

Daca a = l, atunci b = Ag a dg p p'i, . Rezultǎ .

Daca a l , atunci b = aa p p si .

  Mai aratam ca:

| (y, a p y cu j(y) j a , unde a este fie l, fie incepe cu un neterminal.

i

 

  n = 1 : . Fie y cu j(y) j a

x l : (xy, S$, l (xy, xa l pentru cǎ j(xy) j(xay(S))

| (y, a p

2) x = l : (y, S$, l (y, a$, i) pentru cǎ j(y) j a j ay(S))

n n+1

a

 

A

 

x1

 
cu p p'i (am pus in evidenta ultimul pas)


  Din a inceput al lui a rezulta ca a l sau a incepe cu un neterminal.

  Fie y cu j(y) j a . Trebuie | (y, a p

Cf. ipotezei de inductie, pentru z cu j(z) j(Aa , avem : (x, z, S$, l (z, Aa p

Luam z = x2y.

Atunci j(x2y) j(Aa deoarece j(x2y) j(x2a j(Aa pt. ca Aa T x2a a = x2a

 


Deci (x1x2y, S$, l (x2y, Aa p

= x

 

  Mai trebuie (x2y, Aa p (x2y, x2a a p'i) | (y, a p

? dacǎ j(x2y) j(x2a y(A))

dacǎ x2 l, evident

dacǎ x2 = l trebuie j(y) j a y(A)). Dar j(y) j a j a a j a j a j a y(A)) pentru cǎ .

Inlocuind acum y = a l in pasii notati cu , sse obtine rezultatul din enuntul teoremei.

Aplicatie

Consideram urmatoarea gramatica ce genereaza expresiile aritmetice corecte in care apare variabila a, operatiile binare si , precum si cuprinderea intre paranteze.

S S+T

S T

T T*F

T F

F (S)

F a

Este evident ca aceasta gramatica nu este de tipul LL(1). Ea poate fi adusa insa la o gramatica de tipul LL(1), folosind faptul ca ansamblul de productii:

A Aa

A b

este echivalent cu ansamblul de productii:

A bA'

A' aA'

A' l

Obtinem astfel urmatoarea gramatica echivalenta de tipul LL(1):

S TE

E +TE

E l

T FU

U *FU

U l

F (S)

F a

Tabelul de analiza sintactica este urmatorul:

a

l

S

TE,1

TE,1

E

l

+TE,2

l

T

FU,4

FU,4

U

l

l

*FU,5

l

F

a,8

(S),7

a

SALT

SALT

SALT

SALT

SALT

DA

Sa consideram cuvantul w=(a*a) si sa aplicam algoritmul sintactic:

[(a*a),S$,l [(a*a),TE$,1] ├ [(a*a),FUE$,14] ├

[(a*a),(E)UE$,147] ├ [a*a),E)UE$,147] ├

[a*a),TE)UE$,1471] ├ [a*a),FUE)UE$,14714]├

[a*a),aUE)UE$,147148] ├ [*a),UE)UE$,147148]├

[*a),*FUE)UE$,1471485] ├ [a),FUE)UE$,1471485]├

[a),aUE)UE$,14714858] ├ [),UE)UE$,14714858]├

[),E)UE$,147148586] ├ [),)UE$,1471485863] ├

l,UE$,1471485863] ├ l,E$,14714858636] ├

l

Rezulta ca w este corect ( adica wIL(G) ) si sintaxa sa stanga este p , pe baza caruia putem construi arborele de derivare.

Observatie. De fapt am redus problema la determinarea functiilor j si y, sarcina ce nu este deloc facila!





Politica de confidentialitate


creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului

Secvente numerice 1d si 2d in matlab
Coeficientul de corelatie pentru 2 variabile aleatoare
Proprietatile functiilor de autocorelatie
Varianta (fluctuatia) dispersa sau abaterea medie patratica
CONCEPTE PROBABILISTICE DE BAZA ALE SECURITATII SISTEMELOR
Seria de repartitie bidimensionala
NUMERE COMPLEXE SUB FORMA TRIGONOMETRICA
Numere complexe sub forma trigonometrica

Termeni si conditii
Contact
Creeaza si tu