CAPITOLUL I.

LIMBAJE FORMALE

1.1. CONCEPTE DE BAZĂ

Cunoaştem unele limbaje de nivel înalt, cum sunt Pascal, Fortran,

Basic, C şi altele. Ne scriem programele în aceste limbaje iar când citim

un program sau o descriere a unui algoritm scris într-unul din ele, de

obicei, putem spune ce face programul sau algoritmul respectiv (cel puţin

atunci când programul este bine scris şi are o lungime rezonabilă).

Totodată ne dăm seama de erorile din programe sau dintr-o secvenţă de

cod scrisă într-unul din aceste limbaje create de om. Următorul exemplu

de linie de cod din Fortran,

IF (IND.EQ.1) N = N + 1 (1.1)

este corect, în timp ce

IF (IND.EQ.1) N = (1.2)

nu este corect. Surprinzător, nu doar noi, presupuse fiinţe inteligente,

descoperim astfel de greşeli, da chiar şi maşinile (care în esenţă sunt

formate dintr-o colecţie de elemente hardware). Cum se realizează acest

lucru? De fapt, noi introducem programul într-o maşină simbol cu simbol.

Când o expresia de forma (1.1) este prezentată calculatorului se transmite

mai întâi litera I urmată de litera F, simbolul (, şi aşa mai departe. Maşina

acceptă aceste simboluri unul câte unul şi după ce s-au introdus toate,

„ştie” cum să procedeze în continuare. Ea poate determina de asemenea

dacă şirul de simboluri primit este „corect” sau nu. Pentru aceasta,

maşina trebuie să cunoască ce înseamnă „corect” şi să fie în stare să

determine dacă şirul (1.1) este „scris corect”, în timp ce (1.2) nu. În acest

capitol vom discuta mai întâi cum se defineşte un limbaj. Această

definiţie ne va permite să determinăm, în mod automat, dacă un şir de

simboluri aparţine sau nu unui limbaj. O astfel de definire complet

formală şi deterministă nu este posibilă pentru toate limbajele – în

particular, pentru limbaje naturale, cum sunt engleza, franceza şi rusa,

este probabil imposibil. Dar ea pare adecvată pentru limbajele de

calculator – până la urmă calculatoarele funcţionează.

Vom începe cu un alfabet – fiecare limbaj presupune un alfabet.

Alfabetul pentru Fortran se compune din 26 de litere: A, B, ..., X, Y, Z; 10

numere: 0, 1, 2, ..., 9, şi alte simboluri cum ar fi: =, +, /, *, (, (spaţiu).

Alfabetul complet, numit şi mulţime de caractere, poate fi regăsit pe

primele pagini ale oricărui manual dedicat limbajului respectiv.

Definiţia 1.1. Un alfabet este o mulţime nevidă şi finită de

simboluri.

De obicei vom nota alfabetul cu simbolul Σ . Definirea unui limbaj

peste un alfabet dat devine acum simplă.

Definiţia 1.2. Un limbaj L peste un alfabet Σ este o mulţime de

şiruri finite de elemente din Σ .

Elementele uni alfabet Σ se mai numesc şi caractere. Şirurile

dintr-un limbaj L se numesc şi propoziţii din L.

Exemplu 1.1. Fie alfabetul Σ , compus doar din două simboluri: 0

şi 1, { }0,1Σ = . Două exemple de limbaj peste Σ sunt:

a) { }1 0,01,110L = . Acest limbaj conţine doar trei propoziţii: 0, 01 şi

110.

b) 2L = Toate şirurile de 0 şi 1 cu un număr egal de 0-uri şi 1-uri.

Aşadar, 010011 şi 1010 sunt în limbajul 2L , în timp ce 110 şi 010

nu. Evident că limbajul 2L (spre deosebire de 1L ) conţine un număr infinit

de propoziţii.

Pe parcursul acestei lucrări vom folosi deseori şiruri de simboluri.

Fapt pentru care folosim următoarele convenţii de notaţie. Dacă

1 2... nx x xσ = şi 1 2... my y yτ = sunt două şiruri, atunci concatenarea lor, notată

στ , este definită prin 1 2 1 2... ...n mx x x y y yστ = . Aşadar, στ se obţine din σ şi

τ prin alipirea şirurilor σ şi τ (în această ordine). De exemplu, dacă

01011σ = şi 001τ = , atunci 01011001στ = . Se observă că 00101011τσ = ,

deci, în general στ τσ≠ . Dacă x este un caracter, atunci nx este definit

prin ca ...xx x (de n ori). Observăm că 2x xx= , 3y yyy= , etc. Lungimea

unui şir 1 2... mx x xσ = corespunde numărului de caractere din σ . Astfel,

lungimea lui abaaσ = este 4. Convenabilă este introducerea conceptului

de şir vid. Un astfel de şir nu are nici un caracter; lungimea lui este 0. El

va fi notat întotdeauna cu λ şi reciproc, simbolul λ va fi rezervat pentru

un astfel de şir. Dacă σ este un şir oarecare şi λ este şirul vid, atunci

concatenarea lui σ cu λ va fi întotdeauna σ , σλ λσ σ= = . Din acest

motiv, dacă x este un simbol oarecare, definim 0x ca fiind şirul vid λ ,0x λ= . Lungimea şirului vid λ este 0, el fiind singurul şir cu această

lungime.

Definiţia 1.3. Fie Σ o mulţime nevidă. Limbajul tuturor şirurilor

finite de elemente din Σ (inclusiv şirul vid) se notează cu *Σ . Limbajul

tuturor şirurilor nevide de elemente din Σ se notează +Σ .

În general, un limbaj L peste un alfabet Σ nu conţine toate şirurile

posibile de elemente din Σ . Aceasta corespunde faptului că nu orice

secvenţă de simboluri formează un program valid. Ceea ce dorim să

facem în continuare este să descriem o regulă pentru a decide dacă un şir

aparţine unui limbaj sau nu. Un astfel de exemplu putea fi considerat

descrierea limbajului 2L din exemplul 1.1. Aici regula este foarte simplă;

mai mult, dat fiind un şir σ de simboluri de 0 şi 1, este uşor de verificat

dacă propoziţia face parte din limbaj sau nu. Pe de altă parte este greu de

imaginat o regulă atât de simplă pentru un limbaj ceva mai real, cum e

Pascal. Ca urmare, regula trebuie să fie sofisticată şi precisă astfel încât,

dat fiind un program în Pascal (văzut ca un şir lung), ea să determine dacă

este sau nu un program valid: Sunt toate BEGIN-uri închise cu END-uri?

Sunt toate expresiile algebrice bine formate? etc.

O metodă utilă şi generală pentru descrierea de limbaje se bazează

pe gramatici. În general, o gramatică este o mulţime de reguli care, dacă

sunt urmate, vor produce o propoziţie corectă într-un limbaj. O descrierea

detaliată şi exactă a conceptului de gramatică este următoarea:

Definiţia 1.4. O gramatică G se compune din patru obiecte:

1. O mulţime Σ nevidă şi finită numită alfabet. Limbajul generat

de gramatica G se va compune din şiruri de simbolurile din Σ .

Elementele din Σ se numesc terminale şi vor fi notate, în

general, cu litere mici a, b, c, etc.

2. O mulţime nevidă şi finită de simboluri N, fiecare dintre ele

diferit de terminalele din Σ ( N ∩Σ =∅ ). Elementele din N se

numesc neterminale sau variabile; în general se notează cu

litere mari A, B, C, etc.

3. Un element dedicat S din N. Acest neterminal S se numeşte

simbolul de start.

4. O mulţime P de producţii (numite şi reguli de producţie, reguli

de substituire). Ea este formată din reguli de forma

1 2... nA X X X→ ,

unde A este un neterminal şi 1 2... nX X X este un şir finit de

terminale sau neterminale ( iX N∈Σ∪ ).

Gramaticile astfel definite poartă denumirea de gramatici

independente de context; le vom discuta amănunţit mai târziu.

Şirul 1 2... nX X X , din partea a 4-a a definiţie de mai sus, nu trebuie să

conţină nici un simbol, el poate fi un şir vid λ . Producţia corespunzătoare

ar fi atunci de forma A λ→ , şi se numeşte producţie vidă. O gramatică G

cu Σ , N, S şi P, ca în definiţia 1.4., se va nota { }, , ,G N S P= Σ .

Exemplu 1.2. Fie următoarea descriere a unui gramatici

{ }, , ,G N S P= Σ :

1. Mulţimea de terminale Σ (alfabetul) este { }, ,a b c .

2. Mulţimea de neterminale N este { }, , ,S A B C .

3. Simbolul de start este S.

4. Mulţimea P este formată din următoarele producţii:

S AaB→ S B→ A aB→ A a→

B bC→ C ac→ C λ→

În ultima producţie λ este şirul vid şi C λ→ este o producţie vidă.

Gramatica are trei terminale (a, b, c), patru neterminale (S, A, B, C) şi

şapte producţii.

În continuare vom descrie cum generează o gramatică un limbaj.

Avem nevoie de următoarea terminologie:

Definiţia 1.5. Fie { }, , ,G N S P= Σ o gramatică. O formă

propoziţională a lui G este orice şir 1 2... nX X X de simboluri, fiecare iX

fiind un terminal sau neterminal ( iX N∈Σ∪ ).

O formă propoziţională nu trebuie să conţină nici un simbol, ea

poate fi chiar şirul vid λ . În exemplul 1.2. şirurile AaB, AAaCB, aba şi λ

sunt exemple de forme propoziţionale.

Definiţia 1.6. Fie { }, , ,G N S P= Σ o gramatică. Presupunem că σ

este o formă propoziţională exprimata astfel: 1 2Aσ γ γ= unde 1γ şi 2γ sunt

şiruri de terminale sau neterminale (forme propoziţionale) şi A este un

neterminal. Mai presupunem că 1 2... nA X X X→ este o producţie din P. Fie

τ forma propoziţională obţinută din σ prin înlocuirea lui A cu 1 2... nX X X ,

1 1 2 2... nX X Xτ γ γ= . Vom spunem că forma propoziţională τ este imediat

derivabilă din σ folosind producţia 1 2... nA X X X→ . Folosim următoarea

notaţie:

σ τ⇒

Fie gramatica { }, , ,G N S P= Σ din exemplul 1.2. Forma

propoziţională aBabCσ = derivă imediat forma propoziţională abCabCτ =

folosind producţia B bC→ :

aBabC abCabCσ = ⇒

Cu alte cuvinte, a spune că σ τ⇒ înseamnă că unul dintre neterminalele

din σ poate fi înlocuit cu partea dreaptă a producţie şi devine şirul τ . În

forma propoziţională aBabCσ = am înlocuit B cu bC ( B bC→ fiind o

producţie) şi am obţinut abCabCτ = . Ca alt exemplu, fie aaCbaσ = .

Aplicând la σ producţia C λ→ obţinem

aaCba aabaσ = ⇒

Aici am substituit C cu partea dreaptă a producţiei C λ→ (şirul vid). Şirul

λ , fiind şirul vid, nu are simboluri, deci aa ba aabaλ = , astfel simbolul C

„dispare”.

Definiţia 1.7. Fie 1σ şi 2σ două forme propoziţionale ale unei

gramatici G. Presupunem că există o secvenţă de forme propoziţionale

1 2, ,..., nτ τ τ astfel încât

1 1 2 2... nσ τ τ τ σ⇒ ⇒ ⇒ ⇒ ⇒ .

Vom spunem atunci că 1σ derivă 2σ , sau 2σ este derivabilă din 1σ şi

notăm

1 2*σ σ⇒

În exemplul 1.2. avem *S aabC⇒ deoarece

S AaB aaB aabC

S AaB A a B bC

⇒ ⇒ ⇒

↑ ↑ ↑→ → →

Sub fiecare simbol ⇒ am indicat producţia corespunzătoare

folosită din G la derivare.

Fiind dată gramatica { }, , ,G N S P= Σ , limbajul L(G) generat de G

este mulţimea tuturor şirurilor de terminale derivabile din simbolul de

start. Formal avem:

Definiţia 1.8. Fie { }, , ,G N S P= Σ o gramatică. Limbajul L(G)

generat de G este definit a fi mulţimea de şiruri

{ }*( ) | , *L G Sσ σ σ= ∈Σ ⇒ .

Elementele (şirurile) din L(G) se numesc propoziţii din L(G).

În exemplul 1.2. şirurile b, aabac şi bac aparţin toate lui L(G):

S B bC bS AaB aaB aabC aabacS B bC bac

⇒ ⇒ ⇒⇒ ⇒ ⇒ ⇒⇒ ⇒ ⇒

Observăm că şirul cb nu este în limbajul L(G). Într-adevăr,

începând cu simbolul de start S, prima formă propoziţională derivată din

S va fi AaB sau B. Nici una dintre aceste două propoziţii va deriva într-o

propoziţie care începe cu c.

Exemplu 1.3. Gramatica din acest exemplu va da limbajul tuturor

expresiilor algebrice corect formate care pot fi obţinute folosind

simbolurile a, +, *, (, şi ). Astfel, expresia ( )*a a a+ va fi în limbaj, în

timp ce ( )*(a a a+ + nu. Această gramatică o notatăm 0G şi o vom întâlni

des pe parcursul acestei lucrări. Alfabetul din 0G este { }, ,*, (, )aΣ = + ,

mulţimea de neterminale { }, ,N E T F= şi simbolul de start este E.

Producţiile din 0G sunt:

1.2.3. *4.5. ( )6.

E E TE TT T FT FF EF a

→ +→→→→→

Expresia ( )*a a a+ face parte din limbajul 0( )L G , derivarea sa fiind

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 a T F

a F F a a F a a a

⇒ ⇒ ⇒ ⇒ ⇒ +

⇒ + ⇒ + ⇒ +

⇒ + ⇒ + ⇒ +

Numărul deasupra simbolului ⇒ indică producţia folosită la fiecare

derivare. Pentru a vedea că şirul ( )*(a a a+ + nu este în 0( )L G , observăm

că singura posibilitate de apariţie a simbolurilor ) şi ( într-o formă

propoziţională este prin aplicarea producţiei ( )F E→ . De aici, orice şir

derivat din E va avea acelaşi număr de ) ca şi (, iar şirul cu pricina nu are

această proprietate. Literele E, T şi F, care formează mulţimea

neterminalelor, sunt mnemonice pentru expresie, termen şi factor.

Există o serie de convenţii folosite la descrierea de gramatici. În

lipsa unei alte specificaţii, terminalele alfabetului Σ vor fi notate cu litere

mici a, b, c, etc., cu numere 0, 1, 2, ..., 9 sau cu simboluri specifice ca +,

*, (, ). Neterminalele sunt notate cu litere mari A, B, C, ..., şi simbolul de

start cu S. Şirul vid se notează întotdeauna cu λ . Prima producţie va avea

simbolul de start pe partea stângă. Elementele mulţimii NΣ∪ se vor

numi simboluri gramatice; deci un simbol gramatic este sau terminal sau

neterminal. Dacă

1

2

k

AA

A

αα

α

→→

→M

sunt toate producţiile cu aceeaşi parte stângă A, atunci, pentru a se salva

spaţiu, ele vor fi scrise sub următoare formă

1 2 1| | | |k kA α α α α−→ L .

Ca urmare, gramatica din exemplul 1.2. se va scrie

||

|

S AaB BA a aBB bCC ac λ

→→→→

iar gramatica 0G din exemplul 1.3.

|* |

( ) |

E E T TT T F FF E a

→ +→→

Înţelesul simbolurilor reiasă din context. Dacă nu se specifică în

mod explicit, fiind dată descrierea unei gramatici prin

| |10 1| 0 |

S ABA BSB BBB A λ

→→→

tragem concluzia că mulţimea de terminale Σ este { }0,1 , mulţimea de

neterminale { }, ,N S A B= şi producţiile sunt

10 10

S ABA BSBA BBAB ABB λ

→→→→→→→

Forma această o vom folosi des pentru descrierea gramaticilor.

Derivarea unei propoziţii într-un limbaj generat de o gramatică se

poate reprezentat grafic printr-un arbore de derivare. Ca exemplu

considerăm gramatica G:

|S aBa B Sb bCC C abb→ → →

şi o derivare a propoziţiei aababbabbaba:

S aBa aSba aaBaba aabCCabaaababbCaba aababbabbaba

⇒ ⇒ ⇒ ⇒⇒ ⇒

O derivarea reprezentată schematic printr-un graf, se numeşte arbore de

derivare, figura 1.1.

Obiectele rotunde din graf se numesc noduri. Nodul din vârf, S, se

numeşte rădăcina arborelui. Dacă un nod X este legat de un nod de pe un

nivel mai jos, atunci X se numeşte părintele lui Y şi Y se numeşte fiul lui

X. Nodurile care nu au fii se numesc frunze, nodurile cu fiu/fii şi părinte

se numesc noduri interne. Formarea grafului, numit arbore de derivare,

este evidentă. Dacă A este un neterminal, care se înlocuieşte cu partea

dreaptă a producţiei 1 2 nA X X X→ L , atunci nodul A are ca fii 1 2, ,..., nX X X

(de la stânga la dreapta). Rădăcina arborelui este nodul S, unde S este

simbolul de start a gramatici iar frunzele sunt noduri de forma x, unde

x∈Σ sunt terminale. Dat fiind un arbore de derivare a unui şir, vom

obţine acest şir prin concatenarea frunzelor arborelui de la stânga la

dreapta.

Figura 1.1. Un arbore de derivare a unui şir.

Propoziţia ( )*a a a+ în limbajul 2( )L G din exemplul 1.3., are arborele de

derivare din figura 1.3.

Exemplu 1.4. Ca un alt exemplu, prezentăm o gramatică pentru

limbajul tuturor constante reale valide din Fortran. În manualul de

Fortran, aceste constante sunt descrise în diferite moduri. Printre care „o

constantă reală este reprezentată printr-un şir de numere; conţine un punct

zecimal şi un exponent reprezentând o putere a lui 10 sau amândouă.

Constante reale pot fi în următoarele formate:

. ., . , . , . , . ,n n n n n nE s n E s nE s nE s± ± ± ± .

Figura 1.3. Arborele de derivare pentru ( )*a a a+

Figura 1.2. Formarea unui arbore de derivarea

Exemple sunt: 3.E1, 3.1415768, 31.41592E-01, 314.0749162, .31415E01,

-3.141592E+279, .31415E+01”. Un exemplu de gramatică care generează

un astfel de limbaj este:

|. | . | . |

| ||

0 |1| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

S ABA XDB EXID I I I I IXI M MIM

λ

λ

→→→→→+ −→→

Terminalele formează mulţimea { }0,1, 2, 3, 4, 5, 6, 7, 8, 9, , , , .EΣ = + − ,

mulţimea de neterminale este { }, , , , , ,N S A B D I M X= şi simbolul de start

este S. Arborele de derivare pentru -3.14E01 este dat în figura 1.4.

Evident, că toate constantele Fortran (şi numai acestea) pot fi derivate

folosind această gramatică.

Bineînţeles că aceasta nu este unica gramatică care poate fi folosită

pentru descrierea acestui limbaj; este posibil să avem două gramatici

distincte 1G şi 2G astfel încât 1 2( ) ( )L G L G= . Vom discuta acest concept

mai târziu. De fapt, întregul limbaj Pascal, ca şi oricare alt limbaj de

calculator, poate fi descris prin gramatica lui. Aceste gramatici sunt lungi

şi includ mai multe sute de producţii. Metodă aceasta de descriere a

limbajului de calculator este numită Backus Normal Form sau BNF.

Notaţia folosită aici diferă puţin de notaţia introdusă mai sus. Săgeata →

este reprezentată prin simbolul ::= şi neterminalele sunt scrise ca fraze

auto explicative închise între < >L . De pildă, o descriere BNF a

constantelor întregi din Fortran (sau oricare alt limbaj) poate fi:

:::: | |

:: |:: 0 |1| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

IntegerConstant Sign NumberSignNumber Digit Digit NumberDigit

λ< > = < > < >< > = + −< > = < > < > < >< > =

Evident, că această formă de descriere a gramaticilor (şi a limbajelor), în

afara convenţiilor de notaţie, este identică cu aceea prezentată anterior.

1.2. TIPURI DE GRAMATICI ŞI CLASIFICAREA LOR

Ideea descrierii unui limbaj printr-o gramatică aparţine lui N.

Chomsky. În prima parte a activităţii sale interesul lui s-a îndreptat spre

limbaje naturale, ca engleza şi germana. Vom prezenta în continuare

unele definiţii generale de gramatici.

I. Gramatici de tip 0 sau gramatici fără restricţii. O gramatică fără

restricţii G se compune din patru obiecte: o mulţime nevidă de terminale

Σ , o mulţime nevidă, N, de neterminale, cu N ∩Σ =∅ , un simbol de start

Figura 1.4. Arbore de derivare pentru -3.14E01

S N∈ şi un ansamblu finit de producţii P. Într-o gramatică fără restricţii

producţiile sunt de forma

u v→

unde u şi v sunt şiruri oarecare de terminale sau neterminale; u λ≠ .

Această producţie permite înlocuirea arbitrară a unui şir (u) cu un şir (v).

Se spune, că o forma propoziţională σ derivă imediat o formă

propoziţională τ dacă uσ α β= , vτ α β= şi u v→ este o producţie a

gramaticii. Vom nota aceasta prin σ τ⇒ . Limbajul ( )L G este definit a fi

mulţimea şirurilor de terminale derivabil din simbolul de start S.

Exemplu 1.5. Fie { }, ,a b cΣ = alfabetul unei gramatici G,

{ }, ,N S X Y= mulţimea neterminalelor, S simbolul de start şi mulţimea

producţiilor dată de

1.2.3.4.5.

S aXYcaX cadXc aXaXYc XccYc λ

→→→→

→

Un exemplu de derivare în această gramatică ar fi

S aXYc cadYc cad⇒ ⇒ ⇒

sau

S aXYc aXcc aaXac acadac⇒ ⇒ ⇒ ⇒ .

În formele propoziţionale de mai sus am subliniat partea stângă a

producţiilor folosite. Gramaticile de acest tip sunt foarte generale; orice

limbaj (mulţime de şiruri) poate fi descris de o gramatică de tip 0. Un

limbaj generat de o gramatică de tip 0 se numeşte limbaj de tip 0.

II. Gramatici de tip 1, sau gramatici dependente de context.

Terminalele, neterminalele şi simbolul de start sunt aceleaşi. Fiecare

producţie va avea acum forma

Aα β ασβ→

unde A este un neterminal şi σ λ≠ este un şir oarecare de terminale sau

neterminale. Neterminalul A se înlocuieşte cu σ doar dacă A este

înconjurat, sau în context, de α şi β . Evident că gramaticile dependente

de context sunt şi de tip 0, dar reciproc nu.

III. Gramatici de tip 2 sau gramatici independente de context. Dacă

toate producţiile unei gramatici sunt de forma A σ→ , unde A este un

singur neterminal şi σ un şir oarecare de terminale sau neterminale,

atunci gramatica se numeşte gramatică independentă de context, notată

GIC. Gramatici de tip 2 sunt o restricţie a gramaticilor de tip 1: este

necesar ca α β λ= = . Astfel, dată fiind forma propoziţională 1 2Aγ γ şi o

producţie A σ→ , înlocuim A cu σ pentru a deriva o formă 1 2γ σγ

indiferent de contextul 1γ şi 2γ . Acest fapt explică denumirea de

„independent de context”. Obţinem exact definiţia unei gramatici dată de

definiţia 1.4. Strict văzut, gramatici de tip 2 nu sunt chiar restricţii ale

gramaticilor de tip1, deoarece sunt permise producţii de forma A λ→ în

una dar nu şi în cealaltă. Acesta ne conduce la un caz special. Vom arăta

într-un capitolul 7, că dată fiind o gramatică independentă de context cu

producţii vide, există o gramatică independentă de context echivalentă

(generând acelaşi limbaj) fără producţii vide, exceptând S λ→ (unde S

este simbolul de strat). În particular, dacă G este o gramatică

independentă de context astfel încât ( )L Gλ∉ – limbajul generat de G –

atunci ( ) ( ')L G L G= , unde 'G este o gramatică independentă de context

fără producţii vide. Astfel, dacă L este un limbaj de tip2 care nu-l conţine

pe λ , atunci este şi de tip 1. Reciproca nu este adevărată: există limbaje

de tip1 care n-au gramatici independente de context. Majoritatea

gramaticilor discutate în această lucrare vor fi independente de context –

ele sunt mult mai uşor de analizat. Toate limbajele actuale de programare,

Pascal, C, etc., sunt independente de context.

IV. Gramatici de tip 3 sau gramatici regulare. Există o subclasă

interesantă de gramatici independente de context, numite gramatici

regulare sau liniare.

Definiţia 1.9. Spunem că o gramatică G este liniară la dreapta sau

regulară la dreapta, dacă fiecare din producţiile sale are una din formele

următoare:

S A aB A aλ→ → → .

Unde, S este simbolul de start, λ şirul vid, A, B neterminale arbitrare şi a

un terminal oarecare. O gramatică se numeşte liniară la stânga sau

regulară la stânga dacă toate producţiile sale au una din formele

următoare:

S A Ba A aλ→ → →

O gramatică se numeşte regulară (liniară) dacă este regulă (liniară) la

dreaptă sau la stânga.

Evident, gramaticile regulare sunt independente de context. Le vom

studia detaliat în capitolul 2. Această clasificarea a gramaticilor (tip j, j=0,

1, 2, 3) este cunoscută sub denumirea de ierarhie Chomsky.

1.3. REPREZENTAREA LIMBAJELOR PRIN GRAMATICI

Am văzut în paragrafele 1.2. şi 1.3. cum se descrie un limbaj în

termeni de gramatici. Din punct de vedere a ştiinţei calculatoarelor

următoarele două probleme „inverse” sunt mai importante (şi dificile).

I. Fiind dat un şir σ de terminale, aparţine el limbajului?

II. Fiind dat un şir σ dintr-un limbaj, cum a fost derivat?

Importanţa problemei I este evidentă – fiind dat un program scris într-un

limbaj oarecare dorim să determinăm dacă este scris corect. Nu punem

întrebarea dacă programul face ceea ce ar trebui să facă, ci doar dacă este

valid sau nu. Ceea ce dorim să aflăm la acest punct este dacă programul

este „gramatical corect”. Sunt toate instrucţiunile în forma potrivită? Sunt

toate ciclurile DO închise? Se termină toate BEGIN-urle cu END-ul

corespunzător? ş.a.m.d. Examinarea acestui tip de întrebare este

cunoscută sub denumirea de analiză lexicală. Problema II este chiar mai

importantă, ea permiţându-ne să interpretăm „înţelesul” programului şi să

decidem cum va fi executat. Studierea acestei a doua probleme se

numeşte analiză sintactică (eng. parsing). Vom ilustra aceste două puncte

de vedere în următorul exemplu.

Exemplu 1.6. Fie 0G gramatica tuturor expresiilor aritmetice

corecte scrise formate din întregi pozitivi şi simbolurile +, *, (, şi ).

Această gramatică are producţiile

1. E E T→ + 3. *T T F→ 5. ( )F E→

2. E T→ 4. T F→ 6. F a→

Simbolul a reprezintă un şir oarecare de întregi pozitivi. Fiind dat o

propoziţie în limbajul 0( )L G , (5 3)*4+ , avem să decidem:

I. Este o propoziţie validă?

II. Ce înseamnă propoziţia?

În II este implicată interpretarea sau evaluarea şirului (5 3)*4+ .

Când acest şir va fi introdus, maşina ar trebui să ştie să ia numerele 5 şi

3, să le încarce în memorie sau în registre, să execute adunarea, să ia

rezultatul adunării şi să-l încarce în locaţia potrivită, iar apoi să încarce

numărul 4 şi să execute înmulţirea finală. Toate acestea se producă

complet automat; maşina fiind programată astfel încât, când primeşte

şirul (5 3)*4+ , toate operaţiile anterioare să se realizează în ordinea

corectă. Vom arăta în continuare că dacă maşina este capabilă să

reproducă arborele de derivare a propoziţiei, ea poate intui cum să

realizeze cele de mai sus, de exemplu, poate descifra „înţelesul” sau

valoare expresiei.

Într-adevăr, presupunând că avem arborele de derivare pentru

(5 3)*4+ , ca în figura 1.5., a verifica dacă şirul aparţine limbajului este

simplu: concatenăm frunzele arborelui de la stânga la dreapta şi verificăm

dacă şirul obţinut se potriveşte, simbol cu simbol, celui iniţial. Nu vom

discuta cum se memorează un astfel de arbore, cum se accesează

nodurile, etc. Acestea ţin de implementare şi, în particular, pot depinde de

aspecte hardware ale maşinii. Pretindem că, dat fiind acest arbore de

derivare putem determina înţelesul şirului.

Vom rescrie arborele într-un mod diferit. Fiecare nod va fi

reprezentat printr-o celulă |X n : Simbolul X va fi simbolul gramatic al

nodului, (terminal, neterminal) iar n specifică numărul producţiei folosite

în obţinerea fiilor nodului.

Figura 1.5. Arbore de derivare pentru (5 3)*4+ .

Dacă X este un terminal, de exemplu când nodul este frunză, punem 0n = .

Arborele de derivare pentru (5 3)*4+ va arăta atunci ca în figura 1.6. Se

defineşte o funcţie ( ) ( )| ,V X n V X n= pe noduri în felul următor:

0( ( , )) ( ( , )) 1

( , ) ( ( , ) 2, 4, 6( ( , ))* ( ( , )) 3( ( , ) 5

X if nV LeftChild X n V RightChild X n if n

V X n V Child X n if n sauV LeftChild X n V RightChild X n if nV MiddleChild X n if n

= + == = =

=

E 2

T 3

* 0T 4

F 5

E 1

+ 0

F 6

4 0

) 0

T 4

F 6

3 0

( 0

E 2

T 4

F 6

5 0

Figura 1.6. Derivarea lui (5 3)*4+ .

Funcţia ( , )V X n este deci definită pentru acei X şi n pentru care |X n

poate fi nod într-un arbore de derivare a unei expresii aritmetice.

Definiţiile funcţiilor LeftChild, RightChild, MiddleChild şi Child se

subînţeleg. Dat fiind arborele de derivare a unei expresii, pentru aflarea

înţelesului sau valorii acesteia, se evaluează V(Root). În exemplul

discutat, vom avea:

( ) ( , 2)( ,3)( , 4)* ( ,6)( ,5)* (4,0)( ,1)*4

( ( , 2) ( , 4))*4( ( , 4) ( ,6))*4( ( ,6) (3,0))*4( (5,0) 3)*4( (5,0) 3)*4(5 3)*4 32

V Root V EV TV T V FV F VV EV E V TV T V FV F VVV

====== += += += += += + =

Evident, funcţia V va calcula corect valoarea oricărei expresii aritmetice

valide, dacă cunoaşte arborele de derivare a expresiei. Funcţia V este

recursivă, ea se va autoapela la evaluarea unor argumente. S-ar putea ca

să nu fie clar cititorului cum se implementează, în mod complet automat,

pe calculator evaluarea unei astfel de funcţii. Acest lucru, însă, poate fi

realizat, iar implementarea specifică va depinde, la rândul ei, de limbajul

şi de hardware-ul folosi. Nu intrăm în amănuntele acestui subiect. Mai

degrabă vom studia procesului de reconstruire a arborelui de derivare

pentru un şir dat. Motivul introducerii funcţiei V a fost, de a convinge

cititorul că procesul de reconstruire a arborelui de derivare este într-

adevăr folositor şi chiar necesar.

Următoarea problemă se ridică imediat ce discutăm de parsing (de

exemplu despre reconstruirea arborelui de derivare): Fiind dată o

gramatică G şi un şir σ din limbajul ( )L G , atunci poate avea σ doi arbori

distincţi de derivare? Se constată, desigur, că astfel de fenomene exista.

Exemplu 1.7. Fie G gramatica

S A→ 0 |1A A A→

Figura 1.7. arată doi arbori de derivare distincţi pentru şirul 10101σ = .

Aceasta ne conduce la următorul concept:

Definiţia 1.10. O gramatică G se numeşte ambiguă dacă există o

propoziţie σ în ( )L G cu doi arbori de derivare distincţi. Dacă o gramatică

nu este ambiguă, ea se numeşte neambiguă.

Exemplu 1.8. Următorul este un exemplu concret relativ la

construcţia „ 1 2 3if C then C else C ” din Pascal sau din alt limbaj de

Figura 1.7. Arbori de derivare distincţi pentru şirul 10101σ = .

programare. Un fragment a unei gramatici pentru Pascal care foloseşte

această construcţie poate fi dat în felul următor:

||

statement if condition then statementif condition then statement else statement

other kind of statement

< >→ < > < >< > < > < >

< >(1.3)

Dacă aceste construcţii sunt descrise de gramatica de mai sus, atunci

arborele de derivare a unor propoziţii nu va fi unic. Considerăm

următoarea propoziţie:

0 1 : 3 : 4if C then if D then A else A= = = = (1.4)

Ea are doi arbori de derivare distincţi, ca în figura 1.8. „Înţelesul” sau

„valoarea” lui σ , diferă pentru fiecare dintre cei doi arbori. Presupunând

că în timpul execuţiei, variabila C are valoarea 1, D=1, A=5 şi se

întâlneşte propoziţia σ . Dacă se admite ca arborele de derivare să fie dat

de figura 1.8.(a), valoarea 5A = rămâne. Dacă, pe de altă parte, se

consideră arborele din figura 1.8.(b) ca fiind cel corect, valoarea lui A

devine 4. Astfel, la compilarea programelor derivate de la o gramatică

ambiguă, trebuie luată o decizie arbitrară şi anume, care dintre arborii de

derivare se va folosi, adică, ce înţeles se atribuie propoziţiei. În acest

exemplu, este preluat înţelesul dat de arborele din figura 1.8.(a). Regula

arbitrar aleasă, însă fixată, este: „Fiecare else se asociază cu cel mai

apropiat then precedent”.

Figura 1.8. Ambiguitate pentru if...then...else.

Observăm că, gramaticile neambigue sunt preferabile celor ambigue. În

general, fiind dată o gramatică G, nu există un algoritm pentru a

determina dacă ea este ambigua sau nu. Unele gramatici speciale permit

însă acest lucru – în capitolul 8 vom arăta că gramatica expresiilor

aritmetice, 0G , este neambiguă.

Se poate întâmpla, ca pentru o gramatică dată G, care generează un limbaj

( )L G , să existe o altă gramatică diferită care generează acelaşi limbaj,

adică, ( ') ( )L G L G= . Următorul exemplu arată acest fenomen.

Exemplu 1.9. Fie gramatica G

0 0|

S AA S λ→→

if C = 0 then <statement>

if D = 1 then A := 3

<statement>(b)

else A := 4

if C = 0 then <statement>

if D = 1 then A := 3 else A := 4

<statement>(a)

şi gramatica 'G

00 | 0

S BB S→→

Este evident că ambele gramatici generează acelaşi limbaj L – mulţimea

tuturor şirurilor având un număr par de zerouri. Gramaticile la rândul lor,

sunt total diferite: 'G este o gramatică regulară fără producţii vide, iar G

nu are nici una din aceste proprietăţi.

Se poate da o gramatică ambiguă G şi să existe o altă gramatică 'G

astfel încât ( ) ( ')L G L G= . Rescriem gramatica pentru if...then...else din

exemplul 1.8. în felul următor:

1 2

1 1

2 1

2 2 2

||

|

|

statement S S other kind of sentenceS if condition then S

if condition then S else Sother kind of sentence

S if condition then S else Sother kind of sentence

< >→ < >→ < >

< >< >

→ < >< >

(1.5)

Această gramatică generează aceeaşi propoziţie ca gramatica din

exemplul 1.8., dar ambiguitatea a fost înlăturată. Aşadar, dacă propoziţia

0 1 : 3 : 4if C then if D then A else A= = = =

este analizată sintactic, înţelesul ei se interpretează ca

0 ( 1 : 3 : 4)if C then if D then A else A= = = =

opus lui

0 ( 1 : 3) : 4if C then if D then A else A= = = =

Definiţia 1.11. Un limbaj se numeşte ambiguu în mod inerent dacă

orice gramatică care generează L este ambiguă.

Un exemplu de astfel de limbaj este

{ }| , , şi 1, cu ( 1şi ) sau ( şi )k k m nL a b c d k l m n k m n k n l m= ≥ = = = = .

Şiruri din L sunt aabbcccddd ( 2, 3)k l m n= = = = şi aabbbcccdd

( 2, 3)k n l m= = = = . A demonstra că acesta este un limbaj ambiguu în mod

inerent, nu face parte din scopul acestei lucrări.

1.4. O INTRODUCERE ÎN PARSING (ANALIZA SINTACTICĂ)

Considerăm problema reconstruirii arborelui de derivare pentru o

propoziţie dată, adică, problema analizei sintactice. Întreaga lucrare se va

concentra asupra acestei probleme, actualul paragraf fiind doar partea de

introducere. Am putea crede că pentru specificarea arborelui de derivare

este de ajuns folosirea secvenţei de producţii de la derivare. Urmând

această idee, în lipsa unor restricţii, vor apărea dificultăţi. În primul rând,

două secvenţe diferite de producţii pot conduce la acelaşi arbore. De

exemplu, fie gramatica expresiilor aritmetice 0G

1. E E T→ + 3. *T T F→ 5. ( )F E→

2. E T→ 4. T F→ 6. F a→

şi şirul a a+ din acest limbaj. Secvenţele 1, 2, 4, 6, 4, 6 şi 1, 4, 6, 2, 4, 6

sunt diferite şi corespund la două derivări pentru a a+ .

1 2 4 6 4 6E E T T T T F T a F a a a⇒ + ⇒ + ⇒ + ⇒ + ⇒ + ⇒ +

şi

1 4 6 2 4 6E E T E F E a T a F a a a⇒ + ⇒ + ⇒ + ⇒ + ⇒ + ⇒ +

Ambele derivări generează acelaşi arbore din figura 1.9.

Poate avea loc şi situaţia inversă: dacă nu specificăm la fiecare pas care

neterminal este înlocuit, aceeaşi secvenţă de producţii poate conduce la

arbori de derivare distincţi. Pentru a vedea asta considerăm gramatica

1.2. 03. 1

S AA A AA

→→→

Secvenţa de producţii 1, 2, 2, 3, 3, 3 conduce la două derivări distincte:

Figura 1.9. Arbor de derivare pentru a a+ .

1 2 2 3 3 30 0 0 10 0 1010 10101S A A A A A A A A A⇒ ⇒ ⇒ ⇒ ⇒ ⇒

şi

1 2 2 3 3 30 0 0 0 01 0101 10101S A A A A A A A A A⇒ ⇒ ⇒ ⇒ ⇒ ⇒

(În fiecare formă propoziţională este subliniat neterminalul care va fi

înlocuit.) Arborii de derivare a acelor două derivări, apar în figura 1.10.,

ei sunt diferiţi.

Aşadar, pentru a specifica arborele de derivare prin secvenţele de

producţii folosite, este totodată necesară şi specificarea, la fiecare pas, a

neterminalului înlocuit. Aceasta este greu de realizat şi se observă că nu

este necesar deoarece putem specifica dinainte care neterminal va fi ales

pentru înlocuire.

Figura 1.10. Gramatici ambigue.

Definiţia 1.12. Fie G o gramatică, σ o propoziţie în limbajul ( )L G

şi

1 2 ... nS σ σ σ σ⇒ ⇒ ⇒ ⇒ = (1.6)

derivarea lui σ . Spunem că (1.6) este derivarea la stânga a lui σ , dacă la

fiecare pas 1i iσ σ +⇒ , neterminalul înlocuit din iσ , este cel mai din stânga.

Spunem că (1.6) este derivarea la dreapta dacă la fiecare pas înlocuim

neterminalul cel mai din dreapta.

De exemplu, derivarea la stânga a lui ( )*a a a+ în 0G (gramatica

expresiilor aritmetice din exemplul 1.3.) este

1 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 a T F a F F

a a F a a a

⇒ ⇒ ⇒ ⇒ ⇒ + ⇒

+ + ⇒ + ⇒ + ⇒ + ⇒

+ ⇒ +

Derivarea la dreapta a aceleiaşi propoziţii este atunci

2 3 6 4 5 1

4 4 6 4

1

* * * ( )*

( )* ( )* ( )* ( )*

( )* ( )*

E T T F T a F a E a

E T a E F a E a a T a a

F a a a a a

⇒ ⇒ ⇒ ⇒ ⇒ ⇒

+ ⇒ + ⇒ + ⇒ + ⇒

+ ⇒ +

Astfel, dacă ştim de dinainte ce fel de derivare se foloseşte (la stânga sau

la dreapta), secvenţa de producţii din derivarea unei propoziţii va descrie

complet arborul de derivare.

Definiţia 1.13. O analiză la stânga a unui şirσ este secvenţa de

producţii folosită în derivare la stânga a lui σ . O analiză la dreapta a lui

σ este inversa secvenţei de producţii folosite în derivarea la stânga a lui

σ .

Motivul folosirii „inversei” din definiţia analizei la dreapta va fi, pe

scurt, discutată în această parte şi detaliat în capitolul 8. Astfel, analiza la

stânga pentru ( )*a a a+ este: 2, 3, 4, 5, 1, 2, 4, 6, 4, 6, 6. Analiza la

dreapta a aceluiaşi şir va fi: 6, 4, 2, 6, 4, 1, 5, 4, 6, 3, 2. Putem vorbi de o

analiză la stânga şi la dreapta a oricărei forme propoziţionale derivate din

simbolul de start S. De exemplu, analiza la stânga pentru *( )a E în

gramatica 0G este 2, 3, 4, 6, 5, deoarece

2 3 4 6 5* * * *( )E T T F F F a F a E⇒ ⇒ ⇒ ⇒ ⇒

Toate acestea nu ne dau o metode de determinare a analizei (la

stânga sau la dreapta) a unui şir. Fiind dat un şir de terminale 1 2... na a aσ = ,

singurul lucru pe care-l ştim despre arborele lui de derivare este, că are

simbolul S în vârf iar frunzele din partea de jos formează şirul 1 2... na a a :

Figura 1.11. Arborul de derivare pentru 1 2... na a a .

Există două posibilităţi de a popula interiorul arborelui: una este de a-l

reconstrui de sus în jos (eng. top-down) iar cealaltă de jos în sus (eng.

bottom-up).

În schema de analiză top-down, pornim cu neterminalul S şi

încercăm să descoperim prima producţie 1S σ→ care garantează o

derivarea a lui 1 2... na a a de forma

1 1 2... nS a a aσ⇒ ⇒L .

Odată ce a fost determinată, avem de examinat şirul 1σ şi de descoperit

care din neterminalele sale, fie acesta A, trebuie înlocuit cu partea dreaptă

a producţiei A α→ , producând astfel forma propoziţională 2σ în

derivarea

1 2 1 2... nS a a aσ σ⇒ ⇒ ⇒L .

Procedura se repetă până când întreaga derivare este reconstruită. Dacă ne

limităm la derivarea la stânga, de exemplu, la fiecare pas vrem să aflăm

neterminalul cel mai din stânga care va fi înlocuit, dintr-o formă

propoziţională σ , există o modalitate foarte bună pentru efectuarea

acestei alegeri avansate. Ea va fi prezentată în capitolul 6.

În schema de analiză bottom-up, procesul este invers: Începând cu

şirul 1 2... na a a , încercăm să găsim o formă propoziţională kσ astfel încât

derivarea lui 1 2... na a a să aibă forma

1 2...k nS a a aσ⇒ ⇒ ⇒L .

Pentru aceasta, trebuie să localizăm un subşir α din 1 2... na a a care

corespunde părţii drepte a unei producţii A α→ şi să înlocuim acest α cu

A. (Un astfel de subşir α se numeşte referinţă (eng. handle)). În

continuare repetăm procedura cu şirul kσ în loc de 1 2... na a a . Continuăm

până când ajungem la S. Nu reiese limpede cum se obţine aceasta, dar

este posibil, dacă ne limităm la construirea derivării la stânga. Vom

explica acest proces în capitolul 8. Aşa se explica de ce analiza la dreapta

a fost definit ca fiind inversul secvenţei de producţii folosite în derivarea

la stânga a şirului: În analiza bottom-up determinăm mai întâi ultima

producţie folosită în derivare, iar apoi penultima ş.a.m.d.

PROBLEME

1. Fie 0G limbajul expresiilor algebrice din exemplul 1.3. Daţi

arborele de derivare, analiza la stânga şi la dreapta a următoarelor

şiruri:

a) a a a+ + b) ( )* *( )a a a a a a+ + + c) * * *a a a a a+

Daţi în problemele 2 – 12 o gramatică independentă de context care

descrie limbajul dat şi un arbore de derivare pentru şirul 0σ indicat.

2. Toate şirurile *{0,1}σ ∈ având un subşir 001; 0 01001110σ = .

3. Toate şirurile *{0,1}σ ∈ de lungime impară; 0 0011011σ = .

4. { | 0, 0}m n m nL a b d m n+= ≥ ≥ 0 aaaabcccσ = .

5. { |1 2 }m nL a b n m n= ≤ ≤ ≤ ; 0 aaabbσ = .

6. { | 2 2 3 }m nL a b n m n= ≤ ≤ ≤ ; 0 aaaabbσ = .

7. Mulţimea tuturor şirurilor peste {0,1}Σ = de lungime impară;

0 0010111σ = .

8. Mulţimea tuturor şirurilor peste { , }a bΣ = în care numărul de a-uri

este egal cu numărul de b-uri; 0 abbaaabbσ = .

9. Mulţimea tuturor şirurilor peste { , }a bΣ = în care este un a mai mult

decât b-uri; 0 aabbbaaσ = .

10. Mulţimea şirurilor peste {0,1}Σ = în care 1 apare cep puţin de 3 ori;

0 001101σ = .

11. Mulţimea şirurilor peste { , }a bΣ = în care primul simbol este diferit

de ultimul simbol; 0 aabababσ = .

12. Mulţimea tuturor datelor valide pentru anul 1900 până 1999 dat sub

forma NOIEMBRIE 30, 1941. Observăm că anul 1900 nu a fost un

an bisect deci nu a existat un FEBRUARIE 29 în 1900;

0 30,1941OCTOMBRIEσ = .

În problemele 13 – 15, descrieţi limbajul generat de gramatica dată.

13. |S aaSb A→ , |A cAdd cd→

14. |S ASBB AB→ , |A aA b→ , |B Bc d→

15. | | |S aSb aSbb aSbbb ab→

Fiecare gramatică din problemele 16 – 21 este ambiguă. Găsiţi pentru

aceste gramatici o propoziţie cu doi arbori distincţi de derivare.

16. |S SaSa b→

17. | | |S aSb Sb Sa a→

18. | |S aaS aaaS a→

19. | |S aS aSb A→ , |A Aa a→

20. S AA→ , | | |A AAA a bA Ab→

21. S AaA→ , | |A aA bA λ→

22. Arătaţi că fiecare gramatică stâng liniară are şi o gramatică drept

liniară, şi reciproc.

23. Un fragment al gramatici corespunzătoare construcţiilor

if...then...else, dat în (1.3), a fost ambiguu, propoziţia (1.4) având,

ca în figura 1.8., doi arbori distincţi de derivare. Acest fragment a

fost rescris în (1.5) astfel încât propoziţia (1.4) să aibă arborele de

derivare dat de figura 1.8.(a). Rescrieţi gramatica din (1.3) astfel

încât propoziţia (1.4) să aibă un unic arbore de derivare dat de

figura 1.8.(b).