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).
Top Related