cartea de programare

5/12/2018 cartea de programare - slidepdf.com

http://slidepdf.com/reader/full/cartea-de-programare 1/106

dr. Tudor Bălănescu, Şerban Gavrilă, conf. dr. Horia Georgescu, dr. Marian Gheorghe,

Liviu Sofoüea, prof. dr. Ion "Văduva

IPffiOGlMMAMEA ÎN LÏÏMBAHELIEPASCAL TURBO

PASCAL

volumul ILimbajul Pascal. Concepte fundamentale

(Q )

■

■

EDITURA TEHNICA

Bucureşti, 1992



Copyright © 1992, Editura Tehnică Toate drepturile asupraacestei ediţii sînt* rezervateediturii

Adresa : Editura TehnicăPia{a Presei Libere, 1 33Bucureşti, România cod 79738

■

«

Redactor: Ing. SilviaCândea

( .«pena : grafician

Simona Dumilrescu

Tehnoredactor : Ing.

Silvia Cundea

Coli de tipar: 17; Bun de tipar: 24.1.92 C.Z.:681.3.06

ISBN: 973-31-0430-2; ISBN: 973-31-0431-0

B024779



Comanda nr. 49 Tiraj : 20 000

exemplare

Tiparul: IMPRIMERIA „ARDEALUL" CLUJ

UnivarsiUUH d.->

Stat A l • C B Ru o i: o"

iJiblioieca Ştiinţifica Fonddidactic



Limbajul Pascal - Concepte fundamentale

Un limbaj de programare este un sistem de notaţii pentru reprezentarea

algoritmilor. Exprimaţi în această formă, algoritmii pot fi executaţi de cătrecalculatorul electronic sau comunicaţi altor programatori. Primele limbaje de programare au fost limbajele maşină, care foloseau o notaţie foarte depărtată decea uzuală sau matematică. Odată cu dezvoltarea activităţii de programare aapărut necesitatea de a transcrie un proces de calcul într-un limbaj cît maiapropiat de modul în care a fost elaborat algoritmul ce-l descrie, sau apropiat delimbajul natural. Astfel au apărut limbajele de nivel înalt (FORTRAN, COBOL, ALGOL, PL/I, BASIC, APL, Pascal, C, Aia etc).

Dacă limbajele FORTRAN şi COBOL sînt cele mai folosite în problemelede calcule ştiinţifice şi în cele comerciale, limbajul Pascal a devenit în ultimul timp"lingua franca" a comunităţii informatice din mediul universitar, integrînd cu mult succes un număr mic de facilităţi într-un corpus puternic şi eficient. Acest limbaj afost definit în 1971 de profesorul Niklaus Wirth de la Universitatea Tehnică din Zurich [Wi71a, Wi72J. Numele limbajului este cel al matematicianului şiumanistului francez Blaise Pascal (1623 - 1662), care a conceput la vîrsta denumai 18 ani prima maşină simplă de calculat.

Cîteva din caracteristicile ce au impus limbajul sînt: simplitatea şiclaritatea acestuia, obţinute printr-o riguroasă selecţie a conceptelor de programare; posibilitatea de a atinge o anumită disciplină a programării ceconduce la programe robuste şi eficiente, prin obligativitatea impusă declarăriiobiectelor utilizate (tipuri, constante, variabile) precum şi prin facilităţile oferite deinstrucţiuni ce permit un bun stil de programare (instrucţiuni compuse - begln. . . end, instrucţiuni condiţionale - l f . . . then. . .else, caso, instrucţiuni iterative- while, repeat. . .vntll, fox). La noi în ţară, importante investigaţii privindimplementarea sau/şi utilizarea limbajului Pascal au fost efectuate de colective

din învăţămîntul superior (Institutul Politehnic din Timişoara [Ci82, Ci85], InstitutulPolitehnic din Bucureşti [Io83, Se84], Universitatea din Iaşi [Ru87J).

Prezentarea limbajului Pascal din lucrarea de faţă urmăreşte atît nucleulsău, aşa cum rezultă din monografiile lui Jensen şi Wirth [JeWi74, JeV/i85], cît şiextensiile din varianta Oregon [Pa81]. Un compilator pentru acest limbaj estedisponibil pe minicalculatoarele din familia Independent - Coral. în textul lucrăriimarcăm extensiile limbajului prin scrierea cu italice a părţii care semnaleazăacest fapt.

Lucrarea se adresează cititorilor care sînt oarecum familiarizaţi cu proble

4



matica programării calculatoarelor şi cu noţiunile de bază ale informaticiiteoretice. Ea poate servi ca suport de curs studenţilor facultăţilor de matematică

şi tn aceeaşi măsură poate fi parcursă cu folos şi de absolvenţii acestor facultăţi şiai secţiilor de specialitate din institutele tehnice şt economice.In abordarea anumitor concepte ale limbajului Pascal am încercat să

introducem un instrument matematic care să confere mai multă exactitate şiclaritate prezentării Astfel, tipurile de date au fast în general definite utiUzSndinstrumente din teoria structurilor algebrice [AUr78], sintaxa limbajului este expri-mată fie în notaţia BNF, fie prin diagrame sintactice, iar anumite elemente desemantică jac apel la modele ale semanticii axiomatice de tip Hoare [HoWî73].

Lucrarea este structurată astfel: o introducere, 7 capitole şi 4 anexe.Primele noţiuni despre programarea în limbajul Pascal sînt expuse în

introducere. Capitolul 1 prezintă elementele lexicale şi sintactice ale limbajului încapitolul 2 sînt abordate tipurile de date simple, structurau! şi tipul pointer,variabilele, constantele, etichetele şi expresiile. Instrucţiunile limbajului sînt

prezentate în capitolul 3. in capitolul 4 sînt prezentate conceptele de procedură,funcţie şi program care permit descrierea modular-structurată a proceselor decalcul de mare complexitate. Printre aplicaţiile mai importante prezentate aiciamintim: construcţia tabelelor de analiză sintactică în cazul gramaticilor de precedenţă simplă; folosirea recursiei în cadrul unor algoritmi cu reluare ('back-tracking algorithms") şi pentru analiza sintactică recursiv descendentă Capitolul5 conţine o prezentare formalizată a semanticii, utiUzînd modele axiomatice.Mecanismele dezvoltate aici sînt aplicate la proiectarea programelor prin metodarafinării succesive şi verificarea corectitudinii tn capitolul 6 sînt prezentatefacilităţile de depanare simbolică ale compilatorului Pascal-Oregon, utile şi pentru învăţarea interactivă a limbajului Capitolul 7 oferă cîteva informatiireferitoare la punerea în lucru a compilatorului Pascal sub sistemul de operare

RSX. Anexele Î ş i 2 conţin lexicul şi respectiv sintaxa limbajului Pascal în notaţiaBNF; anexa 3 conţine diagramele de sintaxă O listă a constantelor, tipurilor şivariabilelor predefinite, precum şi o scurtă prezentare a procedurilor şi funcţiilor predefinite se află în anexa 4. _,• , Adresăm cele mai sincere mulţumiri colegeiSilvia Pepelea care, cu răbdare, pricepere şi conştiinciozitate, ne-a asistat înredactarea acestui text

Autorii




INTRODUCERE................................................................................................. 1

1. VOCABULARUL ŞI SINTAXA LIMBAJULUI ....................................................... 5

1.1. Mulţimea de caractere............................................................................. 5- 1.2. Vocabularul limbajului.................................................................. 61.3.Sintaxa limbajului......................................................................... 8

1.3.1................................................................Formalismul BNF............................................................................ 81.3.2................................................................Diagrame sintactice ...................................................................... 10

1.4. Exerciţii........................................................................................ 11

2. TIPURI DE DATE, VARIABILE, CONSTANTE, ETICHETE, EXPRESII ---------------- 132.1. Tipuri de date simple.................................................................... 14

2.1.1................................................................ Tipuri de date predcfmitc............................................................... 14

2.1.2................................................................ Tipuri de date enumerare............................................................... 192.1.3................................................................ Tipulde date subdomeniu............................................................... 20

2.2.Tipuri de date structurate............................................................. 212.2.1................................................................ Tipulde date array (tablou)............................................................ 212.2.2................................................................ Tipulde date record (înregistrate)................................................... 262.2.3................................................................ Tipulde date set (mulţime)............................................................. 302.2.4................................................................ Tipul

de date file (fişier).................................................................. 322.2.4.1...................................................................................Fişiere secvenţiale 33

2.2.4.1.1. Operaţii de intrare/ieşire ............... 332.2.4.12........................................ Fişiere text .................................................................382.2.4.13. Fişierele standard input şi output . . . . 44

2.2.4.2. Asocierea fişierelor Pascal cu fişiere externe .. .44

2.2.4.3.Fişiere cu acces direct.................................... 462.3............................................................................. Tipulde date pointer (referinţă)................................................................... 47

2.4............................................................................. Tipuri de date recursive............................................................................... 49

6



2.5.......................Expresii..........................................................'.($t)

2.6.............................................................................Exerciţii ......................................................................................................................54

3. ÎNSTOUCŢRJNI............................................................................................... 573.1. Instrucţiuni simple....................................................................... 57

3.1.1................................................................Instrucţiunea dc atribuire.............................................................. 573.1.2................................................................mstrucţiunea apel de procedură.................................................... 593.1.3................................................................Instrucţiunea de transfer necondiţionat ........................................ 593.1.4................................................................Instrucţiunea de efect nul.............................................................. 62

,3.2. Instrucţiuni structurate................................................................. 62




3.2.1................................................................Instrucţiunea compusă.................................................................. 623.2.2................................................................Instrucţiuni iterative...................................................................... 63

3.2.2.1....................................................Instrucţiunea while .......................................................... 633.2.2.2....................................................Instrucţiunea repeat.......................................................... 663.2.2.3....................................................Instrucţiunea for ............................................................... 68

3.2.3.................................................................................................... Instrucţiunicondiţionale .......................................................................... 71

3.2.3.1....................................................Instrucţiunea if.................................................................. 713.2.3.2....................................................Instrucţiunea case ............................................................ 73

3.2.4.................................................................................................... Instrucţiunea with74

3.3.............................................................................Exemple................................................................................................... 763.4.............................................................................Exerciţii .....................................................................................................................80

4. PROCEDURL FUNCŢII, PROGRAME, MODULE ............................................. 844.1.............................................................................Mecanisme de abstractizare în Pascal......................................................... 844.2.............................................................................Funcţii .....................................................................................................................84

4.2.1................................................................Declararea funcţiilor...................................................................... 844.2.2................................................................Apelul funcţiilor............................................................................. 854.2.3................................................................Exemple ....................................................................................................86

4.3.Proceduri...................................................................................... 904.3.1................................................................Declararea procedurilor................................................................. 90

4.3.2...............................................................Apelulprocedurilor..........................................................................i 904.3.3................................................................Exemple ...................................................................................................91

4.4.Programe...................................................................................... 924.4.1................................................................Forme sintactice; exemple . .'...................................................... 924.4.2................................................................Structura statică a programelor.................................................... 934.4.3................................................................Domenii de vizibilitate a declaraţiilor............................................. 94

4.4.3.1....................................................Dom

enii de vizibilitate ale declaraţiilor de identificatori..................................................................................95

8



4.4.3.2.Domenii de vizibilitate pentru alte declaraţii ....984.4.3.3....................................................Context asociat unei unităţi de program............................ 99

4.5.Comunicarea între unităţi de program ...................................... 1004.5.1...............................................................Comunicarea prin identificatori globali ......................................... 1004.5.2...............................................................Comunicarea prin parametri.......................................................... 101

4.5.2.1..................................................Parametri valoare........................................................... 1014.5.2.2..................................................Para

metri variabilă.......................................................... 1024.5.2.3..................................................Parametri formali funcţie / procedură............................. 1034.5.2.4.................................................. Tablouri ca parametri....................................................... 1064.5.2.5..................................................Structura dinamică a programelor .................................... 107

4.5.3. Efecte secundare la execuţia funcţiilor şi procedurilor ... . 1084.5.3.1.

Atribuiri asupra variabilelor globale.............. 1094.5.3.2. Atribuiri asupra parametrilor formali varia

bilă.............................................................. 1094.5.3.3.

...............................................................................

Parametri actuali cu acelaşi nume pentru para-metri formali variabilă distincţi..................... 110

4.5.4. Recursie .................................................................... 1114.5.4.1..................................................Recursia indirectă ............................................................ 1114.5.4.2..................................................Recursia directă ............................................................. 1124.5.4.3. Recursia şi metoda reluării ("backtracking") . . .

1254.5.4.4..................................................Aplica

ţie: analiza sintactică recursiv descendentă 1314.5.4.5.Aplicaţie: calculul relaţiilor de prece-

denţă .......................................................... 1394.6. Module....................................................................................... 150

4.6.1.Definirea si utilizarea modulelor in Pascal Oregon....... 1504.6.1.1..................................................Compilarea separată.......................................................... 1514.6.1.2..................................................Module externe................................................................. 1514.6.1.3..................................................Modulprincipal................................................................... 153

4.6.2.Comunicarea între module.......................................... 1544.6.2.1............................................Comunicar

ea prin variabile globale ..................................• • • • 154




4.6.2.2..................................................Comunicarea prin apel de funcţii / proceduri externe................................................................................154

4.7. Exerciţii...................................................................................... 155

5. REPREZENTAREA FORMALIZATĂ A SEMANTICII.......................................... 1585.1...........................................................................Introducere................................................................................................ 1585.2...........................................................................Sisteme axiomatice de tip Hoare.............................................................. 159

5.2.1.............................................................. Axioma instrucţiunii de efect nul.................................................... 162

5.2.2.............................................................. Axioma instrucţiunii de atribuire ................................................... 1625.2.3.......................................... Regula consecinţelor .

...................................................................1635.2.4...............................................................Regula instrucţiunii compuse........................................................ 1635.2.5...............................................................Regula instrucţiunii if..................................................................... 1645.2.6...............................................................Regula instrucţiunii while.............................................................. 1655.2.7...............................................................Regula instrucţiunii repeat............................................................ 1715.2.8...............................................................Proble

ma terminării programelor ................................................... 1745.2.9...............................................................Regula instrucţiunii for ............................................................... 1765.2.10.............................................................Regula funcţiilor............................................................................ 1775.2.11.............................................................Regula apelului dc procedură ....................................................... 178

5.3...........................................................................Metoda de programare top-down................................................................ 1805.4...........................................................................Exerciţii ...................................................................................................................192

6. DEPANATORUL SIMBOLIC........................................................................... 1966.1...........................................................................Consideraţii generale................................................................................ 1966.2...........................................................................Comenzile de bază ale depanatorului........................................................ 197

6.3. Comenzi de depanare .................................................. 1986.3.1. Comenzi relative la crearea/distrugerea punctelor de

întrerupere (breakpoints).................................... 1986.3.1.1. Comenzi relative la crearea/distrugerea punctelor de

întrerupere ce controlează execuţia

unui program................................................. 1986.3.1.2. Comenzi relative la crearea/distrugerea punc-

telor de întrerupere pentru variabile.................. 1996.3.2...............................................................Comenzi ce controlează execuţia programului..................................... 200

10



6.3.3...............................................................Comenzi pentru trasarea execuţiei..................................................... 2016.3.4...............................................................Comenzi relative la date................................................................... 2016.3.5...............................................................Comenzi informative........................................................................ 2026.3.6.................................Macrocomenzi..................,

2036.3.7...............................................................Comenzi referitoare la stiva programului............................................. 204

6.4. Lista comenzilor ............................................................................ 206

7. UTILIZAREA COMPILATORULUI PASCAL-OREGON----------------------_ .. „.------------- 201

7.1...........................................................................Punerea în lucru a compilatorului Pascal-Oregon.............................................. 2077.2...........................................................................Opţiuni de compilare..................................................................................... 2087.3...........................................................................Exemple ...................................................................................................................2097.4. Directive comentariu.................................................................... 2117.5. Directiva % include ....................................................................... 212

Anexa 1. VOCABULARUL LIMBAJULUI PASCAL........................................,............. 219

Anexa 2. SINTAXA LIMBAJULUI PASCAL ÎN NOTAŢIA BNF........................................ 221

Anexa 3. DIAGRAMELE SINTACTICE PENTRU LIMBAJUL PASCAL.............................. 226

Anexa 4. CONSTANTE, TIPURI, VARIABILE, FUNCTH, PROCEDURI

PREDEFINITE .................................................................................... 2334.1...........................................................................Constante................................................................................................... 2334.2........................................................................... Tipuri

...................................................................................................................2334.3...........................................................................Variabile ...................................................................................................................2334.4...........................................................................Funcţii

...................................................................................................................2334.5...........................................................................Proceduri ...................................................................................................................2354.6...........................................................................Listasimbolurilor echivalente........................................................................ 236

RĂSPUNSURI LA EXERCIŢII................................................................................. 237

BIBLIOGRAFIE.................................................................................................. 255




INTRODUCERE

Acest capitol prezintă cîteva exemple de programe în limbajul Pascal, pre-cum şi unele caracteristici ale limbajului, avînd drept scop formarea unei viziunide ansamblu asupra acestuia înainte de a-i cunoaşte detaliile. în încheiere sînt

descrise pe scurt comenzile necesare executării unui program scris în limbajulPascal-Oregon sub sistemul de operare RSX-11M. Acest limbaj a fost proiectat şiimplementat de către firma Oregon Software.

Menţionăm că la citirea şi scrierea datelor în exemplele din acest capitolse utilizează doar mediile standard de intrare / ieşire, in implementarea Pascal-Ore-gon acestea fiind terminalul utilizatorului.

Primul exemplu este un program numit Mesaj care scrie un şir decaractere. Pe unele linii ale programului apare un comentariu, delimitat prinacoladele { şi }.

program Mesaj; (programul numit Mesaj}begin {inceputul secvenţei de instrucţiuni}

writeln('Primul program in limbajul Pascal')

{instrucţiunea writeln ...scrie şirul decaractere "Primul . . ." si apoi trece lalinia următoare a ecranului terminalului}end. {sfirsitul programului}

Următorul program numit suma, citeşte două numere întregi, calculeazăsuma acestora şi scrie rezultatul.

program Suma;var x, y, z : integer; {declara variabilele intregi

x, y, z}begin

read(x); {citeşte o valoare in x}readln(y); {citeşte o valoare in y si trece la linia

următoare a ecranului} z := x + y;{instrucţiune de atribuire; z primeşte

valoarea x + y}writeln(z) {este scris z}

Din exemplele anterioare se poate desprinde următoarea structură a unuiprogram în limbajul Pascal:

program NUME; } antet de program. {decl araţ ii de varia bile } ~|

\ partea declarat ivă Jbegin 1

. {instrucţiuni ce pot} |

12

. {uti l iza aceste variabile} \ instrucţiunea| compusăend. J

Prin urmare, un program este alcătuit în general dintr-un antet de program, oparte declarativă în care sînt descrise toate entităţile folosite şi o instrucţiune compusă.

Instrucţiunea compusă poate conţine la rîndul ei, alte instrucţiuni (condiţionale,iterative, etc.).

Spre exemplu, pentru a calcula valoarea absolută a unui număr real x se foloseşteinstrucţiunea condiţională if, după cum urmează:

program Valabs;var x : real; {se declara var iabi la reala x}begin

readln(x); {se citeşte x}if x < o {daca x < 0 }then x := -x; {atunci i se atribuie lui x

valoarea -x, altfel x.ramineneschimbat}

w ri te lnCa bs ( x ) , x ) { si nt s cr is e m es aj ul "abs( x) ="si valoarea.x}

end.

Dintre instrucţiunile iterative ale limbajului Pascal vom alege spre exemplificareinstrucţiunea for care este folosită în programul următor pentru a calcula suma a n

elemente aflate într-un vector:

program Suma_n_elem;const n - 10; {se introduce constanta 10, cu numele n} var i :integer;

v : array [l. .n ] of rea l; {se dec lar a un vec tor v cun componente numere rea le}

suma : real;

procedura Adună (x :xe al ; var y: rea l);{Procedura Aduna ca lc ul ea ză x+y s i intoaxce re zu lt at ul in y; detaliidespre proceduri in capitolul 4i begin

y:= y + x

end; {Aduna}

begin {pr ogr am p rin cip al}for i: =l to n do {pen tr u i de la 1 la nj readln (v[i ) ; {se

cit eşt e va loa rea v[i ] , cit e una de pe o linie}suma :- 0;for i := 1 to n do {pentru val or il e succesive

ale lui i}Adună(v[ i], sum a); {ad una la suma al i-lea

element al l ui v)write ln(' suma ■»', suma)

end.

în programul care urmează, ilustrăm utilizarea instrucţiunii iterative whilepentru a calcula numerele Fibonacci mai mici decît 100.

program Fibonacci; var J, K : integer; begin J := 0;K := 1; ->r-':

while K < 100 do begin {c it ti mp ul ti mu l numărFibonacci obţinut estemai mi c decît 100}writeln(K); {scr ie valoarea numărului

Fibonacci}K ;= K + J; {K vă f i următorul număr

Fibonacci} J := K - J {J este valoarea anter ioara

a lui K}end {wh il e}

end.

Presupunem că textul unui program Pascal se află într-un fişier creat cuajutorul unui editor de texte (EDT, EDI, etc). Pentru ca programul să devină exe-cutabil, acest text este" prelucrat succesiv de compilator şi de editorul de task-uri.

Spre exemplu, dacă programul Fibonacci se află într-un fişier numit 7IBO.PAS, atunci compilarea sa se face în urma lansării comenzii

PAS FIBO

Rezultatul compilării este depus în fişierul FIBO .OBJ , care va fi prelucrat

de editorul de task-uri. Acesta se activează prin comanda

FTB PROG /FP /CP " FIBO, LB«[1,1]PASLIB /LB

Programul în format executabil este obţinut în fişierul PROG. TSK şi poatefi lansat în lucru prin comanda:

HUN PROG

Alte detalii în legătură cu compilarea programelor pot fi găsite în capitolul 7.Pentru programatorii familiarizaţi cu alte limbaje de programare, men-

ţionăm cîteva din caracteristicile limbajului Pascal:

1. Declararea variabilelor este obligatorie.2. Anumite cuvinte cheie (de exemplu hegin, end) sînt rezervate,neputîndfi utilizate ca identificatori.

* 3. Tipurile de date disponibile în Pascal sînt: simple (tipuri de date întregi,reale, logice, caractere, enumerare, subdomeniu), structurate (tipuri de datetablou, înregistrare, mulţime, fişier), pointer. Limbajul permite definirea de cătreutilizator a unor tipuri noi.

4. Tablourile pot avea dimensiuni şi limite arbitrare, dar constante, aleindicilor.

5.Instrucţiunile pot fi etichetate. Etichetele sînt întregi fără semn şitrebuie să fie declarate.

6. Procedurile şi funcţiile pot fi apelate recursiv.7. Toate obiectele (constante, tipuri, variabile, etichete, proceduri, funcţii)

trebuie să fie declarate înainte de utilizare, cu următoarele două excepţii:

14

- identificatorul de tip din definiţia unui tip de date pointer (vezi 2.3);- identificatorii de proceduri şi funcţii pentru care există o directivăforward (vezi 4.6.4.1).

Vocabularul oricărui limbaj de programare conţine cele mai simpleelemente cu semnificaţie lingvistică, iar sintaxa limbajului defineşte modul încare se combină elementele vocabularului pentru a obţine fraze corecte(instrucţiuni, secvenţe de instrucţiuni, declarări de tipuri, variabile, constante,etichete, funcţii, proceduri etc).

1.1. Mulţimea de caractere

Elementele vocabularului sînt alcătuite din caractere. Orice caracter estereprezentat în calculator, în mod urne, printr-un număr natural cuprins între 0 şi

0î23456,70 |nulsohstxetx eotenqack bel1Ibshtlfvtff crsosi 2 |

dle deldc2dc3 dc4naksynetb 3 |canemsubescfsgs us4 !- • -..5 |l6 j7

|'8' • 9 ' 1 m 1I m *t ' <'* ST '' >'' ?'8 |'®''A''B''C' 'D': 'E'' F'' G' 9

1' H' 10 |'p''Q' 'r.''s''t* -'u''v'.11 |i 'X' 'Y'• [''V* *1 12 |I I I 'a' .',b' ,•c'd''ef ■ •%''g' 13,. j\ -K'

i''■X'k' ■1''m' 'h''o' 141 'p'15del

Se face distincţie între caracterele neimprimabile (caracteruldel şi cele de pe primele patru linii, care au codul cuprins

127, numit cod ASCII. Astfel, codul unui caracter de pe linia 1 şi coloana c dmtabela de mai jos este 81+c. Spre exemplu, codul caracterului 2 este 50.Mulţimea de caractere a limbajului Paseal-Oregon conţine următoarele elemente:ale acestei mulţimi: literele alfabetului latin (mari sau mici), cifrele arabe,caracterul * ' (spaţiu), '+*, *-', '>', etc.

1.2. Vocabularul limbajului

Cele mai simple elemente, alcătuite din caractere şi care au semnificaţielingvistică sînt unităţile lexicale. Acestea fonnează vocabularul limbajului. Distingemurmătoarele unităţi lexicale:

- simboluri speciale;

- identificatori;- numere;- şiruri de caractere;- etichete;- comentarii;- directive.

Simbolurile speciale sînt:

+ -* / = < > ( > I J : =

{ } * @ <> <=>=

■ t .0)

şi cuvintele cheie: ■ ■■

and array begin case const

div do downto else end

file for function goto if

in labei mod nil not (2)of or origin otherwise packed

procedure program record repeat set

then to type until var

while with

Cuvintele cheie sînt rezervate, adică sînt utilizate în programe doar cusemnificaţia dată explicit prin definiţia limbajului. Celelalte simboluri speciale sîntfolosite ca operatori şi delimitatori.

Identificatorii sînt nume asociate constantelor, variabilelor, tipurilor dedate, procedurilor şi funcţiilor. Primul caracter al numelui este o literă sau '$* iarcelelalte sînt litere, cifre, '$', sau *_'• Exemple: x i , Suma____x_y, $PRET____NOU.

Numerele pot fi de tipul integer sau de tipul real.Numerele de tipul integer desemnează numere întregi şi sînt scrise în

reprezentare zecimală, precedate sau nu de semnele *+* sau Spre exemplu, va-loarea întreagă 23 poate fi reprezentată prin numerele +23, 23, 023 etc. înPascal Oregon numerele de tipul integer pot fi reprezentate şi în baza 8, şirul decifre octale fiind urmat în acest caz de litera B (sau b). Spre exemplu +27B, 27 bşi 027B sînt reprezentări ale valorii 23.

Numerele de tipul real desemnează numere raţionale cu număr finit de

zecimale. în mod uzual ele sînt reprezentate prin numere fracţionare (în baza 10)cu partea""fracţionară separată de partea întreagă prin punct,,Spre exemplu prin

16

3.1415 este reprezentată aproximarea prin lipsă a numărului %. Punctai zecimaltrebuie să fie precedat şi urmat de cel puţin o cifră zecimală. Astfel, 1. sau .1 sîntreprezentări eronate pentru 1.0 şi respectiv 0.1.

în scrierea numerelor de tipul real se poate utiliza şi un factor de scală.Acesta este un număr de tipul integer, precedat de litera E (sau e). El apare dupăun număr de tipul integer sau un număr fracţionar şi are următorul efect:valoarea numărului de tipul real este valoarea numărului întreg sau a celuifracţionar, înmulţită cu 10 la puterea dată de factorul de scală.

Spre exemplu 31415E-4, 314.15E-2, 0.31415E1, 0.31415E+leta.,reprezintă aceeaşi aproximare a numărului 7C.

Numerele de tipul real pot fi precedate de semnele + sau -.Şirurile de caractere sînt şiruri de caractere imprimabile, delimitate de

apostrof. în şirul de caractere, apostroful apare dublat.Exemple:'şir de caract ere IMPRIMABILE''APOSTROFUL ESTE ' ' 'Etichetele sînt şiruri de cifre zecimale.Exemple: 1, 01,20, 0. De notat că 1 şi 01 reprezintă aceeaşi etichetă.Comentariile sînt şiruri de caractere precedate de { şi urmate de }.Directivele sînt cuvintele rezervate forward, externai, nonpascal (vezi

capitolul 4) şi %include (vezi capitolul 7).In scrierea oricărei unităţi lexicale ce nu este literal alfanumeric nu se

face distincţie între litere mari şi litere mici. Astfel, identificatorul SUMA esteidentic cu Suma, dar literalele alfanumerice 'SUMA' şi 'Suma' sînt distincte.

De asemenea orice unitate lexicală (cu excepţia comentariilor) se scrie

peo singură linie. ' ;-,Exemplu: Următorul mod de scriere a identificatorului SUMA: su MA . nu este

permis.La scrierea consecutivă a identificatorilor, a cuvintelor cheie, a literalelor

numerice fără semn şi a celor alfanumerice, începutul unei unităţi lexicale arputea fi luat în unele cazuri drept o continuare a celei precedente. în aceastăsituaţie, între ele se inserează spaţii (caracterul ' ')» caractere de tabulare (ht dintabela ASCII) sau de salt la rînd nou (f f şi cr în aceeaşi tabelă). Trebuie observatcă simbolurile speciale compuse de forma o, < = etc., identificatorii şi literalelenumerice sînt unităţi lexicale ale programului; deci nu se pot introduce spaţii

între caracterele componente.

Exemplu: nu se poate scrie < >, < =, su MA, I 23 pentru o, <=,SUMA şi 123 .• Uiii '. ■■• .' • • ii •■

13. Sintaxa limbajului

Prin sintaxa unui limbaj de programare se înţelege, în general, unansamblu de reguli de agregare a unităţilor lexicale pentru a forma structuri maicomplexe (instrucţiuni, declaraţii, programe, etc). Spre exemplu, în introducere afost prezentată forma generală a unui program Pascal: un antet, urmat de o partedeclarativă şi de o instrucţiune compusă. Pentru descrierea în detaliu a acestorcomponente sînt necesare desigur alte reguli. Prezentarea în limbaj natural aacestor reguli poate conduce la neclarităţi sau la specificări incomplete. Ne-am

putea întreba spre exemplu dacă prezenţa antetului unui program este

obligatorie etc. De asemenea, prin această prezentare nu este posibilă overificare completă a corectitudinii unui program. în 1959 este prezentată de către J. Backus o descriere a sintaxei limbajului

Aigol60 printr-un ansamblu de reguli formale [Back59]. Notaţia utilizată a devenitcunoscută sub numele de notaţie BNF (Backus-Naur-Form) şi are aceeaşi puteregenerativă [GR62] cu gramaticile independente de context introduse de N.Chomsky [Ch59].

Au fost dezvoltate şi alte variante echivalente de specificare a sintaxei,precum formalismul de descriere a sintaxei limbajelor Cobol şi PL/I [Sam78] şidiagramele sintactice pentru definirea sintaxei limbajului Pascal [Wi72] şiFORTRAN [ANSI78J.

1.3.1. Formalismul BNFDeoarece majoritatea limbajelor de programare nu sînt independente de

context [F166], prin notaţia BNF se obţine o descriere incompletă, referitoaredoar la aspectele de sintaxă ale limbajului. Cu toate acestea, datorită simplităţiisale, formalismul a căpătat o largă popularitate, răspunzînd atît dezideratelorimpuse de fazele de proiectare şi implementare a unui limbaj de programare, cîtşi cerinţelor utilizatorilor.

Varianta de formalism BNF utilizată în această prezentare foloseşte urmă-toarele opt metasimboluri:

< > | { 1 [ ]

pentru a defini uhităţile sintactice ale limbajului Pascal.O unitate sintactică este o mulţime de fraze alcătuite din elemente ale

vocabularului.

Metasimbolurile < şi > sînt utilizate pentru delimitarea numelui uneiunităţi sintactice. • u >;.-

Exemplu. Unitatea sintactică <program> are numele program şi estemulţimea tuturor programelor Pascal; <expresie> este mulţimea tuturorexpresiilor ce apar în programele Pascal.

Pe mulţimea unităţilor sintactice este definită o operaţie de concatenareprin

<uxv> - {xy | x din , y din <v>i

unde xy este o frază obţinută prin adăugarea frazei y la sfîrşitul frazei x. Aceastăoperaţie este asociativă şi are elementul neutru <empty> (unitatea sintactică cenu conţine nici o frază).

Exemplu: dacă + aparţine lui <semn> şi (a ♦ b) aparţine lui <termen>atunci + (a *■ b) este în <semn><termen>.

Metasimbolul ::= apare după o unitate sintactică şi are sensul "unitateasintactică este definită prin".

Exemplu. Definiţiile următoare:

< te rm en > : :- < fa ct or > < re st termen><rest termen)::^ <operator multipl icativ> <factor><rest termen>

<rest termen>: : - <empty> T "

18

au semnificaţia: un termen este o succesiune de unul sau mai mulţi factori,despărţiţi printr-un operator multiplicativ.Metasimbolul | este utilizat pentru a delimita între ele mai multe variante

de definire a unei unităţi sintactice. Unitatea sintactică definită este obţinută prinreuniunea variantelor. - •»

Exemplu. Unitatea sintactică <rest termen}.- <mai poate fi definită siprin ' ■ i

:•

• • • i •' . ■<rest termen)::»<empty > |

<operator multipl icativ) <factox> <rest.termen)iar definiţia

<o pe ra to r m ul ti pl ic at iv ) ::- * | / | div | mod | and

precizează care sînt cei cinci operatori multiplicativi. ; , • ,Metasimbolurile { şi } denotă repetarea posibilă (de zero sau mai multe

ori) a simbolurilor pe care le delimitează. în general, <u) :.:= { <v) ) se foloseşteca prescurtare pentru definiţia recurşi vă .-■v-

 ::= <u)<v> | <empty) v - .

Exemplu. Definiţia unităţii sintactice < termen > din exemplele anterioaremai poate fi scrisă sub forma

<termen>::=<factor> ţ <operator mult ipl icativ) <factor> î

Exemplu: Definiţia

•Cident i f icator> : : = <l i tera> { <l i tera> | <ci fra> ] _ }

are semnificaţia: un identificator începe cu o literă; după această literă poateurma o secvenţă finită de litere,cifre sau caractere *_*. Astfel, A, al , A1B, Al_bsînt conforme cu această definiţie, dar 2A nu.

Metasimbolurile [şi 3 denotă prezenţa opţională a simbolurilor pe care lelimitează. Spre exemplu, definiţia < unu > [ + | --] l defineşte unitatea sintacticăce conţine elementele +1, -l şi 1.

O definiţie în notaţia BNF poate fi privită ca o expresie în care sînt eva-luaţi, în această ordine de prioritate, operatorii concatenare, | şi : : = , cuconvenţia uzuală în ceea ce priveşte parantezele ( , } şi [ , ] .

Sintaxa limbajului Pascal, în notaţie BNF, este dată în anexa 2.Frazele unităţii sintactice <program> se numesc programe Pascal corecte

sintactic.Exemplu. Următoarele fraze

program A ( I ) ; begin end.program A ( I , O); begin begin end end.

sînt programe Pascal corecte sintactic.Simbolurile { , } , [ şi ] utilizate în notaţia BNF sînt în acelaşi timp şi

elemente ale vocabularului limbajului Pascal. Pentru a evita confuziile, în anexa 2aceste simboluri, ca elemente ale vocabularului, sînt redate prin simbolurile echi-

valente ( *, *) , (. şi respectiv .) . în programele Pascal pot fi utilizate ambelevariante.

în notaţia BNF se poate specifica şi vocabularul unui limbaj deprogramare dacă prin desemnăm unitatea lexicală u. Vocabularul limbajuluiPascal este descris in notaţie BNF în anexa 1.

1.3.2. Diagrame sintactice m

Prin diagrame sintactice se realizează o reprezentare mai intuitivă asintaxei unui limbaj independent de context decît cea dată de notaţia BNF. Aufost utilizate pentru prima dată pentru definirea sintaxei limbajului Pascal [Wi73J.Notaţia prin diagrame poate fi derivată din notaţia BNF în modul următor.

1.4.

Exerciţii

11

O definiţie de forma : x_l . . . x_n se reprezintă prin diagrama

-------> x_l --------> . .. --------->x_ n ----->

iar o definiţie de forma :: - x_l | x_2 . . . | x_n prin diagrama

------—> x_l---------------,------>

I-------> X 2 --------1

1-------> x_n --------1Definiţia ::= x { yx { se reprezintă prin

•I--- --> * ------1-------->1-------- y <-----J

F 1

iar <U^ : : = [ X ] prin

-------1- - -> X ----1----->L______________I

Exemplu. Unitatea sintactica <r.ertnen> poate fi definită prin diagrama

<termen>------1----------------> <factor >-------------------------1----->

l----- <ope rat or mul tip lic ati v> <----------1

iar <identif icator> prin<xdentif icator>

----------------------------> <litera> ---------1--------:------------i

<litera> <------j<cifra> <-

— <-------U

Sintaxa limbajului Pascal este definită cu ajutorul diagramelor sintactice înanexa 3.

20

I A . Exerciţii1. Limbajul Pascal are cuvinte rezervate. Dar FORTRAN? Daţi exemple de limbaje care

au cuvinte rezervate.

2.Care dintre următorii identificatori sînt corecţi: Pascal, PASCAL, $PASCAL, PI, 1 P ,p_l . Ident i f icator_f oar te_lung_dar__, $ 1 , $_Ţ1, P_-

3.Limbajul Ada [Ada83] defineşte instrucţiunea if astfel:

<if_stmt> ::=if <cond itio n> then <soq _of_ stmts > <if_ alter .nati ve> endif

<if_atternative> ::- (<elsif_alternative>}

[else <seq_of_stmts> J < elsif_alternati ve> ::-elsif <condit ion> then <seq_of_stmts>

Rescrieţi această notaţie BNF prin diagrame sintactice echivalente.

4. Fie următoarele diagrame sintactice:A B

----,--------------,----> —,-------> C"------,---->

I---- B <—' '------- c <-------1

Scrieţi în notaţia BNF definiţiile acestor diagrame.

5. Fie diagramele următoare:

" A • -i i'î ■•■ -4i ' B ■■■■■

-------------,-----------------------------------------------i---------------> ---------> C ------> DI----- B <----■

Sînt acestea echivalente cuA

—>---- C <— D <—-l

6. Care dintre exemplele următoare sînt programe Pascal corecte sintactic (vezianexele 1 şi 2) ?a) program EX EMP LU;

b) const A - 1;type T = 0 . . 2 ;const C - A;var X, Y : T;

c) beginX :- A + 1;

Y : = A *■ C

end.

d) Programul obţinut prin concatenarea exemplelor a, b şi c.

TIPURI DE DATE, VARIABILE,

CONSTANTE, ETICHETE, EXPRESII




Un program în limbajul Pascal conţine o descriere a acţiunilor ce trebuiesă fie executate de calculator şi o descriere a datelor ce sînt manevrate deaceste acţiuni. Acţiunile sînt descrise prin instrucţiuni, iar datele prin declaraţii(sau definiţii). Prin tip de date se înţelege o mulţime de valori. Pe tipurile de dateale unui program se definesc o serie de operaţii, rezultatul fiind o algebrămultisortată [ADJ77] avînd ca domenii aceste tipuriijSe disting trei categorii detipuri de date: sjmple (elementare), compuse (structurate) şi de referinţă(pointer). în general, tipurile de date sînt definite explicit prin declaraţiile type iaroperaţiile asociate prin declaraţiile f unction sau procedura şi sînt specificeprogramului în care ajpar.: Există însă tipuri de date elementare de interes maigeneral, numite tipuri predefinite a căror definiţie se consideră cunoscută şi nucade în sarcina programatorului. O serie de operaţii relative la aceste tipuri sîntde asemenea predefiñité. .Valorile unui tip de date sînt referite prin variabile sauconstante. Anumite constante sînt predefinite (vezi anexa 4).

O declaraţie de tip este de forma

type I - T;

unde I este un identificator numit numele tipului, iar T specificaţia sa (vezi anexa3, diagrama 3.7). Declaraţia variabilelor este precedată de cuvîntul cheie var, aconstantelor de cuvîntul cheie const, iar a etichetelor, de ciivîntul cheie labei(vezi anexa 3, diagramele 3,8, 3.6, 3.5). Numele I poate fi folosit pentm referirea

la tipul T in declaraţiile ulterioare de variabile sau pentru definirea altor tipuri.Exista însă tipuri de date anonime, definite implicit prin declaraţii de

variabile de formavar v_l, . . . , v_n : T ;

Exemplu. Prin labei 1, 10;type bin = 0..1; var bit.: bin;

cifra : 0..9; constzer o - 0; var i :integer;

s-au definit: etichetele 1 şi io,

tipul b in cu elementele 0 şi i, variabila bit de tipul bi n, variabila cifră de tipulanonim o. variabila i de tipul predefina integer precum şi constanta zero avîndvaloarea 0.

2.1. Tipuri de date simple

Tipurile simple sînt de trei categorii: predefinite, enumerare şisubdomeniu. Tipurile simple se mai numesc şi tipuri scalare.

2.1.1. Tipuri de date predefinite

Există cinci tipuri de date predefinite: integer, real, boolean, char şi text.

■—- Tipul integer este o mulţime de numere întregi cuprinse între cel mai micşi cel mat mare număr întreg ce se pot reprezenta pe un calculator gazdă allimbajului. Valoarea maximă admisă poate fi referită prin constanta predefinită

22

ataxint, iar valoarea minimă este -max in t. In implementarea Pascal -Oregon, maxint este 32767, iar valoarea minimă este -maxint -1.Elementele de acest tip se reprezintă în programele Pascal prin literale numericede forma i, unde i este număr întreg în reprezentare zecimală (eventual precedatde semnul + sau -) sau de forma i 13, unde i este număr întreg în baza 8(reprezentare octală, eventual cu semn). Spre exemplu, elementul -15 altipului integer poate fi reprezentat prin literalele -15 sau - l7B.

Reprezentarea internă (fornui de memorare) a elementelor deacest tip se face în cod complementar pe cuvinte de 2 bytes [PDP76J. Fiex reprezentarea în baza 2 a unui număr întreg. Reprezentarea în codcomplementar a lui x este

f x dacă 0 < x < 0 111 3 11 11.1 i ii mrc(x) - j

l_2"-|x| dacă x<0 şi 2"-|x| 1 1 000 000 000 000 000 f x

dacă 0 < x < 2i,-lHL 2 l t e+x dacă 2" < x < o

De exemplu -9 se reprezintă prin 2l6-9, adică 177767 (în octal), iar 9 prin 000011(în octal).Rezultă că cel mai mare număr reprezentabil în cod complementar este 2lM,adică 32767 (maxint); cel mai mic număr este -21S, adică -32768. Tipul real este

mulţimea de numere reale

{xfx-±0,x 0Xi. . .x„- b* şi x. s înt cifr e în baza b şi l,SeSl,J

unde baza b a sistemului de numeraţie, limitele lt şi 1„ ale exponentului e şinumărul n+l de cifre ale părţii fracţionare sînt dependente de implementare iarx0*o pentru x*o. în cazul de fală, b = 2, -128 £ e < 127, iar n - 23 (sau,opţional, n = 55 - vezi cap. 7, opţiunea /DOUBLE).

Elementele tipului real se reprezintă în programe prin literale numericede formele i. f, i. f Es sau iEs, eventual precedate de semnul + sau -, unde i şi f sînt numere zecimale întregi fără semn reprezentînd partea întreagă şi respectivpartea fracţionară a literalului numeric. Dacă este specificat şi factorul de scală s(zecimal întreg, eventual cu semn), atunci literalul reprezintă valoarea reală i, f •io" sau ir io?.

Spre exemplu, elementul -0,25 al tipului real poate apare în programePascal în una din formele -0.25, -25E-2, -25.0E-2 etc.

Se observă că î n programele Pascal elementele tipului real se presupuna fi scrise în baza 10.

Reprezentarea (memorarea) acestora în calculator se face învirgulă mobilă pe 2 cuvinte (32 biţi - simplă precizie) sau pe 4 cuvinte(64 biţi - dublă precizie). Poziţia binară 15 (prima din stingă, în notaţiauzuală) a primului cuvînt este a semnului, în poziţiile 7-14 ale primuluicuvînt se memorează caracteristica (exponentul mărit cu 128), iar în rest se memorează mantisa (partea fracţionară fără prima poziţie dupăvirgulă; numărul real fiind normalizat, această poziţie este 1, cu excepţia

numărului real 0). De exemplu +1.0 se scrie 0,1-2' (adică xc=l, b=2 şi e-l);caracteristica este c = l?B+e ~ 27+.l = îoo ooo oi. Deci primul cuvînt al

reprezentării în calculator este o 10000001 oo oo oo o, iar al doilea cuvînt esteoooooooooooooooo (în baza 2). Reprezentarea octală este 4 0200, respectivo. în mod analog, -5.0 se va reprezenta prin numerele octale 14 064 0 şi o.

Cel mai mare număr real reprezentabil în simplă precizie este0, l l l l . l l l l l l J . l l l l l l l l l - l l . i l . ' 2.A-,*l- 2'27*1038.

Cel mai mic număr real pozitiv reprezentabil este0,1-2' 1 2 7=2 1 2 3»ip3% .

Numerele reale de fonna o, lx t. . . x2, împart intervalul în 223 subintervale delungime (l-^)'2"23=224. în consecinţă, eroarea maximă de aproximare a unuinumăr real printr-un număr real reprezentabil este zS-2"2* < IO"7. De aici rezultăo precizie de 7 cifre zecimale semnificative pentru numerele reale reprezentate

înprecizie simplă. --.

Tipul boolean conţine două elemente referite prin constantele predefinitefalse şi true. Operaţiile predefinite ale acestui tip (and, or şi not) definesc ostructură de algebră booleana.

Tipul char este o mulţime finită şi ordonată de caractere ce conţine,printre altele, litere, cifre şi caracterul spaţiu. în cazul de faţă, toatecaracterele ASCII (vezi paragraful 1.1) aparţin tipului char.

în programe, un element al acestui tip se desemnează prin includereacaracterului între două semne ' (apostrof). Spre exemplu, ' A' , '0 ', ' + ', ' 'desemnează litera A, cifra o, caracterul + şi caracterul spaţiu. Caracterul ' sereprezintă prin

Reprezentarea internă a unui element de acest tip se face pe Ibyte şi areca valoare codul ASCII al caracterului respectiv (paragraful LI). Primulcaracteral tabelei are numărul de ordine 0. . c.

-Tipul text va fi prezentat în paragraful 2.2.4.1.2. Există de asemenea o serie de operaţiipredefinite în care sânt implicate tipurile de date descrise anterior. Ele sînt desemnate prinoperatori şi funcţii predefinite. Astfel, operatorii binari ♦ (adunare), - (scădere), * (înmulţire)şi / (împărţire) pot avea operanzi de tipul integer sau real . în cazul operatorului /rezultatul este totdeauna de tipul real. Pentru +, - şi * rezultatul este de tipul integerdacă ambii operanzi sînt din integer şi este de tipul real dacă cel puţin unul din operanzieste de tipul real. Pentru împărţirea prin trunchiere a valorilor din tipul integer seutilizează operatorul dlv. Astfel, a div b - n dacă:

1) § 2' 0- şi n £ § < n+1

sau2) § < 0 şi n-l< g Sn.

Deci -13 div 2 este -6.Fie a, b € z, b*o. Se notează prin q cîtul şi prin r restul împărţirii întregi a lui a la

b (a - b * q + r , 0< = r < abs (b)); He rem - a - ( a div b) * b.Dacă a £ o sau b divide pe a, atunci q - a div b şi r - rem. în caz contrar, q = a

div b - sign (b) şi r = rem + abs (b).Pentru calculul expresiei r em se poate utiliza operatorul nod. în limbajul standard

[JeWi85], a mod b m rem dacă ai.0 sau b divide pe a şi a mod b = rem + b în cazcontrar. în implementarea Pascal-Oregon, a mod b - rem în ambele cazuri înconsecinţă, în implementarea Pascal-Oregon q şi r se calculează prininstrucţiunile următoare:

q :- a div b; r := a mod b; it (a < 0)and ( r O 0) than begin

24

r := r + abs(y);ii b < 0 then q := q + 1 else q := q - 1end

în limbajul standard, q şi r se calculează prin: q := a divb; r :« a mod b; if. (a < 0) and (r O 0) then if b > 0then q q - 1

else begin q : - q + l ; r : - r - 2 * b end

Exemplu:begin

wr it el nC 8 div 3 =wr it el nC -8 div 3 =writelnC 8 div -3»'writelnC-8 div -3- 'writelnC 8 mod 3-'writeln('-8 mod 3=', -8nod 3}.;:*. wri tel nC 8 mod -3- ', 8 nod (-3)) ; wri tel nC- 8 mod-3- ', -8 nod (-3 ));

end.

'4 - -■■ ' :' -ii .;• ■* . TOt ;>' V - -"

ilustrează aplicarea operatorilor div şi mod.Operatorii relaţionali uzuali », o (diferit de), <, <■ (mai mic sau egal), >, >■ conduc la

rezultate de tip boolean. Ambii operanzi trebuie să fie de acelaşi tip (integer, real , charsau boolean). Ca excepţie, se admite in locul unui operand de tipul real un operand detipul integer.

Pe tipurile integer şi real relaţia de ordine <* este cea uzuală;elementele tipului char sînt ordonate prin valorile asociate în codul ASCII, iarfalse < tiue. .

Operatorii not, and şi or se aplică asupra operanzilor de tip boolean, cusemnificaţia logică uzuală. în plus, operanzii pot fi şi de tip integer; rezultatul estetot de tip integer şi se obţine prin aplicarea operatorilor respectivi asuprareprezentării binare a operanzilor bit cu bit. Spre exemplu, not a este - 2, 6 ox 3 este7, 6 and 3 este 2.

Alte operaţii sînt implementate prin funcţii pnedefinite. Spre exemplu, abs (x)este valoarea absolută a lui x, iar sqr (x) este pătratul lui x. Tipul rezultatelor este acelaşicu tipul argumentului x, care poate fi integer sau real.

Următoarele funcţii: s in, co s, arctan, exp (exponenţiala de bază e), In,

sqxt (rădăcina pătrata) admit argumente de tipul Integer sau real, dar rezultatul estetotdeauna de tipul real. Predicatul odd (xţ.;, cu argument de tip integer ia valoareatrue dacă x este impar şi f alse în caz contrar. Trunchierea şi rotunjirea numerelor realese realizează prin funcţiile trunc şi respectiv round. Astfel, t runc (x) -n dacă x este detipul real, n număr întreg şi nix<n+l în cazul cînd x kosaun- l < x S n în cazul cînd x< 0. De asemenea, round (x) este trunc(x +0.5) pentru x o şi trunc ( x-o.5) pentrux<0.

Pentru tipurile integer, char şi boolean există funcţiile succ (succesor) şi pred(predecesor), cu semnificaţia uzuală. Funcţia bijectivă ord, cu argument de tip char iavalori de tip integer cuprinse între 0 şi 127 şi realizează codificarea caracterelor. Spreexemplu, ord('0')=48, ord(' 1')-49 etc., ord('A')=65, ord('B')-66 etc.. Inversaacestei funcţii este chr. De fapt, relaţia de ordine o pe mulţimea char este definită astfel:

a <- b dacă şi numai dacă ord (a ) <- ord(b).De asemenea, pred (c ) -chr (o rd (c ) -1) şi succ(c) =chr (o rd(c) +l). Toate aceste operaţii sînt prezentate sintetic în anexa 4.

, 8 div 3);, -8 div 3);

8 div (-3));-8 div (-3));

8 mod 3 ) :




Trebuie remarcat că tipurile de date sînt mulţimi finite, prin urmare cea mai mareparte a operaţiilor discutate anterior sînt doar parţial definite; spre exemplu, succ(maxint) , maxint+1, pred (- maxint -1) etc, nu au sens. în general operaţiile nu sîntdefinite pentru acele argumente care provoacă depăşirea limitelor impuse de tipurile dedate. Executarea programelor în aceste situaţii conduce la obţinerea unor rezultateincorecte. Evitarea acestor cazuri este în sarcina programatorului, deoarece numai o partea lor este sesizată şi semnalată de calculator.

Tipurile de date şi operaţiile predefinite prezintă o seric de abateri de laproprietăţile matematice cunoscute. Astfel, tipul integer nu este considerat o submulţime atipului rea 1, datorită modurilor diferite de reprezentare în calculator. Acest fapt estereflectat în programe prin forma diferită a literalelor cate desemnează elementele celordouă tipuri (spre exemplu, numărul real 1 se reprezintă prin 1.0).

Pentru a corecta această anomalie, operaţiile asociate tipului real sînt extinseastfel încît admit şi operanzi de tip integer; în acest caz, calculatorul realizează o conversiede la reprezentarea integer la cea de tip real. Spre exemplu, operaţia 1/2 este precedatăde conversia lui 1 în 1.0 şi a lui 2 în 2.0. Această conversie nu cade în sarcinaprogramatorului.

De asemenea, multe proprietăţi familiare ale operaţiilor nu se mai păstrează.Astfel, adunarea întregilor nu este totdeauna asociativă; spre exemplu, maxint+(maxint-maxint) dă rezultatul maxint, dar (maxint ♦ maxint) - maxint conduce la depăşirea limitelortipului integer. Totuşi, cu excepţia cazului în care apare depăşirea limitelor, axiomelearitmeticii numerelor întregi se consideră a fi satisfăcute pentru tipul integer, cu operaţiilepredefinite ataşate. Deoarece depăşirea este semnalată de calculator, se poate presupunecă un program care s-a terminat fată această eroare a executat operaţiile asupra tipuluiinteger respectînd proprietăţile matematice uzuale.

Situaţia este mai complicată în cazul tipului real, deoarece astfel de abateri potapare în absenţa fenomenului de depăşire a limitelor. Pentru ilustrare, să considerăm careprezentare a tipului real mulţimea {x | x-i o, XgXiXgX,• io*}. Fie elementele x-o,9554-IO0, y = 0,3000* 10° şi z - -0,2555*10° de acest tip. Dacă se evaluează în aceastăreprezentare expresia x ♦ (y + z) se obţine rezultatul corect 0.9999. într-adevăr, s = y+ +z = 0,0445 şi se reprezintă prin 0,4450*IO"1, iar x + s - 0.9999 şi se reprezintă prino,9999• io0. Pentru expresia (x + y)+z, suma s=x+y-i,2554 şi se reprezintă prin0,9995*10°. Aceasta este o aproximare a rezultatului corect Estimarea erorilor de calcul încazul tipului real cade în responsabilitatea programatorului.

Următorul exemplu ilustrează utilizarea variabilelor de tipurile prezentate mai sus,precum şi a operatorilor şi funcţiilor predefinite asociate.

Exemplu: vara : integer; "b ! real;c : char;d : boolean;

baginc := 'X';

7

26

•nd.

2.1.2. Tipuri de date enumerare

Un tip enumerare este o mulţime ordonată de valori specificate prin identificatori.Această specificare are forma

(identif icator_l, . . . , identif icator_n)

şi induce o relaţie de ordine astfel că

identificator_i < identificator_jj pentru i < j.

Spre exemplu, tipul predefinit boolean poate fi specificat şi ca tip enumerare printyp« boolean » (f al se , t ru e) ;

Elementele unui tip de date enumerare E sint identificatori ce constituie mulţimea

valorilor hii E. De exemplu, dacă se defineşte tipul type EN - (unu, doi, trei);

atunci elementele acestui tip sint unu, doi şi trei.Operaţiile aplicabile elementelor de tip enumerare sint cele relaţionale specificate

în paragraful anterior (<, < = etc). De asemenea, se pot aplica funcţiile predefinite succ,pred şi ord (astfel, ord (identif icator_l) - 0). Identificatorii ce apar în definiţia unui tip dedate enumerare urmează regulile obişnuite de valabilitate (vezi paragraful 4.5.4).

Exemplu:type luni - (i an , feb, mar, ap r, ma i, iun,

iu l, aug, sep, oc t, nov, de c) ; var L, X, Y, z :luni;

b : boolean; begin

writeln(ord(ian));L : - feb;X pred(L);

Y succ(X); bX < Y;writ eln( b, feb < oct, ian = dec)

end.Observaţie. Variabilele de tip enumerare nu pot apare in instrucţiunile de

intrare - ieşire; ele pot ti utilizate, spre exemplu, pentru indexarea tablourilor.

2.1.3. Tipul de date subdomeniu

b- 1.5; .-a- a +trunc(-b)♦round(b);a- a nod a diva■:♦ ord( 'X'); b-succ(a) + b /b -pred(succ(a));c-chr(ord(c)); d- (b <-b) andtrue;wri

te(a, b, c, d)

Un tip subdomeniu este o parte a unui tip deja definit. Tipul subdomeniu se poateintroduce pentru orice tip scalar în afară de real. Specificarea acestui tip se taceprin:

<constanta>..<constanta>

unde prin cele două constante se defineşte un interval ce conţine valorilesubdomeniului.

Un subdomeniu se poate indica şi ca un tip anonim asociat unor variabile în declaraţii de tipul:

var v__l, .. . , v_n : c_l. .c_2

Operatorii şi funcţiile prédéfini te care se pot aplica operanzilor de tip

subdomeniu sînt cele asociate tipului în care acesta este inclus. în cazulimplementării de faţă se poate defini un tip întreg fără senin care nu este unsubdomeniu al tipului prédéfinit integer. Acest tip are ca mulţime de valorinumerele întregi x, cu proprietatea o. <= x <= 65535, iar operaţiile cu careeste înzestrat sînt cele ale tipului integer.

Exemplu. ,type T =

"IO..10;natural = 0..65535; f ,:. _

m b : natural ; ^ ;:,c , a : a . . a ;

begina :» 0; a : = succ(pre d(a)) ;b 65535; b := pred(b) + 1;c := 'a ' ; d = 'd' ;writeln(a,b,c,d);c := chr(succ(ord (c))) ;d chr(pred(ord(d)));wiiteln(cd)

Observaţie. Toate tipurile de date simple sînt mulţimi finite şi ordonate de valori. Tipurile de date simple diferite de real se mai numesc şi tipuri ordinale. O caracteristică aacestor tipuri este prezenţa operaţiilor predecesor (pred) şi succesor (succ).

Pentru tipurile ordinale diferite de integer şi care nu sînt subdomenii ale acestuiase poate aplica funcţia bijectivă o rd care asociază valorilor tipului numerele naturale 0,1etc. Relaţia de ordine este cea indusă de funcţia ord şi este notată prin <.

2.2. Tipuri de date structurate

Tipurile de date structurate sînt agregări ale unor tipuri de date deja definite(simple sau structurare). Tipurile de date structurate care se pot defini în limbajul Pascalsînt următoarele: azzay, record, set şi file.

r&'* . ■- v -JidssîKv ei •-. ' .-ii-.- ;. ' 'ijtariti* *>fî5>ifsc-..-; jmm J«v« fi

9io ■: *j* .a ţs, ,.>a2.2.1. Tipul de date array (tablou)

•Re T un tip de date oarecare şi I un tip scalar diferit de integer şi real. T se

numeşte tip de bază iar I mulţime de indici. .Prin tip de date azzay cu indici din I şi elemente din t se înţelege mulţimea defuncţii A = {x | x :; I ——> T), care se notează (I -—-> T).

28

Elementele tipului azzay se numesc tablouri.Un tip azzay poate fi specificat prin

azzay ti] of T M

saupacked azzay [I] of T

Tipurile I şi T pot fi predefinite, anonime sau definiţia lor trebuie să preceadă, în textulprogramului, definiţia tipului azzay.

Dacă x este numele unei variabile sau constante de tip azzay, atunci elementulx(i ) se notează în programe prin x[ i ] .

Atributul packed indică în general cerinţa de optimizare a spaţiului de memorarepentru elementele tipului azzay.

Un caz special îl reprezintă tipurile de date string (şir de caractere), declarate prin

packed azzay [I] of char eo ■

Elementele de tipul string, avînd acelaşi număr de componente pot să apară îninstrucţiuni de atribuire şi de asemenea pot fi asociate cu operatori relaţionali ( =, O , < , > ,< = , >= ) .

za?

Elementele acestui tip pot să apară ca argumente în procedurile standard xead şiwrite.

Exemplu. Prin programul

var a, b: packed arxay [1..7] of char; begina :- ' lo nes cu ' ; b 'Popescu'; if a < bthen wr it el n(b) else wr it eln('eroare')

•nd.

se realizează atribuirea şirurilor de caractere ' lonescu', ' popescu' variabilelor a şirespectiv b, iar în urma executării instrucţiunii if se tipăreşte şirul de caractere ' Popescu'.

Trebuie menţionat că dacă a şi b ar fi fost declarate tară atributul packed atunci expresia a< b şi instrucţiunea writeln(b) nu ar mai fi avut sens, necesitind substituirea referirilorla variabilele a, b cu referiri la componente ale acestora.

Optimizarea spaţiului de memorie ocupat de elemente de tipul packedazray poate provoca accesul ineficient la componentele acestora. Din acest motiv,se recomandă efectuarea unei operaţii de despachetare a acestor elemente prin

invocarea procedurii predefinite unpack, înainte de prelucrarea elementelor lor.După această prelucrare, spaţiul de memorie ocupat de elementele respective poatefi din nou optimizat prin operaţia de împachetare apelînd procedura predefinităpack. Re i.

. . . .

A: array (m..n] of T;B: packed axzay [u..v] of T;

şin-m >= v-u. Dacăm <= i <= n, atunci prin operaţia de împachetare pack (A, i, B)tabloul B ia valorile Bt j] - A[ j- u+ i] pentru u <- j <= v, iar prin operaţia dedespachetare unpack(B , A, i ) tabloul A ia valorile A[ j ] -B[j+u-i ] , pentru i <= j <=i+vru.

Elementele tipului array pot apare în programe sub formă de constantestructurate (vezi anexa 3, diagrama 3.9). Spre exemplu, dacă A desemnează un




tip array definit prin type A = axzay [1..5] of integer, atunci A (1 , o, 2, -1, 3) esteun element al acestui tip.

Exemplu. Fie programul

type A - arxay [1. .5] of real ;B - axzay [- 1. .3 ] of rea l ; corist ca - A (1.1, 2. 1, 0. 1, 3. 1,

2E-1);cb - B(l .l, 2.1, 0.1, 3.1 , 2E- 1); Var x

: A;y : B;

i : 1. . 5 ;begin

writeln(ca[l] , cb[l]); X ;=ca; y := cb;fox i := 1 to 5 do

writeln(x[i] , y[ i-2])end.

Sînt definite aici două tipuri azxay (a si B) ale căror elemente reprezintă vectori,avînd cîte 5 componente numere reale. în timp ce componentele variabilei x şi aleconstantei ca sînt referite în program prin x [l] , . . . , x [5] şi respectiv ca [1], ca 12]etc., cele ale lui y şi cb sânt referite prin y [ -1] , t . . , y [3], respectiv cb [ -1], cb [ol,etc. Constantele ca şi cb, deşi conţin aceleaşi componente, sînt totuşi de tipuri diferite.

Exemplu.

type T - (ro şu , verde, al ba st ru ); vax e :

axxaytT] of integer; begine[rosu] := 1;e[succ (roşu) 3 '•" succ (e [r oşu ] ) ;e[albastru] := 3;writeln(e[verd e]) [valoarea 2}

end.


vax a, b : paeked axzay [i..1] of char;d : paeked azzay VI --2] of char ; c : char;

beginb[l] := 'a'; ['a' este constanta de tip char } d :=

'ab'; {'ab'este constanta de t ip string} writeln (b, d)[şiruri de caractere in write}end.

Trebuie subliniat că tipul char nu este identic cu tipul paeked axxay [1. .1] of char. Astfel, instrucţiunea b 1= 'a' este incorectă, deoarece b este variabilă de tipul şirde caractere, dar 'a' este constantă de tipul char. Din acelaşi motiv şi instrucţiunea b : - ceste incorectă.

în exemplele de mai sus, tipul de bază a fost de fiecare dată un tip prédéfinit (decisimplu). Considerăm acum un exemplu în care tipul de bază este el însuşi un tip structurat.

type N - axxay [1. .3] of real ;

type M = axxay [1.. 2] of N;

const C - M(N(1.1, 1.2, 1.3), N(2.1, 2.2, 2.3));

30



Elementele tipului M au cîte 2 componente reprezenund la rîndul lorvectori cu 3 componente.Fie o declaraţie de forma

type T = array[i ] of array[J] of B;

Elementele tipului T sînt funcţii avînd domeniul I şi codomeniul( J------>B). Tipul T este deci mulţimea de funcţii (i -------------> ( j------->B)). întremmţimileT şiu * (I x J----------------> B) există o corespondenţă bijectivă, deoareceunei funcţii f e T i se poate asocia o funcţie g e u, definită prin g (i , j ) - f ( i) (j ). înastfel de situaţii se poate folosi declaraţia în formă prescurtată: type U = array [I ,

J ] of B;

Trebuie subliniat că tipurile T şi u sînt considerate totuşi distincte. Com-ponentele unei variabile sau constante x de tipul T sau u pot însă să apară înprograme în oricare din formele x [i] [ j] sau x [i, j].

Forma prescurtată a declaraţiei de tip array se aplică şi în cazul general.Astfel, o declaraţie de forma &

:-{ - . .■ i - ; -

array [T_0] of array[T_l, T_k] of T

se poate scrie ca

array [T_0, .. . , T_k] of T Deci x [ i_o, i_i,. . . , i_k] are sensul x [i_p] [i_i, — , i_k].

Exemplu.

type B = array[1..3 ] of rea l;

T = array[1.. 2] of B; .H. U - «"«y 11. .2, 1. .3] of real; constCT -= T( B(1.1, 1.2, 1.3), B(2.1, 2.2, 2.3));

CU 4 U((l. l , 1.2, 1.3), (2.1, 2.2, 2.3) ); var VB : B;VT s T;VU : ti;

beginVT := CT;

VU := CU;writeln(VT[l] [2], VT[1,2]>;

(LINIEd.0, 2.0), LINIE(3.0, 4.0)), prin M 2RB ((1.0,2.0),(3.0, 4.0)), SOU prin M 2RC ((1.0, 2.0), (3.0, 4.0)).

Exemplu.

type M 2RC - azzay [1..2,1..2] of real; const M -

M 2RC((1.0, 2.0), (3.0, 4.0));{prima l inie: 1 , 2}

{s e scr ie de doua or i valoarea 1.2} VU : =U((10.1,10.2,10.3), (20.1,20.2,20.3));writeln( VU[l,2})

end.Constantele CT şi cu au proprietatea CT [ i] [ j] = CT[i, j] - CU[ i , j] = CU[ i ]

[j] pentru orice l <- i <= 2 si 1 <= j <- 3. Ele sînt totuşi de tipuri diferite; astfel,variabila VT de tipul T nu poate lua niciodată valoarea cu (de tipul u) dar poate luavaloarea CT.

Exemplu. Mulţimea matricilor pătrate de ordinul 2 cu elemente numerereale poate fi definită prin >

>r >

typa LINIE - azzay (1..2J of re al ; ' M 2RA -array [1. ,2] of LINIE;

sau prin"'• s:S.l.Si f iftH^. . hx&.№ S^;^r.a.-., v. • WI -'rVfcfc

type M 2RB = azzay [1..2] of azzay [1..2] of real ;

sau prescurtat printype M 2RC = azzay [1..2, 1..2] of re al ;

Deci matricea j1 2 | poate fi descrisă in programe Pascal prin M 2RA 3 4

(1.0, 2.0), LINIE(3.0, 4.0)), prin

32



{a doua iin ie: 3 , 4 }var 1: integer; beginfoz 1:=1 to2 do wri tel n( M [ l , l]){se scr iu elementele de pe di ago nal a p ri nci pal a}

end.

Exemplu. Acest program ilustrează utilizarea şirurilor de caractere: vazsir: packed azzay [1..4] of char; copie :azzay [1..4] of ch ar ; i: integer;

begins ir ' MASA ';unpack(sir,copie,1); {s ir es te despachetat in copie} copie[1]' . - • C i pac k(c opi e, 1, sir ); {in sir este impachetat cop ie}

writeln(sir) {scrie şirul 'CASA'}end.

2.2.2. Tipul de date record (înregistrare)

Re tipurile de date T x , . . . , Tm şi identificatorii distincţi s x , . . . , sm prin care sîntnotate proiecţiile canonice ale produsului cartezian 1\ x.. . x Tm. Spre exemplu, dacă m =2 şi (x ,y ) € Tx x T2, atunci s x(x, y) - x şi s3(x, y) - y.

Se numeşte tip de date record produsul cartezian Tt x... x Tn împreună cu cele moperaţii de selectare a componentelor, definite de proiecţiile canonice s x , ..., s„.Elementele unui astfel de tip se numesc articole. Forma sintactică a unei definiţii de tip

record este prezentată în anexa 3, diagramele 3.12-3.15. Elementele sj (x) apar înprograme notate prin x.s± . Există posibilitatea de a omite în această notaţie partea x.,prin utilizarea unei instrucţiuni with (vezi 3.2.4). Dacă unul din tipurile T 4 este de asemenearecord şi are proiecţiile ri, compunerea celor două proiecţii se notează prin s x . zy

Exemplu. Mulţimea numerelor complexe poate fi reprezentată în programe Pascalca un tip de date record. Astfel, prin programul

*

type C - record re, im : real end; var x : C;begin

x.re:=l.0;x. im:=2.0

end.

se defineşte tipul record cu numele c, avînd ca proiecţii funcţiile re şi im. Tipurile si T, sîntambele r eal. Partea reală şi partea imaginara a variabilei x apar în program în notaţiax.re şi respectiv x.im.


type data - recordluna : (ian, feb, mar, apr, mai, iun,

iul, au g, sep, oc t, noi, d ec); ziua ; 1..31;anul : integer end;

persoana = record

nume: packed array [1..10] of char; data n: data ____________________________22. Tipuri de date structurate_______________________27

•nd;var data_cr : data;p : persoana; begin

data_cr.lunaian;data_cr.ziua:-24;data_cr.anul:-1859;p.nuine:-'IONESCU p.data_n.luna:=feb;p.data_n.ziua:=2; p.data_n.anu1:=1947

•nd. în acest program este introdus tipul record cu numele data şi cu proiecţiile luna,

ziua şi anul. Tipul T x este un tip enumerare, T2 un tip subdomeniu, iar T, un tip predefinitVariabila data_cr are componentele data_cr.luna, data_cr.ziua şidata_cr.anul.

Exemplu. Poziţia unui punct material în spaţiul cu trei dimensiuni poate fi descrisă în funcţie de timp, prin elemente ale unui tip de date racord, în programul:

fcype POZIŢIA = racordx, y, z : real;timp : 0.. 3600

and;var punct, origine : POZIŢIA; begin

origine:=POZITIA(0.0,0.0,0.0,0);pun ct. x:=1.0 ; punct.y:= 1. 0; punct.z:=-1.0; pune t.timp:-19 89

and.Componentele variabilei punct se obţin prin proiecţiile x, y, z şi timp Şi

sînt următoarele: punct. x, punct.y, punct. z, şi punet. timp.Elementele unui tip de date record sînt reprezentate în programe

conform cu anexa 3, diagramele 3.9, 3.10. Astfel c(0.o, 1.0) şi C(1.0, 2.0) sînt articole ale tipului c reprezentind numerele complexe i şi respectiv 1 + 2i , data(aug, 2,1 988) este articol al tipului data iar persoana (' POPESCU ', da ta (i ul ,l , 1950)) aparţine tipului persoana.

Deci tipurile de date racord descriu elemente ale produsului cartezian T x

x . . . x T f f Produsele carteziene T pot fi descrise şi prin tipuri de date axray. Totuşi, tipul array nu este caz particular de tip record, pentru ^ = T, l <= i <=m, deoarece operaţia de selectare a componentelor în cazul tipului de date array

este mai generală decit în cazul tipului racord într-adevăr, indicele unui tip axxay poate fi orice tip scalar (diferit de integer şi

real) în timp ce proiecţiile canonice ale unui tip record sînt desemnate prin identificatori.Mai mult, un indice poate fi o expresie ce se evaluează în timpul execuţiei

programului dar identificatorii ce indică proiecţiile canonice sînt stabiliţi la momentul scrieriiprogramului.

Cazul particular de tip record obţinut prin T4 = T, i < = i < = m poate fidefinit ca un tip array, în care indicele este un tip enumerare. Astfel

type RT = zacordx, y, z : T

end;poate fi definit prin

type AT = array [(x, y, z)] of T;

■

34



Bineînţeles, operaţiile de selectare a componentelor se notează în mod diferit (v.xpentru v de tipul RT şi v[x] pentru v de tipul AT). De asemenea, indicele unui element detip AT se poate exprima prin expresii de genul pr ed ( y), succ(pred(y)), eto.

Există şi o formă mai generală de tipuri record prin care se definesc reuniunidisjuncte de tipuri de date. Acestea se numesc tipuri de date record cu variante. Elementeleunui astfel de tip sînt articole ce conţin o componentă prin care se identifică tipul din careface parte articolul. Această componentă apare explicit în definiţia tipului record cu variantedupă cuvîntul cheie case şi se numeşte identificator de variantă. Forma completă a uneidefiniţii de tip record cu variante este dată în anexa 3, diagramele 3.12-3.15. Ca şi în cazultipului record fără variante, numele proiecţiilor canonice ale aceluiaşi tip trebuie să fiedistincte între ele.

Exemplu. Prin definiţiile:

typevarianta - (a, b); « T - 1. .2; U - 2. .3 ; reuniune_di sj -record

case v : va ri an ta of a : (X : T; y : U) ;b : (Z : U; W : T)

and;

se introduce tipul reuniune_dis j . Elementele acestui tip se reprezintă în Pascal prin:reuniune_disj (a, 1, 2) reuniune_disj(b, 2 , 1)reuniune_disj(a, 1, 3) şi reuniune_disj(b, 2, 2)

reuniune_disj (a, 2, 2) reuniune_disj(b, 3, 1)ieuniune_disj (a, 2, 3) reuniune_disj(b, 3, 2).

Aceasta corespunde reuniunii disjuncte T x U U U x T. Se obervă că elementul (2, 2),comun celor două produse carteziene, apare dublat Operaţiile de selectare acomponentelor sînt desemnate de identificatorii distincţi între ei v, x, y, z şiw.

Exemplu. Să presupunem că se doreşte prelucrarea unor progresii geometrice şiaritmetice. Identificăm o progresie aritmetică prin elementul (t, r) e xeal x realreprezentind primul termen şi raţia. în mod analog, o progresie geometrică se reprezintăprin (u,q) € real x real. Rezultă că o progresie (aritmetică sau geometrică) este unelement al reuniunii disjuncte real x real U r eal x real . în limbaj Pascal, următorul

program ilustrează prelucrarea progresiilor:type progresie = record case modul : (ar , ge) of

ar : (t , r : real); ge : (u, q ; real)end;

var x: progresie; beginX:= progresie(ar, 1.0, 2.0); Iprogresie aritmetica}writ elnC termenul t_10- ', x.t+9* x.r); x:= pro gresi e(ge, 1. 0,2.0); {prog resi e geomet rica } w ritel n('termenul u_3 = ',x.u*sqr(x.q))

end.

Elementele acestui tip sînt articole de forma progresie (ar, t , r ) pentru

progresiile aritmetice şi de forma progresie(ge,u,q) pentru cele geometrice. Naturavariabilei x se determină după valoarea x.modul. Dacă aceasta este a r, atunci primultermen este x. t, iar raţia este x. r. Analog pentru cele geometrice.




Exemplu. Presupunem că se doreşte prelucrarea unor informaţii referitoare lastarea civilă a unor persoane. Aceste informaţii conţin numele persoanei, sexul, starea civilă(căsătorit, căsătorit şi divorţat, văduv, necăsătorit) şi, după caz, data căsătoriei sau datecăsătoriei şi a divorţului. Următoarele definiţii introduc tipurile de date necesare unei astfelde prelucrări.

type da ta = record luna : (i an , fe b, m ar , ap r, m ai , iu n,iul, au g, sep, oct, no i, dec) ; ziua :

1..31; anul t integerend;

type nume_persoana = racordprimul, ult imul:

packed аххауЦ. .10] of ch arend;type persoana = record

nume : nume__persoana;sex : (femeie, bă rb at ); ocase statu t : (căsă torit , necăs ători t,

di vo rţat , văduv) of căsătorit,văduv : (data_casatoriei: d at a) ;divorţat : (data_cas,

data_divort:data);necăs ător it : () end;

Următoarele articole: persoana(nume_persoana('Popescu ',' Ion '), bărbat, căsători t, data(ian, 2, 1940)),persoana (n ume_ pers oan a(' Ion escu ' , 'M ăr ia '), f em eie ,divorţat, data(mar, 2, 1950), data(oct, 10, 1960)), persoana"(mime_persoana('Popa 'Ion '), bărbat,necăsătorit) , aparţin tipului record cu variante persoana.

Asupra acestui tip de date se pot aplica următoarele operaţii de selectare: nume,nume.primul, nume.ul tim ul, sta tut , dat a_c asa tor iei .lu na, data_cas. lunaetc.

2.2.3. Tipul de date set (mulţime)

Unul din conceptele noi impuse de limbajul Pascal îl reprezintă tipul de date alecărui elemente sînt mulţimi asupra cărora se pot aplica operaţiile uzuale.

Fie т un tip scalar diferit de r ealjŞe numeşte tip eet cu tipul de baza т,mulţimea Р (T), formată din toate submulţimile lui т. Definiţia unui tip eet se face printr-odeclaraţie

set of Tsau

packed aet of T

unde prin т este desemnat tipul de bază.Spre exemplu, mulţimea P( {1 , 2 , 50}), este definită prin

declaraţia:

type S_l_50 = eet of 1..50;

36

Construcţia urmi element de tip eet se face în conformitate cu definiţiile:

<set> ::= [<lista_eleniente>] | [ ] <lista_elemente> ::= <element>1, <element> } <element> :: - <expresie> 1 <expresie> .. <expresie>

unde <expresie> desemnează o expresie (vezi 2.5) a cărei valoare aparţine tipului debază.

Spre exemplu, pentru a desemna mulţimea vidă se foloseşte notaţia (], iar pentrua specifica mulţimea {1, 2, 3, 4 , 5} putem folosi una din variantele:[1 ,2 ,3 ,4 ,5 ] sau 5] sau [1, 2 . . 3 , 4, 5] ete.

Operaţiile care se pot face cu variabile sau elemente de tip set sînt: reuniunea (+),intersecţia (*), diferenţa (-), rezultatul fiind de tipul set, şi egalitatea (-), inegalitatea (<>),incluziunea (<", >-), rezultatul fiind de tipul boolean.

Operaţia de apartenenţă a unui element la o mulţime se specifică prin cuvîntulcheie in, iar rezultatul este de tipul boolean.

De exemplu, dacă a, b, c smi variabile de tipul S_l_50, a fiind mulţimea vidă,b mulţimea [i , 2, .. ., 40 } şic = [30 , 31 ,. .. , 50} atunci expresia 30 in b arevaloarea t iue, reuniunea lui a cu b este desemnată prin a ♦ b, iar incluziunea mulţimii[i, 2, . ., 3 0} in b prin [1. .30 ] <= b.

Observaţie. Numărul de elemente ai multimii tipului de bază este limitat înimplementarea de faţă la 256 (dacă tipul de bază este o parte a mulţimii nume-relor întregi, atunci acesta trebuie să fie inclus în l o , 1, . . . . , 255}).

Exemplu. Prin execuţia programului

var A, B, C: aat of 0.. 5;

[A, B, C - m ul ţim i cu elemente numere natu ral e int re 0 si 5}begin

A : = [ 1. -3 , 5 ]; [ A conţine 1, 2, 3, 5}B := [5, 2 . .3 , 1 ]; [B conţine 1 ,2 ,3 ,5}C := []; [C - mulţ imea vida}

writ eln( A-B, A-B - C, A+B = A);writ eln( A+[4] = [1..5] , 3 in A, 1 in [1]) ;writeln(C <= A, [1,2] >= [1], [1,2] O [1])and. •

va fi scrisă de nouă ori constanta true.

Exemplu. în programul următor, mulţimile conţin valori ale unui tip enumerare.

type sta re - (in iţi ala , oarec are , fina la) ; . ■ .var •s: star e;

m: set of stare; beglns:- iniţ iala; m:= [s];writeln(iniţ ial a in m); {scrie true} m:= m + [finala];writeln (fin ala in ni); {scri e true] n i:= m - [ini ţiala ];writeln(init ial a in m) {scrie false}

end.

în paragraful 3.2.2.1 poate fi găsit un alt exemplu de utilizate a tipului de date set.

2.2.4. Tipul de date file (fişier)Fie T un tip de date şi EOF un element special care nu aparţine lui T. Mulţimea FT

= T* {EOF} se numeşte tip file (fişier) cu componente de tipul T. Elementele acesteimulţimi sînt şiruri finite şi ordonate de elemente din T,,urmate de EOF; un astfel de şir senumeşte fişier. Tipul T se numeşte tip de bază. Componentele fişierului se numesc

înregistrări sau articole.

Exemplu. Dacă T este tipul in teger, arunci următoarele şiruri:

<0, -l, EOF> <1,EOF>< E O F > • •'. ~ . ;

. . . .

sînt fişiere cu componente de tipul integer. în limbajul Pascal, un tip fişier se defineşte prin:

<ti p_f is ier >::= file of <t ip> | packed file of <t ip>

unde < tip> este tipul de bază. Atributul packed indică o compactificare a reprezentăriicomponentelor fişierului în memorie.

Cele mai uzuale operaţii asupra unui fişier sînt extragerea ("citirea") şi introducerea("scrierea") unei componente noi. Aceste operaţii se realizează prin procedurile predefiniteget sau read şi respectiv put sau write. înainte de efectuarea operaţiilor de scrieresau de citire este necesară o acţiune de validare a lor, numită deschidere a fişierului,realizată prin procedurile predefinite re set şi rewrite.

După tipul operaţiilor permise asupra componentelor, fişierele se clasifică în: fişierede intrare (este permisă numai citirea); fişiere de ieşire (este permisă numai scrierea); şifişiere de actualizare (sînt permise scrierea şi citirea). Operaţiile permise sîntfixate la deschiderea fişierului.

După medul de acces la componente, fişierele se clasifică în: fişiere cuacces secvenţial sau secvenţiale (accesul la componenta n este permis numaidupă ce s-a citit/scris componenta n-i) şi fişiere cu acces aleator sau direct (oricecomponentă se poate referi direct prin numărul ei de ordine în fişier). în lipsa altorspecificări, fişierele declarate în programele Pascal sînt secvenţiale şi de intraresau de ieşire.

Orice declarare de variabilă f de tip fişier cu tipul de bază T conduce ladeclararea implicită a unei alte variabile cu numele f * de tipul T, pe care o vom

numi variabilă asociată fişierului şi care se poate utiliza în programul Pascal, f *se poate considera ca o "fereastră" prin care se extrage / introduce o componentădin / în fişierul f . Aceasta este singura componentă accesibilă la un moment dat şise numeşte componentă curentă.

Exemplu. Prin definiţiile

type candidat = recordnume : packed array [1..30] of char; media: realend;

t_fc = file of candidat;var fc : t_fc;

se introduc tipul fişier t_f c cu componente de tipul candidat, variabila fişier f c

de tipul t_f c şi variabila f c * de tipul candidat.

38

Observaţie. în apelurile de procedură, parametrii actuali de tip f i le sîntcomunicaţi prin referinţă (vezi 4.6.2.2). Prin urmare, în declaraţiile de procedurăparametrii formali de tip file vor fi declaraţi ca variabili prin specificaţia var.

2.2.4.1. Fişiere secvenţiale 2.2.4.1.1.

Operaţii de intrare/ieşire

Fie definiţiile Pascal:

type FT=file of T;var f :FT; . ;

f,",:,, '.,,15* ■iâ'icy: prin care au fost introduse tipul fişier FT cu tipul debază T, variabila f de tip FT şi variabila f * de tipul T. Pentru a explicamecanismul operaţiilor asupra tipului FT, introducem notaţiile ce urmează. Fie<c1( c2,.. .c„,EOF> valoarea lui f, unde n e N şi Cj e T pentru i= i , . . . ,n sîntcomponentele fişierului f). Cînd n=o valoarea lu i f este <EOF>. Un fişier seconsideră totdeauna a fi secţionat în două părţi (partea stingă şi partea dreaptă),notate prin f „, respectiv f d, astfel încît f=f „ f d. Definiţiile lui f „ şi f d se vor preciza ladescrierea operaţiilor asupra fişierelor. Este posibil ca partea stingă f „ să nu conţină,nici-un.element; această situaţie se va nota prin f 3=e (e este elementul neutru la operaţia deconcatenare). Partea dreapta.f d conţine totdeauna cel puţin elementul EOF.

. Exemplu. Dacă variabila f este declarată prin

var f : file of in te ger ;şi are valoarea < o, -1, EOF>, este posibil ca f „ să aibă valoarea o şi în acest caz f d este<o, - l , EOF>. De asemenea, putem avea f„=<o> şi f d=<-i,EOF>, sau f 8=<o,-i > şi f D=<EOF>.

Definim funcţiile parţiale primu 1: FT ——> T şi r est: FT ^—> FT, unde FT este mulţimea fişierelor cu componente de tipul T prin:

pr imul (<c 1 ,c2 , .. .c„,EOF>) - c l ( daca n>l

•rest (<<=!,c2 , . . .c N,EOF>) « <c 2 , ■ . .c N,EOF> , dacan>l.

Se observă că aceste funcţii nu sînt definite în cazul n=o.s Observaţie. Valoarea variabilei f * asociate variabilei f de tipul fila este definită în felul

următor: dacă f = f 3 f d şi f d nu este <EOF>, atunci f" = pr im ul (f d); în cazul f d = <EOF> valoarea lui f - este nedefinită. Deci pentru f d * <EOF>, primul (f d) este

componenta curentă a fişierului.Exemplu. în cazul cînd f = <o, i,EOF> şi f s = <0>, f d = <-l, EOF>avemf* =

primul (<- l , EOF>) = -l; de asemenea, rest (<-1, EOF>) = <EOF>. Dacă f s =<0, -l> şi f d = <EOF> atunci f * este nedefinit

Descriem în continuare procedurile şi funcţiile predefinite care realizează operaţiileasupra tipului FT.

reset este procedura de deschidere a fişierelor pentru citire. Dacă f este un fişier,arunci după apelul de procedură reset (f ) , avem f B=o, f d=f. Vom nota acest fapt prin

reset(f){f 8=e,f d=f}.

în consecinţă, componenta curentă este f *=primul (f).Exemplu. Dacă valoarea lui f este <o, - l,EOF> atunci după reset(f) avem f

„=e, f d= <0, -1,EOF>; prin urmare f - = o. Notăm acest fapt prin

{f=<0,-1,E0F>]reset(f){f s=e, f d=<0,-l,EOF>}{f'=0}

Observaţie. Dacă fişierul nu conţine nici o componentă din T ( f -<EOF>, adicăfişierul este vid) atunci, după execuţia lui reset(f) , f" este nedefinită.

eof este o funcţie booleana care semnalează prin valoarea t rue sfîrşitul de fişier.

Are ca argument variabila f de tip fişier. întotdeauna are loc relaţia:

eof(f) ~ f D=<EOF>.

Se observă că dacă f =<EOF> (fişierul este vid), după deschiderea fişierului f prinreset( f)avem eo f (f ) =t ru e.

get este procedura de citire a unei componente din fişier. Apelul de procedurăge t( f) este permis numai dacă eof ( f) =f al se . Dacă f „=x, f d=y, atunci dupăexecuţia instrucţiunii ge t (f ) avem: f„ = x pr imul(y), f d - rest (y) . în consecinţă, f"= pr imul (rest (y) ). Vom nota acest fapt prin:

{not eof(f) , f„=x,f d=y}get(f>tf a=x primul (y), f d=rest(y)}lf A=primul ( f d) =primul(rest (y)}}

Se observă că dacă y=<c„,EOF> (adică f * are ca valoare ultima componentă afişierului f ) atunci după instrucţiunea g et (f ), f * este nedefinită şi eof (f ) are valoareatrue.

Exemplu.

var f; file of integer;

begin

{f=<0,- l ,EOF>}reset( f) ;ff„=e,f d~<0 , -l,EOF>}{f«=0}{not eof(f)}get(f);{f„=<0>, f d=<-l ,EOF>} {f-11 {noteof(f)} get(f);{f s=<0,-l>, f d-<EOF>}(f* nedef inită}

{eof(f); deci get(f) nu mai este permis}

Prelucrarea în succesiune a tuturor componentelor unui fişier f se poate realizaprin următoarea secvenţă de program: . . .

var f: file of T;

40

reset (f); {f" este pr ima componenta fl a lui f }while not eof(f) do begin....{p relu crare a componentei curente f *} get(f );{tr ecer ea lacomponenta următ oar e, dac a ex ist a}

end. . . " -Exemplu. Programul următor calculează media aritmetică a cîmpurilor

media din componentele fişierului f c:

type candidat - recordnu me: packed array [1 ..30 ] of char ; medi a: re alend;

var

fc: file of can did at; s: rea l;n: mteger ;

begins:= 0; n:= 0;reset(fc);while not eof(fc) do begin

n: = n + 1;s:= s + fc".media;get(fc)

end;if n <> 0 then write ('med ia ge neral a este =', s/n)

end.

Observaţie. Citirea unei componente care precede componenta curentăeste posibilă numai reluînd citirea fişierului de la început prin apelul re set (f ) .

rewrite este procedura de deschidere a fişierelor pentru scriere. Dupăapelul de procedură r ew ri te (f ) , f„=e şi f d=<E OF> (deci eof (f) =tr ue şi f =<E0F>, adică fişierul este considerat vid). Notaţie:

rewrite(f) {f .-a,f d=<E0F>}{eof(f)}

put este procedura de scriere a unei noi componente în fişier. Apelul deprocedură pu t( f) este permis numai dacă f d = <EOF>. Dacă f 8=x şi f *=c,atunci după execuţia instrucţiunii put(f) avem f„=xc, f d=<EOF>, iar f * este

nedefinită. Notaţie:{f e=x, f d -<EOF>, f=c)put( f)

{f,=xc, f d -<EOF>, f* nedef inită)

Exemplu, var f : file of integer;

begin

rewrite(f) ; {f„=e,f d-<EOF>) f*:=0;put( f) ;

{f 8 =<0>, f d-<EOF>l{ f nedefinită ; astfel f*i- f*- l este incorectă} f -:-- l ; put(f );

{f a =<0, -1> ,f d=<EOF>} ?f =<0, -1,E0F>}

end.

Observaţii.1.După apelul de procedură put (f ), f * rămîne nedefinită.2.Prin execuţia instrucţiunii put (f), valoarea lui f * se adaugă la sfîrşitul

fişierului ca ultimă componentă.3.O componentă deja scrisă nu se poate modifica decît prin rescrierea în-

tregului fişier, validată prin re wr it e.Schema de utilizare a acestor proceduri pentru crearea unui fişier este

următoarea:var f: file of T; . . . begin

rewrite(f);repeat

{atr ibuie valoare lui f * }put(f)

until ul ti ma componentă a fost ad ău ga tă ' end.

42

43 2. Tipuri de date, variabile, constante, etichete, expresii

xead şi. «x i ta smt proceduri de citite, respectiv serios, a valorilor unor variabile,respectiv expresii de tipul T în fişier. Ele admit un număr variabil de argumente al. . . . , amde tipul T. Apelul

read(f, al, .. ., am )

este echivalent cu secvenţa:

al:-f\- get (f);...,-am: =f\- get(f)Apelul

write(f, al , . . . ,am) este

echivalent cu secvenţa:

f* := al ; put(f ); .. .; f* :-am; put(f)

alome este o procedură prin care se interzice accesul la componenteleunui fişier f ptnă la un nou reset sau rewrite (se spune că "închide" fişierul). Aceastăprocedură nu există în limbajul Pascal standard. De notat că fişierele sînt automat închise laterminarea execuţiei programului sau cînd apar ca argumente într-un nou reset saurewrite.

Utilizarea procedurilor de intrare/ieşire este ilustrată în exemplul 1 din paragraful3.3.

Sintetic, operaţiile de creare şi citire a unui fişier secvenţial sînt prezentate înschema următoare:

-> rewrite(f)

—>—1. _____f

_____1

■

ţ—ţ---------1

put(f)1

i—>—

*—/--------

get(f)

I

h-<->

2.2.4.1.2. Fişiere text

In Pascal, tipul text este predefinit ca un caz particular de tip fila. Prin declaraţia

var f : text;

se introduce fişierul f de tip text şi variabila asociată f * de tip char.

Vom numi text valoarea (conţinutul) unui fişier de tip text. Conceptual, textelesînt divizate m linii; modul efectiv de delimitare a liniilor nu este relevant pentru utilizator şi

revrite(f) <-—

<-r

i

reset(f)

depinde de implementare. Pentru discuţia care urmează, considerăm tipul char c extinscu un caracter numit "sfîrşit de linie" şi notat eol (eol £ C).FieC'=cU {eol}. Atoneitipul text este mulţimea C * {EOF}, ale cărei elemente sînt şiruri de caractere (inclusiveol) terminate prin EOF. O linie este un şir <c l ,.. .c„, eol > cu n>- o şi c4 e C. Liniacare conţine componenta curentă se numeşte linie curentă. Cititorul poate tace analogie cutextul unei cărţi, în care trecerea la nudul următor este marcată prin eol.

Evident, operaţiile de intrare/ieşire descrise în paragraful precedent rămîn valabilepentru fişiere text

Observaţie. Dacă primul (f d)-eol atunci valoarea lui f * este spaţiu. Deci lacitirea sfîrşitului de linie (caracterul e ol) acesta este transformat în spaţiu.

Exemplu. Prin execuţia programului

var f: te xt ;c: char;

beginreset(f);while not eof(£} do begin

read(f, c); {adică c:=f*; get(f);} write(c)end;writeC . ')

and.

cu fişierul f avînd conţinutul <a,b,eol ,c,eol,EOF> se afişează rezultatul: ab c

Cele două spaţii corespund caracterelor eol din fişierul f.

în plus, utilizatorul dispune de operatorii predefiniţi eoln, writeln şi readln pentrumanipularea liniilor de text.Reamintim că un tip de date este alcătuit dintr-un domeniu (mulţime de

valori) şi o mulţime de operaţii. Prin urmare, alte tipuri declarate, prin fila of char nu sînt identice cu tipul te xt , deoarece au domenii diferite (C'* {E OF }pentru text şi c* {EO F} pentru fila of char) şi operaţii diferite (re adl n,writ eln şi eoln pot fi aplicate numai fişierelor text). Spre exemplu,programul j j j .

var i : fila of char;begin

reset( f) ;readln(f)esteincorect

eoln este o funcţie booleana care semnalează prin valoarea t rue sfîrşitul de linie.Are ca argument o variabilă de tipul text . întotdeauna are loc relaţia:

eoln(f) «* (primul(f d) =e ol) sau eof (f)

writeln este o procedură prin a cărei execuţie se marchează sfîrşitul liniei curentea fişierului text. Apelul de procedură wi i te In ţ f) este permis numai dacă f d= <E O F>.Dacă f B-x, atunci după execuţia instrucţiunii writeln (f) avem f„-x eol.

Observaţii.1. în implementarea descrisă, la crearea unui nou fişier text, lungimeamaximă a unei linii este de 132 caractere (n <= 132); ea poate fi modificată prinspecificarea comutatorului " /VAR:n" în apelul rew rit e (vezi 2.2,4.2).




2. Spre deosebire de fişierele declarate fila of char, scrierea într-un fişiertext f trebuie să se încheie printr-o instrucţiune writeln(f); în caz contrar, ultima liniede text nu este totdeauna scrisă în fişier din motive dependente de implementare.

xeadln este o procedură prin care la citire se avansează la începutul linieiurmătoare celei curente. Apelul de procedură readln(f) este echivalent cu secvenţa:

while not eo ln (f ) do ge t( f) ;get(f)

Astfel, f * primeşte ca valoare primul caracter din linia următoare celei curente. Dacă liniaurmătoare este vidă (constă doar din eol), atunci f * primeşte valoarea spaţiu şi eoln(f)

ia valoarea true.paga este o procedură cu următorul efect: textul scris în fişierul f după apelul

page (f) va apare pe o nouă pagină atunci cînd conţinutul fişierului f este imprimat Defapt, apelul page(f) are ca efect inserarea în text a caracterului ff ("form feed"),interpretat de imprimante drept comandă de salt la pagină nouă.

Utilizarea fişierelor t ext este ilustrată în exemplul 2 din paragraful 3.3.Exploatarea caracter cu caracter a fişierelor text este greoaie atunci cînd secvenţe

de caractere din text trebuie interpretate ca formînd date de tip integer, r ea 1,boolean, şir de caractere; conversia între formatul extern şi reprezentarea internă aacestor tipuri ar cădea în sarcina programatorului (vezi exerciţiul 11 din capitolul 3). înconsecinţă, procedurile predefiní te read, readln, write, writeln sînt extinse într-unmod nestandard, admiţînd un număr variabil de argumente de tipurile char, integer,

real, şir de caractere ("packed array of char"). Mai precis, fie f un fişier text şi a, al, ...,am variabile de tipurile menţionate mai sus.Apelul xaad (f, a) are următorul efect:

- dacă este de tip integer sau real , atunci este citit întregul şir de caracterecare reprezintă valoarea întreagă sau reală şi convertit la reprezentarea internă respectivă.

în text, datele numerice trebuie separate prin spatii sau eol. Spatiile sau eol dinaintea uneivalori numerice sînt ignorate. Şirul de caractere care reprezintă valoarea numerică seconformează sintaxei constantelor numerice de tipul respectiv.

Exemplu. Fie programul:

var i : integer; beginwhile not eof dobegin

read(i); write(i)and

cod.

prin care sînt citite şi scrise numere întregi pe fişierele text input şi output (veziparagraful 2.2.4.1.3). Trebuie observat că la introducerea datelor, ultima cifră a ultimuluinumăr va fi urmată imediat de sfîrşitul de fişier (caracterul CTRL/Z); în caz contrar, dupăultimul număr citit, condiţia eof este falsă; prin urmare, se execută încă o datăinstrucţiunea r ead(i ) . Deoarece în acest moment nu mai există numere întregi în fişierulinput, va fi semnalată eroare.

- dacă a este un şir de caractere, atunci se citesc atîtea caractere cîtesînt necesare pentru completarea şirului. Dacă înainte de executarea instrucţiunii

read(f ,a) condiţia eoIn (f) este true, atunci şirul a este umplut cu spaţii; de

■

IM •-,*■ ••.ti ■

asemenea, dacă în timpul citirii eoln ( f) devine true, atunci restul şirului estecompletat cu spaţii; în ambele cazuri caracterul curent rămîne eol.

Exemplu. Dacă executăm programul. .

var f: text;a: packed array [1..3] of char;C ! char;

beginreset(f);read( f, a) ; {cara cteru l curent este eol} write ln(a ,eoln(f));read (f, a); {carac teru l curent nu s-a modifi cat

deoarece a est e s ir }writeln(a, eoln(f));read (f, c); {cara cteru l curent s-a modif icat

deoarece c este char}wziteln(c, eoln(f)); read(f , c);writeln(c, eoln(f))

cu fişierul f avind următorul conţinut

<l,2,eol,3,4,eol,EOF>

atunci rezultatele afişate sînt:

12 TRUE TRUEFALSE ■-•

3 FALSE

Apelul xead(f, al,..., an) este echivalent cu secvenţa:

rea d(f , a l); ... ; r ead (f, am) Apelul xeadln(f , al,..., am) este

echivalent cu secvenţa:

re ad (f , a l, .. ., am); re ad ln (f ) Fie f un fişier text şi a, al ,. .. , am

argumente de una din formele:

ee:i x

undea este o expresie de tip char, integer, real, boolean sau packed azray of char (şirde caractere), a cărei valoare trebuie scrisă în fişierul f în format extern; i j şi i2 sînt expresiide tipul integer, numite specificatori de format

i, specifică prin valoarea sa absolută numărul minim de caractere ce vor fi folositela scrierea valorii lui a în fişierul f; dacă Sînt necesare mai puţin de I i j | caractere, atunciforma externă a valorii lui a este completată cu spaţii la stingă pînă la | i t | caractere. Dacăo valoare numerică necesită mai mult de J it | caractere, se scriu atîtea caractere cîte sîntnecesare (valoarea numerică nu este trunchiată). Şirurile de caractere şi valorile booleenesînt trunchiate la primele | i11 caractere. Valoarea implicită a lui it este dependentăde implementare şi de tipul expresiei«:

Tipul l ui. a | i i implicitinteger 1 7real 13char i 1packed array of char | lungimea şiruluiboolean 1 5

2.2. Tipuri dc datestructurate

43

O valoare ij. negativă are sens numai în cazul cînd e este de tip integer, packedazzay of char sau char: întregii sînt scrişi în baza 8, tar scrierea şirurilor de caractere(caracterelor) este suprimată

i, are sens numai în cazul cînd expresia a este de tip real şi specifică prin valoarea saabsolută numărul de cifre care urmează punctului zecimal în scrierea valorii lui a în virgulă fixă.

în lipsa lui i2, valoarea lui a se scrie In virgulă mobilă (cu factor de scală). Exponentul este formatdin litera ' E ', semnul ' ♦' sau ' -' şi două cifre zecimale. Dacă i2 are valoare negativă, atuncivaloarea expresiei a este scrisă în virgulă mobilă.

Apelul write(f ,a) are următorul efect: valoarea expresiei a din argumentul a estescrisă in fişierul f de tip text, convertită la formatul extern conform specificatorilor de format i lf i2.

Apelul wzite (v, al,..., a») este echivalent cu secvenţa:

write(f, al ); .. .; wr it e( f, am ). Apelul «zitain(f, al,..., an) este echivalent

cu secvenţa:

wzi te (f , al , .. ., am); wiiteln(f) . Exemplu.Programul var

i : integex; r: real;si packad array [1 ..10] of char; bsboolean;

begini : - 323;r:« 3.1415926;{r primeşte valoarea 3.141593} s:= 'specificat'; b:=true;writelnCi-', i , ' ; ' , i :4, ' ; ' , i:2, ' ; ' , l:-4);writelnCr-', r , r:10, '; ', 1:4, ' ; ' , r:4:6,

' . i i * .

writeln('r=', r:10:3, ' ; ' , r:10:8, ' ; ' , r:10:-5); writelnCs-', S,'; ',.s:12, '; ', 3:8); writeln('b=', b, ' ; ' , b:3, ' ; ' , b:7)

and.

afişează rezultatele:

i- 323; 323;323; 503r- 3.141593E+00;3.141593E+00;3.141593E+00,-3.141593;1= 3.142;3.14159300;3.14159E+00s=specificat; specificat;specific ' <b- TRUE;TRU; TRUE2.24.U. Fişierele standard input şi output




Există două fişiere text cu numele input şi output, predeclarate astfel: var input, output:text; şi asociate implicit cu mediile standard de intrare şi respectiv ieşire ale sistemului decalcul. în implementarea descrisă, ambele stnt asociate cu terminalul utilizatorului (TI:).Dată fiind utilizarea lor frecventă, numele lor sînt luate ca valori prin lipsă ale numelui de fişiertext în operaţiile de intrare/ieşire. Prin urmare, apelurile următoare sînt respectiv echivalente:

read(a l , . . . , a„) cureadln (a i y . . . , a„) cureadln cuwrite (ai, a j cuwriteln (a l f . . . , a„) cuwriteln ; cu

read ( input, a x , . . . , am)readln(i nput , a1#. . . , 'ajreadln(input)write(output, a l f a„)writeln (output, aw . . . , a m)writeln(output).

în cazul folosirii acestor fişiere, standardul prevede specificarea lor în lista deparametri din antetul de program. în implementarea descrisă, acest lucru nu estenecesar. Fişierele standard input şi output sînt deschise automat la începutul execuţieiprogramului. Apelul reset (input) este echivalent cu readln, iar r ewr i te (ou tput)termină linia de text curentă. Apelurile re set (o u tpu t) şi rew ri te ( in put ) sîntincorecte.

I

Observaţii.1. La deschiderea pentru citire a unui fişier text asociat cu un

terminal interactiv (de exemplu input asociat cu i i : ) , variabila asociată (înexemplu input*) primeşte valoarea spaţiu, iar funcţia eoln primeşte valoarea

false, fără să se transmită efectiv vreun caracter.2. Conform standardului Pascal, variabilele input şi output trebuie con-siderate variabile globale dacă apar ca argumente în antetul de program. în implementareadescrisă, antetul de program este ignorat şi variabilele input, output sînt predeclarate cavariabile globale. Deci la nivelul global, programatorul nu poate declara o variabilă sau oprocedură cu numele input sau output.

2.2.4.2. Asocierea fişierelor Pascal cu fişiere externe

Fişierele existente independent de programul Pascal se numesc fişiere externe.Acestea sînt recunoscute şi gestionate de sistemul de operare. Există posibilitatea deasociere a fişierelor Pascal cu fişiere externe. Standardul Pascal prevede ca aceastăasociere să se realizeze prin specificarea fişierelor externe ca argumente în antetul deprogram. în implementarea descrisă, antetul de program fiind ignorat.

_______ 2.2. Tipări de date structurate 45

asocierea fişierelor externe se realizează prin extensii ale procedurilor zeset şirewrite. Restul paragrafului descrie aceste extensii, in apelurile:

reset(f, n, c, i)rewrite(f, n, c, i)

argumentele f , n, c , i au următoarea semnificaţie: f este ovariabilă de tip file.n (opţional) este o variabilă sau constantă de tip şir de caractere (packed •zzay

of char) şi conţine numele fişierului extern asociat cu fişierul Pascal f. Prin lipsă, fişierul




extern are numele şi extensia vide; el este şters din catalogul curent la terminareaexecuţiei programului.

c (opţional) este o variabilă sau constantă de tip şir de caractere şi conţine altecîmpuri ale specificaţiei de fişier extern neincluse în n. Atît în n cît şi în c se pot specificaopţiuni de intrare / ieşire relative la fişierul «etern asociat O listă completă a opţiunilor deintrare / ieşire apare în [Pa81]. Aici le descriem pe cele mai des utilizate:

/SEEK : permite apelul procedurii seek (vezi 22.4.3) în programul Pascal pentruexploatarea unui fişier în acces direct

/WR: permite operaţii de citire şi scriere într-un fişier secvenţial, indiferent demodul de deschidere. Opţiunea /WR poate fi utilizată la adăugarea unei componente noi lasfirşitul unui fişier extern deja existent la începutul execuţiei programului.

/si m: n specifică numărul de blocuri de 512 bytes ce se vor aloca fişierului creat

prin rewrite./VARm: fişierul va avea înregistrări de lungime variabilă, cu lungimea maximă

n.i (opţional) este o variabilă de tip integer, în care procedurile reset, r ewr i te

întorc dimensiunea fişierului în blocuri de 512 bytes, sau valoarea -l în cazul unei erori ladeschiderea fişierului.

Exemple:1. Prin instrucţiunea

rewrite(fi s, 'Fi s.D AT' )

se deschide pentru scriere fişierul Pascal f is asociat cu fişierul extern Fis .DAT dincatalogul curent

2. Prin instrucţiunea

rewrite(f,'FILEl/SEEK',*.DAT/SI:2')

se deschide fişierul cu acces direct f asociat cu fişierul extern FILEI . DAT, căruia i sealocă 2 blocuri.

3. Prin instrucţiunea

rewrite(f, ,'/SEEK ')

se deschide fişierul cu acces direct f.4. Prin instrucţiunea

rewrite(output,'LPO:')

se asociază fişierul standard output cu imprimanta LPO: a sistemului de calcul. Observaţii.1. La deschiderea prin reset a unui fişier asociat cu un fişier extern pe disc

fără specificarea versiunii, sistemul de operare alege dintre toate fişierele cu numelespecificat în xeset existente în catalog pe cel cu versiunea maximă.

2. La deschiderea prin xewr i te a unui fişier asociat cu un fişier extern pedisc tară specificarea versiunii, sistemul de operare creează un fişier cu versiunea cu 1 maimare decît versiunea maximă a fişierelor cu acelaşi nume existente în catalog în acel

moment: dacă un astfel de fişier nu există, numărul de versiune este 1.

2.2.4.3. Fişiere cu acces direct

Acest paragraf se referă în întregime la implementarea Pascal Oregon.Prin declarare, fişierele cu acces direct nu se deosebesc de cele secvenţiale.

Diferenţierea între cele două categorii de fişiere se realizează la deschiderea fişierului.Pentru fişierele cu acces direct este obligatorie specificarea opţiunii ' / S E E K ' în apelulprocedurilor reset şi rewrite (vezi 2.2.4.2). Indiferent de modul de deschidere, un fişiercu acces direct este fişier de actualizare. Fişierele cu acces direct se pot asocia cu fişiereexterne numai pe disc. Componentele unui fişier cu acces direct se consideră numerotate

începînd cu 1.Operaţiile, de intrare / ieşire pentru fişiere cu acces direct se execută prin apelul

procedurilor;şi funcţiilor standard prezentate în 2.2.4.1.1. Accesul direct la componentelefişierului f se realizează schimbînd componenta curentă prin apelul procedurii nestandardseek. Mai precis, fie f=<c1#.. .f n , EOF> un fişier şi i o variabilă sau constantă de tipinteger cu valori în domeniul 1. . n. După apelul seek (f, i) , componenta cu numărul deordine i a fişierului f devine componentă curentă şi valoarea ei se regăseşte în variabila f *. Dacă f =<EOF> (fişier vid) sau dacă valoarea lui i iese din domeniul 1. . n atunci funcţiaeof (f) primeşte valoarea true.

în consecinţă, se pot scrie secvenţe de program pentru:1. Scrierea secvenţială într-un fişier cu acces direct, începînd cu componenta i:

var f: file of T;

rewrite(f, , ' /SEEK');

seek(f, i) ;

while . . .{exista d ate de scris} do begin . . . .{calculează a}f*:-a; put(f) {sau write(f,a)} ead

. . .

2. Citirea secvenţială dintr-un fişier cu acces direct, începînd cu compo-nenta i.

reset(1 , , ' ISEEK') ;

seek(f, i) ;while not eof(f) do begina:=f*; get( f) ; {sau read(f .a) ;} . . .{prelucrează a} •nd . . .

3. Actualizarea componentei i:

reset(f'/SEEK');ii: i

seek(f, i) ; a:-f; . . .{modif ica a}seek(f, i) ; f .*:-a; put(f);

•Jii . . . : : i

Exemplul 3 din paragraful 3.3 ilustrează modul de utilizare a fişierelor cu accesdirect.

•:




23. Tipul de date pointer (referinţă)

Mecanismul de declarare a variabilelor prin definiţii var desemnează variabileleprin identificatorii asociaţi. Numărul de variabile şi identificatorii lor sînt reflectaţi de textulprogramului. Ele pot fi utilizate cu destinaţia de variabile pe toată durata execuţiei blocului

în care au fost definite (vezi pentru detalii 4.3.3). Există situaţii în care numărul necesar devariabile de un anumit tip nu este acelaşi pe toată, durata execuţiei unui bloc.

Să presupunem că se doreşte prelucrarea unui vector cu n componente de tipulinteger. Dacă n este cunoscut în momentul scrierii programului (sau cel puţin valoarea samaximă N) atunci se utilizează o declaraţie de forma vax v : azray [1..N] of integer;

unde N este o constantă (literal sau identificator de constantă). Pe toată durata execuţieieste rezervat un spaţiu de memorare necesar pentru toate cele N componente ale lui v.

Ar fi mai avantajos, din punctul de vedere al ocupării spaţiului de memorie, unmecanism de definire a numărului de componente in momentul execuţiei. Spre exemplu,dacă de fiecare dată cînd se generează o nouă componentă a vectorului existăposibilitatea de a crea o nouă variabilă de tipul integer în care să fie reţinută valoarea noiicomponente, atunci spaţiul de memorie alocat este cel strict necesar.

Sîntem prin urmare în prezenţa unui fenomen de generare dinamică de variabilede un anumit tip.

Fie T un tip de date. Ptintr-o definiţie de forma

type PT - "T;

se introduce un nou tip PT care este o mulţime de variabile de tipul T. PT se numeşte tipde date pointer. O variabilă de tipul PT declarată prin:

var p : PT;

ia ca valori variabile de tipul T. Variabila de tipul T desemnată de p la un anumitmoment al execuţiei se notează cup*. Atribuirea unei variabile de tipul T lui p se face prinprocedura predefinită nev. Variabila p* obţinută prin instrucţiunea new (p) este distinctăde toate variabilele de tip T create anterior. Executarea repetată a instrucţiunii new (p)conduce la crearea unui şir vL, .. .. .. .. v„ devariabile de tipul T. Numai ultima variabilă creată, v„, este referită prin p *.

Procesul dinamic de creare de variabile de un anumit tip T presupune şi existenţaunui mecanism de distrugere a lor şi de eliberare a spaţiului de memorie ocupat Acestlucru se realizează prin utilizarea procedurii predefinite dispoae.

' După executarea unei instrucţiuni dispose (p), variabila p* devine nedefinită Deasemenea, p nu este definită atunci cînd nu s-a executat nici o instrucţiune new (p).Dacă dorim ca p să nu indice nici o variabilă, atunci îi asignăni valoarea constanteipredefinite nil.

Dacă y este o variabilă de tipul T, p poate lua ca valoare această variabilăprintr-o instrucţiune de atribuire p: «ref (v).

Exemplu:varp : * integer; x , y :integer; begin

p := nil; {p* nu exis ta in aces t moment, dar p ar e valoareani l !

new(p); {a fost creata o variabila p* de tip intreg} p* := 0;writeln(p*); { scrie numărul 0 }x :~ 1;y :- 2;p : - ref(x);writeln(p'); { scrie numărul 1 } p := £ef(y);writeln(p*); { scrie numărul 2 }dispose(p); { p* nu mai exista in acest moment iar valoarea lui p este

nedefinita}end.

Alte aplicaţii ale tipului de date pointer sint prezentate în legătură cu tipurile dedate recursive în paragraful următor.

2A. Tipuri de date recursive

Tipurile de date pointer oferă posibilitatea de a reprezenta în programe Pi.si.iildate a căror definiţie este recurşi vă.

O bună ilustrare se obţine în cazul reprezentării grâturilor orientate. Săconsiderăm mai înrîi gtafuri de forma unor liste

1-------> 5 -------> 7

cu nodurile marcate prin cifre zecimale, definite astfel în notaţie BNF:

<lista> :;= <element> <lista> | e

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

Caracterul recursiv al definiţiei este dat de prima regulă. Precizăm că e esteelementul neutru pentru operaţia de concatenare. Deoarece o listă diferită de • estedement al produsului cartezian <element> x <lista>, este sugerată folosirea tipului dedate record.

Aceasta ar conduce la utilizarea numelui de tip lista pentru propria sa definiţie,ceea ce este interzis în limbajul Pascal. Este posibilă însă depăşirea acestei interdicţii prinintermediul tipului de date pointer.

O listă este identificată prin primul ei element şi prin sublista ce urmează acestuielement în limbajul Pascal aceasta revine la definiţia

type legătura - * lista; type lista= record

element : 0 .. 9;sublista : legătura

•nd;

Se observă că în definiţia tipului l ista se foloseşte tipul pointer legătura,definit la rindul său pe baza tipului l ista. Această circularitate este consecinţarecurşivităţii definiţiei listei.

Mai mult, utilizarea tipului l is ta precede definiţia lui (aceasta este o excepţie, îngeneral utilizarea unei entităţi se poate face după ce aceasta a fost definită).

O listă va fi reprezentată în programe Pascal printr-o variabilă de tipul pointerdeclarată prin

vai 1 : legătura;

http://pi.si.iil/

http://pi.si.iil/

Efectul execuţiei instrucţiunii new(l) este crearea unei variabile 1* de tipull is ta. Dacă 1 - nil, atunci se consideră că lista 1A este vidă (adică a).

Exemplu. Lista l -----------> 5 -------> 7 descrisă prin arborele

<lista>/ \

<element> <lista>I / \

1 <element> <l is ta >I / \

5 <element> <l is ta >

7 a

poate fi obţinută prin următorul program:

type legătura - "l is ta ; li sta= record

element : 0.. 9;subl is ta : legătura

and;

var.p,g ,r t legătura; begin

new (p);q: = p; q* .element:= 1;

r := q; new(q); r* .subl ista:- q; q*.element:= 5; r := q; new(q);rA .sublista:= q; q*.element:- 7; q*.subli sta:= nil;

and.

Prezentăm un alt caz, cel al arborilor binari de forma2/ \

1 3/ \

definiţi prin

<arbore> i : = (<nod> , <arbore>, <a rbor e>) | <nod> | a <nod>::■= 0 | l | 2 | 3 | 4 | 5 | 6 r 7 | 8 | 9 .

ies--, -

Deoarece un arbore este fie în formă complexă, adică un nod urmat de un(sub)arbore sting şi altul drept, fie în formă simplă, adică un nod, el este un element alreuniunii disjuncte de tipuri <nod> x <axbore> x <arbore> U <nod>. De asemenea, elpoate fi vid, adică a. Aceasta sugerează utilizarea tipurilor record cu variante. în limbajulPascal acest arbore poate fi obţinut prin programul:

type legătura - *arbore; typearbore - record

case fel : (complex, simplu) of complex : (nod :0..9;

a_sting,a_drept : legătura); simplu

: (nod_terminal : 0. .9 )end

and;var p, q, st ,d r: legătura; begin

new (p) ;q:- p;q* .f el :- complex; q*.no d: = 2 ; new(st ); new(d r) ; q*.a_sting:- st ;q*.a_drept: - dr; q:= st ;

q' .fe l:- sim plu ; q *.nod_terminai:= 1; q:= dr;q* .fe l:« complex; q*.no d:= 3; new(st) ; new(dr); q*. a_s tin g:-

st ; q*.a_drept:= dr; qs= st ;q*.fel:- s implu; qA .nod_terminai:- 7 ; qt - dr;

q*.f el:= complex; q'.no d:- 4; new( st); dr:«nil; q*.a_st ing:- st ; q*.a_drept:= dr; q:-St;

q*.fel:- s implu ; q*.nod_termi nai:- 5;•ud.

Alte ilustrări ale tipurilor de date recursive se găsesc în exemplul 4 din paragraful3.3 şi în exemplele 5, 6, 7 din paragraful 4.5.4.

2.5. Expresii

în timpul execuţiei unui program pe calculator, instrucţiunile sale prelucreazăelemente ale tipurilor de date predefinite (integer, real, etc), sau ale celor definite deprogramator (array, racord etc.). Aceste elemente sînt referite prin intermediulvariabilelor şi constantelor şi asupra lor sînt aplicate anumite operaţii. Variabilele sîntidentificatori ce apar într-o declaraţie var sau sînt referite prin intermediul unei altevariabile de tipul pointer (vezi paragraful 2.3 pentru detalii). Constantele sînt numere, şiruride caractere (vezi 1.2), constante structurate (vezi anexa 3, diagrama 3.9), constantepredefmite (m ax in t, nil, true, false) sau identificatori declaraţi prin const.Numele operaţiilor, paritatea şi sensul lor pot fi de asemenea predefinite ca în cazul ♦, -,div, mod pentru tipul integer etc, sau definite de programator, ca în cazul numelorproiecţiilor canonice ale tipurilor record şi ale operaţiilor introduse prin funcţii şi proceduri

(vezi capitolul 4).Se poate deci considera că execuţia unui program se desfăşoară în cadrul unuimodel logic de signatură dată, al cărui domeniu D este format de tipurile de date.Signatura acestui model cuprinde mulţimea simbolurilor operaţiilor predefinite (+, - , succetc) sau definite de programator (proiecţii canonice, identificatori de funcţii şi procedurietc.), mulţimea simbolurUor predicat predefinite (<, >, >-, in etc.) sau definite deprogramator şi mulţimea simbolurilor constantă (numere, şiruri de caractere, identificatoride constante predefmite precum maxint, nil, false, true şi identificatori definiţi princonst). Interpretarea acestor simboluri este fie predefinită, fie stabilită de programator.

Se pune deci în mod natural problema modului în care aceste elemente pot fiagregate în limbajul Pascal pentru a obţine expresii. Sintaxa acestor expresii este descrisă

în anexa 3, diagramele 3.24-3.25. Se poate observa că cele mai simple expresii sîntconstantele fără semn şi variabilele. Astfel, numărul l. 2E -10, caracterul 'A ',

constantele predefinite maxint, nil, true, false, constantele structurate M 2RA (LINIE (I.O, 2.0), LINIE (3.0, 4. o)), variabilele x, Y, v* sînt expresii în

limbajul Pascal. Expresiile de la următorul nivel de complexitate se numesc factori (anexa3, diagrama 3.28) şi se obţin prin aplicarea opţională a simbolurilor funcţie, a simboluluipredicat no t şi a parantezelor (, ) sau [, 1. Astfel X, sin(XI), arctan(V),zound(2.8), not false, (2),

[ a , b , c ] (desemnează mulţimea cu elementele a, b şi c), [ 1 . . 5 ] (desemneazăintervalul de numere întregi n, 1 <- n <= 5) sînt factori.

Prin aplicarea opţională a operatorilor multiplicativi *, /, div, mod şi and asuprafactorilor se obţin termeni (anexa 3, diagrama 3.26). Astfel x, a * b, a * b mod 10,

not x and y and z sînt termeni. Din termeni se obţin expresiile simple (anexa 3,diagrama 3.27) prin aplicarea opţională a operatorilor aditivi ♦, - şi or sau prin aplicareasemnelor + şi -. Spre exemplu, x + (-1 ) , a * b, -a * b, a * b + b mod 10,

not x and y and z or not false sînt expresii simple. Cele mai complexe expresii

Pascal se obţin prin aplicarea simbolurilor predicat <, >, <-, >«, -, <>, in. Astfel, x, x < y, x + y in z, (i < j) = (j < k), x in [2, 3 , 6] sînt expresii Pascal corectesintactic.

Expresiile prezente în textul unui program Pascal sînt evaluate în cursul execuţieiprogramului pe calculator. Rezultatul depinde de valorile variabilelor la momentul cînd seface evaluarea (valorile constantelor nu se modifică în cursul execuţiei). Spre exemplu,expresia x < o este evaluată la valoarea false dacă valoarea lui x este l; este posibil

însă ca la o evaluare ulterioară să aibă valoarea true dacă între timp valoarea variabilei xs-a schimbat

Operaţiile predefinite sînt clasificate în patru categorii, după prioritatea pe care oau în cursul evaluării expresiilor. Cea mai mare prioritate o are operaţia not. Urmează apoi

în ordine descreseîndă a priorităţilor operaţiile multiplicative, operaţiile aditive şi operaţiile

relaţionale: prioritate operaţia

(cea mai mare) 0 not1 * / div mod and2 + - or

(cea mai mica) 3 < <= - > >« oin

Prioritatea operatorilor este reflectată în regulile 2.25-2.29 din anexa 2. Spreexemplu, conform notaţiei BNF, expresia a+b*c este descrisă prin arborele de derivareurmător:

<expresie> I

<expresie_simplă> / I \

<termen> <operator_aditiv> <termen> I I / 1 \

<factor> + <factor> <operator_multiplicativ> <factor> I I I I

<variabilă> <variabilă> * <variabilă>

Din plasarea celor doi operatori în acest arbore (+ mai aproape de rădăcină decît*) rezultă că operaţia * se execută înaintea operaţiei +.

Secvenţele de operaţii care au aceeaşi prioritate sânt evaluate de la stingă ladreapta. Expresiile dintre parantezele ( , ) sau [ , ] sînt evaluate independent de operaţiilecare le preced sau care le urmează. Se observă că operaţiile not, and şi or au aceeaşi

ordine a priorităţilor ca în algebra booleana;

Trebuie remarcat că operaţiile relaţionale <, <-, etc. sînt definite şi pentruoperanzi de tipul predefinit boolean, deoarece false < true. Prin urmare, operaţia < - aresensul de implicaţie logică, iar = are sensul de echivalenţă logică. Această încărcare cusensuri suplimentare a operatorilor relaţionali are ca efect o scriere mai complicată aexpresiilor logice în limbajul Pascal decît în matematică sau în alte limbaje de programare(spre exemplu, în AlgoloO există simbolurile predicat implicaţie logică şi echivalenţă logică).Astfel, în cazul declaraţiei

var x, y, z : rea l;

expresia

(x <- y) and (y <" z) <= (x <- z)

este evaluată totdeauna îa valoarea true şi exprimă proprietatea de tranzitivitate ■arelaţiei <-.

Omiterea parantezelor conduce la expresia

x <= y and y <= z <= x <- z

care este incorectă semantic, deoarece se evaluează mai întîi operaţia y and y care nuare sens pe tipul real . Mai mult, dacă x , y şi z Sînt de tipul integer, ultima expresie estecorectă semantic dar evaluarea ei se face începînd cu operaţia and (vezi paragraful 2.1.1).

2.6. Exerciţii

1. a) Să se reprezinte în cod complementar pe 2 bytes numerele întregi - 2,- l , 0, 1, 2.

b) Să se reprezinte în virgulă mobilă (amplă precizie şi dublă precizie)următoarele numere reale: +3.0, -3.0.

2. Dacă un număr pozitiv x se reprezintă în virgulă mobilă prin x -o. ixx . . .xn * 2" (vezi paragraful 2.1.1 tipul real), atunci să se reprezintenumărul întreg io... 01 (scris în baza 2, avînd n zerouri).

2.6.Exerciţii

55

3. Sînt corecte următoarele definiţii?a) type culoare «■ (a lb , ro şu , verde, ga lben );

alta_culoare = (portocaliu, galben);b) JSypa zi le = ( luni , marţ i , miercur i , jo i ) ;

prim ele_ 3_zil e = luni..mie rcur i;

4. Fie declaraţiile:

type T = i nteger; varA, B : integer; C

: integer; D : T; E : T;

Dacă x şi Y aparţin mulţimii {A , B, c, D, E}, care dintre atribuirile "X : - Y" esteacceptată de compilatorul utilizat? -

5. Fie declaraţiile

type R - record I, J : integer end;A - array [1..2] of integer; var RE :

R; AR : A;

Care dintre următoarele atribuiri este corecta?RE.IAR[2]

RE

- AR [1] ;= RE.J;

= AR;

6. Fie declaraţiile

type număr - (un u, do i);complex = record

re, im : realend;

varianta = recordA : integer;case alege : număr of

unu : (B,C : compl ex);

doi : (D : comp le x)end;Care dintre următoarele constante structurate sînt conforme cu definiţiile de mai sus:a)var ia nt a (1,unu,complex(1.1, 0.IEI),complex(-l .0 ,0 .5 )) ;

b)complex (- 1. 0, 2.3E5);

c)varianta (2, do i, (1.1, 1.1) )

7. a) Declaraţi variabilele A , B, c de tip set avînd tipul de bază mulţimea{1, 2,..., 10}.

b)Atribuiţi tui A mulţimea {1, 2, 3, 4} , lui B mulţimea {3, 4, 5, 6}, iarlui c mulţimea A U B.

c)Care este valoarea expresiei 4 in A * B ?

8. Re declaraţiile

type pi = "integer; vari : integer; vp : pi ;

Să se arate cum se pot realiza următoarele acţiuni:a)vp este referinţă la o variabilă de tip integer egală cu 1;b)i este egală cu 1;c)vp este referinţă la i.

9. Să se evalueze următoarele expresii Pascal:

a) l and 2 < 5;b) 1 * 2 < 5c) (l <= 2) and (2 <= D

d) 1 <= 2 and 2 <= 1e) x <= 0 - (-x >= 0)

10. Exprimaţi în limbajul Pascal expresia algebrică xy, unde x şi y sîntnumere reale.



Sintaxa instrucţiunilor limbajului Pascal este descrisă în anexa 2, definiţiile 2.22 -2.23 şi în anexa 3, diagramele 3.22 - 3.23.

O instrucţiune este alcătuită dintr-o etichetă opţională prin intermediul căreiapoate fi referită din alte instrucţiuni, urmată de instrucţiunea propriu-zisă, prin care estedescrisă acţiunea realizată în momentul execuţiei sale. Se face distincţie între instrucţiunilesimple (instrucţiunea de atribuire, apelul de procedură, instrucţiunea de transfernecondiţionat şi instrucţiunea de efect nul) şi instrucţiunile structurate (instrucţiuneacompusă, instrucţiunile iterative, instrucţiunile condiţionale şi instrucţiunea with).

3.1. Instrucţiuni simple

O instrucţiune se numeşte simplă dacă nu conţine alte instrucţiuni.■

3.1.1. Instrucţiunea de atribuireAceastă instrucţiune are forma

v. s- E

unde v este o variabilă (vezi diagrama 3.24 din anexa 3), iar E este o expresie (anexa 2,definiţia 2.23.b).

Prin execuţia instrucţiunii de atribuire, expresia E este evaluată şi rezultatul seatribuie variabilei v. Variabila şi rezultatul evaluării trebuie să fie de tipuri identice, sau tipuluneia să fie un subdomeniu al celeilalte, sau ambele să fie subdomenii ale aceluiaşi tip iarrezultatul în subdomeniul variabilei. Se admite ca excepţie cazul cînd variabila este de tipulreal iar rezultatul de tipul integer sau un subdomeniu al acestuia.

Spre exemplu, să considerăm declaraţiile următoare:ip ■■■ '

type T12 = 1. . 2; T13 = 1..3; ABC = (a, b,c); complex =record

re, im .: rea land;

tab - azray [ABC] of complex; conat i- complex(0 .0 , 1.0) ;

c_tab - tab(complex(0.0,0.0),

3. Instrucţiuni

complex(1.0,1.0),complex(0.1,1.0 )) ;

var k : integer; vl2 : lf.2;vl3 : 1..3; VS6 :

5 . . 6 ; al2 : T12; al3: T13; v_logic :boolean; r : re al ;v_tab : tab; z :complex;

în acest caz instrucţiunile

k := vl2 ; vl3:= a l2; a l2:= vl2

sînt corecte;instrucţiunea vl3 := k este corectă numai pentru l <- k <= 3; instrucţiunea vi2vl3 este corectă dacă l <» vl3 <= 2; instrucţiunile

v56 vl2; vl2:= v56; i:= z

sînt incorecte;instrucţiunea al3 :- loophole (T13, a) este incorectă, deoarece rezultatul evaluării este0 şi deci nu este din T13 (detalii privind funcţia loophole sînt in anexa 4);instrucţiunea a 13 := loophole (T13, b) este corectă şi hii a 13 i se atribuievaloarea 1;instrucţiunile

v_logic := (al2 <= vl2) = (al2 < vl2) or (a l2 = v l2 ); v_logic :=a - p red( b); v_logic := b = succ( a);v_logic := a - pred(c) sînt toate corecte; primele trei atribuie variabilei

v_logic valoarea true iar ultima valoarea false;instrucţiunea r : = sin(r) + co s(k) este corectă;instrucţiunea k : = r este incorectă, dar instrucţiunile

r :-k : = k round(r);trunc(r)

sînt corecte;instrucţiunile

z . rez. imzv tab

0;i;i ;c tab

sînt corecte.

3.1.2. Instrucţiunea apel de procedură

60




Instrucţiunea apel de procedură se inserează în program în locul în care se doreşteexecutarea instrucţiunilor specificate de o declaraţie de procedură asupra entităţilorparticulare "transmise" ei din locul de apel (vezi capitolul 4).

Sintactic, apelul de procedură (vezi regulile 2.23c-f, anexa 1) poate fi reprezentatprin metaforma

P ( 1 )

unde p reprezintă numele procedurii, iar 1 lista de parametri actuali. Parametrii actuali din

1 trebuie să corespundă ca număr, ordine şi tip cu parametrii formali specificaţi în antetuldeclaraţiei de procedură. Ei pot fi expresii, funcţii, proceduri. Numai parametrii actuali carecorespund parametrilor formali variabili (declaraţi prin var) pot fi modificaţi. Ei sînt variabilea căror locaţie este folosită pentru recuperarea în program a rezultatelor din procedură

Exemplu. O procedură cu antetul

procedura p(x, y. intecter; var z , t: r eal)

se poate apela prin

p(3 , 2 *(a + b - c ), u, v)sau

p( a, b, u, v)

saup( 3, 5, u, v)

unde a , b, c desemnează variabile întregi, evaluarea expresiei 2*(a+b-c) produce ovaloare întreagă, iar variabilele u şi v sînt declarate în program ca reale.

3.13. Instrucţiunea de transfer necondiţionat

Instrucţiunile unui program sînt executate secvenţial, aşa cum apar scrise în textulprogramului. Instrucţiunea de transfer necondiţionat oferă posibilitatea de a întrerupeaceastă secvenţă şi a relua execuţia dintr-un alt Ioc al textului (vezi anexa 2, definiţia2.23.p).

Această instrucţiune are forma:

goto e

unde e este o etichetă declarată prin labei. Declararea prin labei a etichetei e esteobligatorie. Domeniul de valabilitate al unei astfel de declaraţii este precizat în 4.4.3.2.

Execuţia instrucţiunii goto e are ca efect transferul controlului la instrucţiuneaprefixată de e (există o singură instrucţiune de acest fel).

Instrucţiunea goto e şi instrucţiunea marcată cu e trebuie să îndeplinească unadin condiţiile următoare:1) instrucţiunea prefixată cu e conţine instrucţiunea goto e;2) instrucţiunea prefixată cu e face parte dintr-o secvenţă de instrucţiuni s, iarinstrucţiunea goto e este una, sau este conţinută în una dintre instrucţiunile lui s

(secvenţe de instrucţiuni apar doar în instrucţiunea compusă begin... and sau îninstrucţiunea zepeat. . , until);

61



3. Instrucţiuni

3) instrucţiunea prefixată cu e face parte din secvenţa de instrucţiuni din instrucţiuneacompusă begin. . . and a unui bloc B, iar instrucţiunea goto e apare într-ofuncţie/procedură definită în partea de declaraţii a blocului B (prin bloc se înţelege unprogram / funcţie / procedură).

Exemplu. Programul următor execută parcurgerea în inordine a unui arbore binarreprezentat prin tablourile st, dr, info [LiGe86]. Stilul de programare folosit în exemplutrebuie descurajat, deteriorînd claritatea programului. Singura instrucţiune goto folosită

justificat în programul de mai jos este goto 1001.

■

labei 1001,1002,1003;conat nmax-9; typetip=integer;

index=0..nmax;f i i=array [ l . .nmax] of index; inform=array[ l . .nmax] of t ip; var st .dr: f i i ; info:inf orm ; r ad: index; procedura inordine(p:index); labei 1,2,3; const smax-5;var stiva: array [L.smax] of index;

k: 0..smax;begin

k:=0;if p=0 then goto 3; {condi ţi a 2} l: if st[ p] O 0 then begin

if k=smax then goto 1001; {c on diţ ia 3}k:=k+l; st iva[k] :=p;ps= st[p];goto 1; {condiţia 1}

end;2:wr iteln (inf o[p]) ; if dr[p ]-0 then

beginif k-0 then goto 3; {cond iţia 2 } p:=s tiva[ k]; k: =k-l ; goto 2;{condiţia 2}

end;

p:= dr [p] ;goto 1; {condi ţi a 2] 3:end;

• "

begingoto 1002; { cond iţia 2} 1001:w ritel n('De pasi re st iva; program

intrerupt*);goto 1 00 3; { co nd iţ ia 2 } 1 00 2:

{iniţ ia l izare arbore}st:-f i i (2,3,0,5,0,7,8,0,0);dr:-f i i(6,4,0,0,0,0,9,0,0);info:- inform(7,3,1,6,5,11,9,8,10);rad:- l ;

{v iz i tare in inordine} inordine(rad);{terminare program} 1003:end.

62




Exemplu. Secvenţele de program următoare sînt incorecte:■

a) goto 1;...begin 1: a:=b;...endb) if a= b then begin x:=a; goto 2 end else 2: y: -bc) procedure p;

procedure q; label 1; begin l: a:-b end; begingoto 1 end

ЗЛА Instrucţiunea de efect nul

Executarea acestei instrucţiuni nu are efect asupra variabilelorprogramului (starea acestuia rămîne neschimbată). Prezenţa sa în programelePascal este stabilită prin parantezele de opţiune [ şi ] ale definiţiei 2.23.a dinanexa 2 şi de arcul nemarcat al diagramei 3.23 din anexa 3. în textulprogramului, instrucţiunea de efect nul nu este reprezentată prin nimic dar,deoarece instrucţiunile sînt despărţite între ele prin delimitatorul "; ■■, prezenţasa este marcată de apariţia acestui delimitator. Astfel, în textul

10: ; i := i + 1 ;;; goto 10

există 5 instrucţiuni, dintre care 3 de efect nul.Deşi efectul său la execuţie este nul, inserarea sau eliminarea unei astfel

de instrucţiuni dintr-un text de program poate să-i altereze semnificaţia (vezi3.2.3, observaţia 1).

3.2. Instrucţiuni structurate

O instrucţiune structurată este compusă la rîndul ei din instrucţiuni carese execută fie în secvenţă (instrucţiunea compusă), fie condiţional (instrucţiunilecondiţionale), fie repetate de un anumit număr de ori (instrucţiunile iterative).

3.2.1. Instrucţiunea compusă

Instrucţiunea compusă are forma (vezi anexa 2, definiţiile 2.23.g):

begin It ; I2. . .; In end

şi specifică un grup de instrucţiuni, l x , l 2 . . . ; in, care sînt executate în ordinea încare sînt scrise. Chiar partea de instrucţiuni a unui program reprezintă oinstrucţiune compusă (vezi paragraful 4.)

Exemplu. Programul:

type compl ex = recor dre, im : integer

end;

vector = array Ц.. 5] of integer; var с :complex;

63

3. Instrucţiuni

a, b : vector;begin

с : = complex(1, 2 ) ; {c := l+2il

a := vector (1, 2, 3, 4, 5 ) ;b := (ere, c.im, 1, 0, 2)end. '

conţine o singură instrucţiune compusă prin care se iniţializează variabilele a,b şi c.

Această instrucţiune este utilă pentru a plasa în locurile din program în care nueste permisă decît o singură instrucţiune acţiuni mai complexe (vezi instrucţiunile while, for

în paragraful 3.2.2, instrucţiunile condiţionale if şi caae în paragraful 3.2.3 şi instrucţiuneawith în paragraful 3.2.4).

3.2.2. Instrucţiuni iterative

Instrucţiunile iterative sînt folosite pentru a exprima execuţia de zero sau maimulte ori a unui grup de instrucţiuni. în limbajul Pascal o instrucţiune iterativă este definităde:

<instructiune_iterativa><instruct iunea_whi le> |<instruct iunea_repeat> |< ins tructiun ea_f or>

Instrucţiunea for este indicată în situaţiile în care numărul de execuţii repetate estecunoscut. în caz contrar se pot folosi instrucţiunile iterative while sau zepeat.

3.2.2.1. Instrucţiunea while

Instrucţiunea while are forma (vezi anexa 2, definiţia 2.23.4): while B do I

în mod normal, instrucţiunea i se execută cît tinip expresia booleana B cecontrolează repetiţia este adevărată. Execuţia se poate însă încheia şi printr-un transfernecondiţionat. Dacă expresia B are de la început valoarea false, atunci instrucţiunea I nueste executată. Astfel, execuţia instrucţiunii

while tru e do x: = 1

conduce la executarea de un număr infinit de ori a instrucţiunii x: = 1. Pe de altă parte,instrucţiunea

whi.le false do I

este echivalentă cu instrucţiunea de efect nul, deoarece I nu va fi executată deloc.Se recomandă utilizarea sa în situaţiile cînd numărul de execuţii repetate ale

instrucţiunii i este dificil de evaluat

64




Exemplu. Re seria definită prin sumele parţiale

s0 = t0 , Si =■ s'ili + t1( pentru i>0 undet4 - - (x2't11)/(k J« (ki - i)J , i>0kj - ki. x + 2, i>0

k0 - 1.

Este cunoscut că lim sn - s in (x) . Următorul program calculează prima sumă parţială

s„ cu proprietatea 11„| £ eps ilo n- | s„ |, unde eps ilo n > o.

var s, t : real; k : integer;x, x2 , epsil on : rea l; begin t :=

x; k := 1; s := t;epsilon 0.0001 ; x2 := sqr (x ) ; «falle abs( t) > epsi lo n *abs(s) do begin

k := k + 2; .t := -t * x2 / (k * (k-D) ; s s + t

endend.

După execuţia programului, valoarea variabilei s este o aproximaţie a lui s in (x).Se observă că valoarea x2 se calculează înainte de instrucţiunea wfaile, deoarece variabilax nu se schimbă în cursul execuţiei acestei instrucţiuni.

Exemplu. Re şirul v1# i£o, definit prin relaţiile de recurenţă

v0 = aVi = ftv j.i); 12:1

şi p o proprietate satsfăcută de cel puţin un termen al şirului. Următoarele instrucţiunidetermină primul termen vk din şir ce satisface proprietatea P:

v:= a;^rtiile not P( v) do v: = f (v ) {v ar e

valoa rea lui v_k}Exemplu. Programul următor calculează frecvenţa literelor într-un text var

ch: char;frecventa: array ['A '.. 'Z' ] of in teg er; li ter a_m are : set of 'A'.. 'Z' ;liter a_mic a: se t of 'a'.. 'z'; begin

l itera_mare := [ 'A'. . 'Z'];I itexa_mica := [ 'a' . . 'z '] ;for ch := 'A' to 'Z' do frec venta [ch] :- 0;while not eof dobegin

while not eoin dobegin

read(ch) ;

65

3. Instrucţiuni

if ch in lit era _mi ca+ li ter a_m are then {li ter ele mici sin tconve rtit e in liter e mari} begin

if ch in lite ra_m ica then ch := ch r(or d(ch) - (ord( 'a') -ord( 'A') ));' frecventa[ch]:= frecventa[ch] + 1 end end; readln end;for ch := 'A' to 'Z' do

wr ite lnC Frecventa lui ch, ' est e-' , fre cve nta [ch ] )end.

Exemplu. Programul următor calculează cu aproximaţie valoarea cos (x)

[WÎ721:{calcu leaz ă cos(x)=l -x 2/2! + x4 /4! - . . .}program co s; const ep s= le-6; var

x,sx,s,t : real;i ,k i integer;

beginwritelnC Furnizaţi valoarea lui x'); read(x); t:- l ; k:=0;s:= l; s x:=sqr (x) ; while abs {t) > eps * abs (s) do begin

k:=k+2; t:--t*sx/(k*(k- 1)) ;s:=s+t

end;writeln('cos C,x,') = ',s)

end.O altă ilustrare a utilizării instrucţiunii while apare în exemplul 1 din paragraful3.3, la prelucrarea informaţiilor dintr-un fişier.

3.2.2.2. Instrucţiunea repeat

Instrucţiunea repeat are forma (vezi anexa 2, definiţia 2.23.1): zepeat I j . . . ;

In until B

Instrucţiunile aflate intre repeat şi until sînt executate pînă cînd expresia booleanaB care controlează repetiţia devine adevărată. Execuţia se poate însă încheia şi printr-un

transfer necondiţionat Această instrucţiune este echivalentă cu secvenţa de instrucţiuni

Ii. ■ •. ; IB î while not B do begin I j . . . ; In and

Se observă că instrucţiunile Ia,. .., I„ se execută cel puţin o dată. Serecomanda utilizarea sa în locul instrucţiunii while atunci cînd evaluarea expresiei carecontrolează repetiţia se face după executarea instrucţiunii I.

Exemplu. Prin programul următor se citeşte de la fişierul standard de intrare un şirde numere întregi cu proprietatea că toate numerele, cu excepţia ultimului, sînt nenule.Aceste numere se transferă într-un fişier cu tipul de baza integer şi se calculează apoi sumatuturor componentelor fişierului.

var v: file of integer; a: integer;suma: integer; <.

66

beginrewrite(v);repeat

read(a);write(v,a) until

a- 0 ; reset(v);suma:= 0;while not eof(v) do begin

suma : = suma + y";

get(v)end;writeln('Suma=', suma)

end.

Exemplu. Programul următor citeşte doi vectori cu componente întregi şiscrie pe ecran TRUE sau FALSE după cum vectorii sînt identici.sau nu:

const n='i;

type vector = airay | L . .n ] of integer; vara, b: vector;

i: integer;begin

for i : - J to n do read(a[i]); fori := l to n do read (b |'i ] ) ;

repeat i : = L * i until ( i=n) or (a i i ] obţ i i ) ;write(a[i]=bfil) ;

end.

Exemplu. Programul următor calculează cel m ai mare divizor comun aldouă numere întregi pe baza algoritmului lu i Euclid.

vara, b, c : integer;t : char;

beginrepeat

write(' Furnizaţi numerele a s: b : ' ) ; readlti(a, b); a: = abs(a); b:- abs( b) ; while (a O 0) and (b <>o) do begin

C b;b : - a mod b;a : -- c

end;wr i te(' cmmdc f ' , a + b,

Continuaţi? Răspundeţi d sau n');readln(t)

until t -- 'n'end.

67



3. Instrucţiuni

Exemplu. Programul următor ordonează crescător o listă de n>i numere întregi, prin metoda inversării elementelor adiacente.

const nmax-100;var lista :array [L.nmax] of integer;

n , {lungimea efectiva a listei (i : O . . nmax;

loCj nv : 1. .nmax; ll o cu L ultimei inversiuni I I. . : integer;begin

writeCdati lungimea li st ei ' ) ;read In(n ) ;writeCdati ', n, ' elemente al e listei' ) ; for i I to n doread ( l ist a [ i ] ) ; repeat

1ocinv:-l;fo r i : ^1 to n-.l do

if lista M l > l is ta l i+.l ]then be gi n {se face inversiune}t: --lista 1 i] ;lista { i ] l i s ta [ i i 1 } ;lista l i " l ] t ;

lOCinV : -

i end;! lista |locinv .. n} este ordonata crescător 1 unti l locinv-1;wr j te In ( 'lista ordonata crescător este:').,;for to n do writeln( lis ta |i|)

end.

3.2.2.3. Instrucţiunea for

Instrucţiunea for are formele (vezi anexa 2, definiţiile 2.23.m, 2.23.n)

for v : - j to [ do I

sau for v : - i downto f do l.

Variabi la v este de ti p scalar ordinal (deci nu real) iar i şi f sînt expresiide tipuri compatibile cu tipul lu i v. în mod normal, instnicţiunea specifică execu-tarea repetată a grupului de instrucţiuni

V : X; T

_

pentru toate valorile x di n intervalul cuprins între i şi t, luate în ordinecrescătoare pentni prima formă şi în ordine descrescătoare pentm a doua.Execuţia poare fi însă încheiată şi printr-un transfer necondiţionat. Valoarea finală

a variabilei v se consideră a fi nedefinită după terminarea normală a instrucţiuni'fo r. Prin urmare, cu excepţia faptului că variabila Y este nedefinită dupăterminarea normală, instmcţiunea

68

for v := i to f do l este

echivalentă cu

v : - i ;

while v <' f do beg in I; v := s.ucc(v) end iar in stru cţiun ea

for v : - i downto f do T . .

cu

v := i ;while v >= f do begin I ; v := pied(v) end

Această instrucţiune este utilă pentru programarea formulelor derecurenţă de forma

ac. = a, an., - f( a n ) , n> -0 .

Astfel, în urma execuţiei unei secvenţe de instrucţiuni de forma următoare

v : - a ; ' ■for i :^ 1 to n do v := f (v)

valoarea lui v este ar.

Prin urmare, în cazul

a0 - 1, a„„ ,a„* (nKI.)

programul următor

var i, v : integer;begin

v 1 ;for i : - 1 to V do -v : = v *. i..

end.

calculează valoarea v = /!. r v:

Pentru a prelucra pe rînd toate valorile tipului dat de definiţia-• -

type EH - (A_l, A_7., A_~\,A_4) ;

în ordine descrescătoare, utilizînd o procedură P şi o variabilă v de tipul EH,putem folosi instrucţiunea iterativă for astfel:

for v :-• A 4 downto A i do P(v )

în acest caz, .secvenţa de instnicţiuni executată va fi :

P(A_4) ; P( A _i) ; P(h _Z) ; P(A_l) .

Exemplu. Programul următor calculează produsul a două matrici.

{i tunul ti . re mat ri ci!

69

3. Instrucţiuni

const m = 1; p = 3;n

- 2 ;

var

i : 1. .m; j :1 .

n ; k :

S:

Integer;

A : array [.):. .m. J . .p!B : array [ .1 . .

p, J . .n]

C : array [1 . . m , l.-.n] begin (ini ti ai i /.are A si B}

writeIn < ' scrieti matrit

for i: ■ l to m do

begin for k : - 1 to p do begin read(s ) ; wr i to (s ) ; A | i ,k} : - S end;wr i. teln

end;

{a fos t c i t i t A}writeln;for k : ■■-1 to p do begin for j : --1 to n do

begin read(s); write(s); B [ k, ; j| : = send; v.

wr i te lnend;{ a tost, citit Blwr i te ln ;ise calculeaza C = A * B) writeln('A * B - ' ) ; for i : - 1 to mdo begin for j :=. lto n do begin s:= o;

for k : - 1 to p dos s * A] i ,k ] * B[k , j 1 ;

Cf i . j J s ; wr i te( s )

end;wr i te ln

end;

wr i teln

3.2.3. Instrucţiuni condiţionale

O instrucţiune condiţională selectează o singură instrucţiune d intreal te rn at iv el e sale, pe care apoi o execută. Instrucţiunile condi ţi on al e sînt if ş i case.

3.2.3.1. Instrucţiunea if

Instrucţiunea if are forma (vezi anexa 2, definiţia 2.23.h): if B then I

sau

70




if 15 then I else J

Ex ecuţ ia instrucţiunii if începe pr in evaluarea condi;iei B. Dacărez ult atu l eva luă rii este tr uc, atunci se execută instrucţiunea 1 . Dacăre zu lt at ul ev al uă ri i este fa l s e, atunci în primul caz se execută instnicţiuneade efect nu l , i ar în a l doilea caz se execută instrucţiunea J.

Observaţii1. Dacă în instrucţiunea i f 6 then s , introducem înainte de s instrucţiu-

nea de efect nul (if B then; S) atunci a nu mai intră în componenţa instrucţiu-ni i cond iţ ionale, deci este executată indif erent de valoarea lui n.

2. Amintim că limbajul Pascal nu consideră simbolul ; ca facînd parte dininstrucţiune ci îl foloseşte ca delimitator. Prin urmare, dacă într-o instnicţiune if B then I else J introducem după I simbolul ; obţinem un program incorectsintactic (în acest caz secvenţa else. . . este interpretată ca fi ind in st ni cţ iu -nea ce urmează celei condiţionale).

3.Ambiguitatea sintactică a construcţiei

if B_lthen if B_2 then I_lelse ]_2

(else face parte din primul i f sau din cel de-al doilea?) este rezolvată p ri ninterpretarea construcţiei ca fiind echivalentă cu

if 13__3then begin

if B_2 then I_ lelse I._2 end

Ilustrăm utilizarea instrucţiunii condiţionale if şi a instrucţiunii iterative while prinexemplul următor care converteşte un număr in baza 10 în scrierea cu cifre romane. Dacax este o variabilă întreagă ce conţine numărul ce trebuie convertit, atunci următoareainstrucţiune compusă realizează conversia dorită:

var x : 0..maxint;begin

readln(x); wri te(x, ' = ' ) ;while x>=1000 do begin write CM'); x:«x-1000 end; if x>=900 then begin write('CM'); x:=x-900 end else if x>=500 then begin write('D'); x:=x-500 end else if x>=400then begin write('CD'); x:=x-400 end; while x>=100 dobegin write('C'); x:=x-100 end; if x>=90 then beginwriteCXC) ; x:=x-90 end else if x>=50 then beginwrite('L'); x:-x-50 end else if x>=40 then begin write{'XL');x:=x-40 end; while x>-l0 do begin write ('X' ); x:= x-10 end;if x=9 then begin write ( ' IX' ') ; x:=x-9 end else if x>=5 then

begin write('V'); x:=x-5 end else if x-4 then begin writeC i v ) ; x : =x -4 end; while x>-l do begin wr ite C I ' ) ; x :=x -lend; writeln

«•> î kăM

71



3. Instrucţiuni

end.O utilizare abuzivă a instrucţiunii if este următoarea

if a - b then found := tr ue else found := f al se

unde found este o variabilă booleana Evident, acelaşi efect se obţine prin execuţiainstrucţiunii

found a = b

Exemplu. Prin programul următor se calculează xy, unde y este număr naturalnenul.

var e, y : 0. .100;u, x, z : real; beginreadln(x); readln(y);z := 1 ; u x; e != y;while e > 0 do begin

while not odd(e) do begin e : - ediv 2; u :- sqr (u ) ;

end;

law e :- e, - 1; z := z * uand;write ln{x, ' la puterea ', y, iz - x** y}

z )

end.Observăm că o variantă mai simplă dar mai puţin eficientă se poate obţine

omiţînd instrucţiunea while interioară, rezultatul z este astfel obţinut prin y multiplicări alelui x.

Alte ilustrări ale utilizării instrucţiunii if pot fi găsite în exemplul 2 din paragraful3.3.

■

3.23.2. Instrucţiunea case

Instrucţiunea case (vezi anexa 2, definiţiile 2.23.i, 2.23.J) constă dintr-o expresienumită selector şi o listă de instrucţiuni, fiecare precedată de o constantă de acelaşi tip cuselectorul sau de cuvtntul cheie othexwise. Instrucţiunea casa se execută astfel: seevaluează expresia ce defineşte selectorul şi apoi se execută fie instrucţiunea precedată deconstanta egală cu valoarea selectorului, fie instrucţiunea precedată de othexwisedacă valoarea selectorului nu coincide cu nici una din constantele ce eticheteazăinstrucţiunile componente. în acest ultim caz, absenţa specificaţiei othexwiseconduce la erori.

Exemplu. Programul următor simulează un calculator cu operaţiile elementare+, -, *, div şi mod pentru numere întregi.

program calculator;var a, b: in teg er; codoper: cha r;begin

72

writ e('co d o peraţ ie:') ; read ln(codoper) whilecodoper <> '.' do begin

wri te( 'operanz i : ' ) ; readln(a, b) ;wr i te( ' rezultat : ' ) ;

case codoper of a+b) a-b) a*b)

div ' , b , ' = ' , a div b, mod ', b,' - ' , a mod b ) ; otherwisewriteln('cod operaţie

necunoscut') and;write('cod operaţie:') ; readln(codoper)

andend.

O altă ilustrate a utilizării instrucţiunii case poate fi găsită în exemplul 3,paragraful 3.3.

Observaţii1.Constantele ce prefixează componentele unei instrucţiuni casa nu sînt

etichete în sensul din paragraful 1.2 şi nu pot prin urmare să fie referite printr-o instrucţiunegoto şi nici nu pot să apară într-o declaraţie labei.

2.Ordinea acestor constante este arbitrară, dar fiecare nu poate apare decît osingură dată ca prefix de componente.

3.Dintr-o instrucţiune componentă nu se poate face transfer la o altăcomponentă.

3.2.4. Instrucţiunea with

în paragraful 2.2.2-, unde a fost introdus tipul de date record, s-a menţionat cădacă x este o variabilă de tip record, avînd pe s_i drept componentă, atunci referirea las_i se face prin x. s_i. Dacă s_i este la rîndul ei de tipul record, atunci referirea lacomponenta sa s_ i_ j se face prin x. s_i. s_i_ j . Acest mod de referire a componentelor

unei date structurate este în anumite situaţii greoi. Pentru a înlătura acest neajuns a fost încorporată în limbaj instrucţiunea witb care defineşte domeniul de valabilitate pentruidentificatorii proiecţiilor canonice ale unor variabile de tip record. în acest fel, o proiecţiecanonică poate fi referită şi prin numele ei s_i, fără a fi necesară calificarea prin numelearticolului care o conţine.

Forma generală a instrucţiunii with este:

witb. <variabila_record> { , <variabila_record>}do <instructiune>

Spre exemplu, în prezenţa declaraţiilor:

type complex = record x, y : real and;

număr - recordcase t ip : ( in t, r e, corn) of

b,b,b,

writeln(a,writeln(a,

writeln(

73



3. Instrucţiuni

int : (x_int : integer);re : ( x_r e : re al);c or n : (x_com : complex)

and;var n : număr;

■

putem face iniţializările:

n.tip .:- int;n.x_int : - 1;n.t ip re;n.x_re := 1.1;V n.t ip corn;

n.x_com.x :» 0.0;n.x_com.y 1.0;

sau putem folosi instrucţiunea with echivalentă:

with n, x_com dobegintip int; x_int 1;tip : = re; x_re

1.1; t ip corn;X :- 0.0; y :- 1.0rad {with}

Exemplele 1 şi 3 din paragraful 3.3 sînt alte ilustrări ale mstrucţiunii with.

Observata

1.Este interzisă afectarea elementelor din lista de variabile prin instrucţiu-nile asociate lui with. Dacă de exemplu a este o variabilă de tipul array avîndtipul de bază un tip record, atunci

with a[i] do i : - i + 1

nu este permisă.

2. Dacă declaraţia

var a : axray [1 ..2] of integez; a : 1..2; nu este permisă, datorită unei

definiţii ambigue pentru a, declaraţia

var a : integer;b : racord a : re al ; b : boolean and;

este permisă, variabila a este de tip inţegez şi b. a este de tip real . în plus, într-oinstrucţiune

with b do Sidentificatorii a şi b, dacă sînt referiţi în S, au semnificaţia b .a şi respectiv b.b.

74




33. Exemple

Exemplul 1. Programul următor creează un fişier cu componente de tipul recordper soana; cîmpurile acestor componente se obţin prin citire din fişierul input (de laterminal). Fişierul este apoi citit şi sînt numărate înregistrările cu cîmpul anul-194 9.

type persoana - record nume,prenume : packed azzay [1..20] of char; z iua :l..31; luna : 1. .12; anul : integer and;

var individ : pe rs oana ; f : filaof pe rs oa na ; n » integer;begin \

rewrite(f) ;vith individ do begin

while not eof {exi sta inca da te} do beginwrite ('nume: ' ) ; readln(nume);write('prenume:'); readln(prenume);writelnCdata naşteri i ' )write C z iua: '); readln (ziua) ;write('luna:'); readln(luna);write ('an ul:' ); readln(anul);f * :- individ; put(f) {sau write( f , individ)}and; mreset ( f ) ; n := 0 ; while noteof(f) do begin

indiv id : - f"; get( f) ; {sau read(f , indiv id) ;} if anul=1949 then n := n + 1

end;wri tel n(' sin t ' , n, ' persoane cu anul 194 9')

andend. .; .

Exemplul 2. Considerăm un fişier text de intrare, fa; conţinutul acestuia estecopiat în fişierul text fb, păstrîndu-se structura de linii a lui fa, dar înlocuind orice grup de

două caractere ' a ' consecutive printr-un caracter ' b ':var fa, fb : text; c : char; begin

reset(fa); rewrite(fb);33.Exemple

77

while not eof(fa) dobegin

if eoln(fa) thenbegin

readln(fa) ; wri teln( fb)end

•Is*begin

75

3. Instrucţiuni

read(fa, c ) ;if c <> 'a' then write(fb, c) else if eof(fa) then write(fb,c) else if eoln(fa) then begin

wri te( fb, c ) ;readln(fa) ;writeln(fb)

end•IB*begin

read(fa, c ) ;if c - 'a' then write(fb, 'b' )elsebegin

wr i te ( fb , ' a ' ) ;write(fb, c)

endend

endend

end.*- ■

Exemplul 3. Considerăm tipul de date persoana din exemplul 1 completat cucîmpurile cod şi copii . Se creează un fişier în acces direct cu componente de tip persoana;cod va fi chiar numărul de ordine al componentei. Programul permite următoarele tipuri deoperaţii asupra fişierului: * a': adăugarea unei componente la fişier (cîmpurile componentei secitesc de

la terminal);'u': actualizarea cîmpului copii al unei componente din fişier, identificată prin

cod;

' 1': listarea componentelor fişierului cu numere de ordine într-un interval; ' a': terminareaprogramului.

type persoana = zacozd cod :

integer;nume,prenume : packed array [1..10] o£ char;ziua : 1. .3 1;luna : 1..12;anul : integer;copii : integerend;

vax individ : per soana;f : fila of persoana;

n,ncod,pcod,ucod,i : integer; codoper : char;begin

rewrite(f, , ' /seek'); withindivid do begin

76

wr ite ('c od operaţie (e, a): '); readln(co dop er) ; while codoper<>'e'do begin caaa codoper of

'a' : {adauga} beginwrite( 'cod: ' ) ; readln(cod); write( ' nume: ' ) ;readln(nume); wr it e( * prenume: ' ) ; readln(p re nume );writelnCdata naşteri i ' ) ; write('ziua:'); readln(ziua);writeCluna: ' ) ; readln( luna); write( 'anul : ' ) ;readln(anul); write('copii:'); readln(copii);seek(f.cod); write(f, individ) end;

'u' : (actualizează) beginwr ite ( ' cod :') ; readln(ncod); write Cnu mar copii deadăuga t: ') ;readln(n) ; seek(f,ncod) ; read(f, indi vid) ;copii:=copii+n;seek( f , ncod ); wr ite( f , individ) end;

'1' : {l istează} beginwrite ( ' de la: ' ) ; readln(pcod); writ eCpi na l a : ' ) ;readln(ucod) ; seek( f , pc od );fox i:=pcod to ucod do begin read(f, individ);

wr it el n( cod, nume, prenume,ziu a, luna, anul, copii)

end

3.3.Exemple 79

«ud;otherwiseend;

write('cod operaţie (e, l ,a,u): ') ; leadln(codoper) endend

end.

Exemplul 4. (Problema lui Josephus [Kn74], p.178). Se consideră n obiecte,aşezate pe un cerc şi numerotate în ordinea aşezării 1, 2, .. . ," n. Parcurgînd cercul însensul dat de numerotarea obiectelor, începînd cu obiectul m, se elimină pe rînd toateobiectele din k în k. Programul următor determină numerele de ordine ale obiecteloreliminate pentru n, m, k daţi, folosind o listă circulară creată dinamic.

type legă tura - "nod; nod= record

număr: integer;următorul: legătura

end;var p, q, r : legătura; n, m,

k: integer; i, j: integer;

begin

writ eCnu mar de obie cte:' ); readl n(n) ; w riteC cu ce obiectse incepe elim ina rea :') ; readln (m) ;

•

77



3. Instrucţiuni

write('din cite in cite:') ; readln(k); {construieşte l istacircu lara } new( p); q:= p; q* .număr:= 1; for i : - 2 to n dobegin

r := q; new(q);r*.următorul : - q;q*.număr:= i

end;q*.următorul : - p;{in a ces t moment p indic a pri mul nod din lis ta si q ult imu l;se determina pr im ul nod de eli mi na t; p va indica nodul deel im in at s i q nodul precedent din li sta}

for i := 1 to m-1 dobegin

q: = p ; p': = p* . urma to ru land;

{incepe el iminarea}writ eln ( ' ordinea de elimina re e ste:' )for i := 1 to n-1 do

begin

writeln(p*.nu măr); {elimina noduldin l ista} q * .următorul:=

p*.următorul; ; dispose(p);{determina ur mă toru l nod de el im inat}

p:- q;fox j:= 1 to k do begin

q:= p; p:= p * . următoru land

and;writeln(p*.număr); dispose(p)

and.

3.4. Exerciţii1. Fie programul Pascal:

vartxue : boolean; i :integer; begin

true := fa lse ;i := 0;

while not true do begin true:= not true; i := i +1

end

and.

Care este valoarea lui i după execuţia sa?

78




2. Să se scrie un program Pascal în care să fie utilizată instrucţiuneaiterativă for (cazul to), pentru a calcula numărul armonic de ordin 100, h _lO0.Reamintim că h_n = 1 + 1/2 + . . . i /n [Kn74].

3» Aceeaşi problemă ca mai sus în care se substituie to cu downto.

4. Fie suma s_ ioo = l/l - 1/2 + 1/3 - . . . -1/100. Scrieţi cîte un programPascal care să calculeze s_ ioo a) evaluînd de la stingă la dreapta

3.4.

Exerciţii

81

b) evaluînd de ia dreapta la stingă.5. Este corect următorul program Pascal? label 1;

var î î (alb, negru);i_sir: packed array [1..5] of char; beginreadln(i_sir); if i _s i r - 'a lb ' then i :=alb else if i _s i r = 'negru' than i: = negruelse writeln('rezultatul imprevizibi l ' ) ; casa iof

alb : beginif true than goto 1;1 : i := succ(i)

and;negru : i := pred( i ) ; end;casa i of

alb: writelnCalb'); negru:writeln( 'negru')

endend.

6. Fie programul Pascal:labei l , 2, 101, 102; var i :integet; begin i : - 1; casa iof

1 : 101 : goto 102;

2: 102

: goto101;

andand.

Este corect? De ce?

7. - Fie declaraţiilevar a : integer; b :

recorda , b : integerend;

a) Suit corecte instrucţiunileb.a := a ;b .b := b .a

b) Dacă se execută instrucţiunilea : = 0 ; withb do

i

ti'-''

79

•A

3. Instrucţiuni

a := 1; cevaloare are a ?

8. Fié T un tip de date pe care s-a definit o relaţie de ordine totală <,. Senumeşte sortare (în ordine crescătoare) a fişierelor din T* o aplicaţie S : T*

------------------------------------------------------------------------------------------------------------->T*,definită astfel: oricare ar fi u = f l i 4 . f n e T, s(u) - f p l . . . f p n , unde (p_l, . . . ,p_n)este o permutare a lui (i , . . . , n), astfel încît f p t £ f p j pentru 1 £ i <, j <, n. Practic, se

poate construi fişierul sortat s (u), eventual în aceeaşi arie de memorie ca u, sau numaipermutarea (p_i, . . . , p_n).

Fie mei un natural fixat, i un tip de date cu ordinea totală £ şi T - i". Pe T definimordinea lexicografică £ astfel: kt. . . k„ £ lt.. .1„ «*• kj - 1± pentru 1 £ i £ m sau existăp, l i p i m , astfel încît lq = l t pentru l 5 i S p - l şi kp < lp. Să se scrie un programde sortare în ordine lexicografică a unui fişier cu componente de tipul T, pentru I - integer.

9. Re definiţiile Pascal:type candidat = zecozd

nume: packad axray [1. .30] of ch ar;media : real '

and;

var f: file of candidat; Să se scrie un program desortare a fişierului f :a)după cîmpul nume, în ordine lexicografică;b)după cîmpul media, în ordine descrescătoare;c) după cîmpul media în ordine descrescătoare, iar în cadrul aceleiaşi

valori a cîmpului media, după cîmpul nume în ordine lexicografică.

10. Fie T un tip de date pe care s-a definit o relaţie de ordine totală <, şi F = im s,unde s este aplicaţia de sortare din exerciţiul 8 (F este mulţimea fişierelor sortate din T*).Se numeşte interclasare o aplicaţie I : F x F —r^-> F definită prin i(u,v) - s(uv).Scrieţi un program de interclasare a două fişiere cu componente de tip integer.

11. Fie un fişier text f i al cărui conţinut este descris prin diagramele sintacticeurmătoare:

<continut>-------------,----------------------------------------------. -'i ,-—> EOF --------->

|----- <constan ta_i ntre aga> <------1|----------------- gp <-----------------------_j

l-------------------- eol <---------------------—J<constanta_intreaga>

--------1----------------1---------------1 -----> <c if ra > ---------1------->

unde sp este caracterul spaţiu, eol este caracterul sfîrşit de linie, EOF este sfîrşirul de fişier,iar <cifxa> este o cifră zecimală Să se scrie un program care să transfere constantele

întregi mai mari ca -100 din fişierul f i într-un fişier text f o. Compararea va fi făcută înbinar, iar conversiile vor ii efectuate prin program. Fişierul f o va păstra structura de linii a

fişierului fi.

80




12. Scrieţi un program care să adauge componente la sfîrşirul unui fişierextern deja existent, utilizind

a)un fişier Pascal secvenţial;

b)un fişier cu acces direct

13. Fie programul:var

l inie: packed axxay [1..72] of ch ar ; contor: integer;begin

contor:- 0 ; «bilanot eoln do begin

contor:- contor + 1 ;read(linie[contor])

and;readln;writeln(contor)

and.Care este valoarea variabilei contor afişată pe terminal ca urmare a execuţiei

acestui program cu datele de intrare următoare:a)o linie vidă, constînd din RETURN;b)spaţiu urmat de RETURN;c)sfîrşit de fişier (CTRL/Z)?

(în legătură cu observaţia 1 de la paragraful 2.2.4.1.3).

14. Să se scrie un program pentru rezolvarea problema lui Josephus (veziexemplul 4 din paragraful 3.3), folosind o listă circulară cu legături duble, definităprin:

type legătura- *nod;nod- record

inapoi: le gă tu ra ; {spr e nodul precedent] număr:integer; înai nte: legăt ura {spre nodul urmă tor]

and;

81

4.1. Mecanisme de abstractizare în Pascal...........

Capitolele precedente au introdus conceptele de bază ale programării (tip de date,expresie, instrucţiune) şi realizarea lor în Pascal. Ele permit exprimarea riguroasă adescrierilor şi prelucrărilor de date sub formă de programe.

Introducem acum conceptele de funcţie şi procedură, care generalizează pe celede expresie şi instrucţiune. O funcţie / procedură se defineşte printr-o declaraţie careasociază un nume cu o instrucţiune compusă precedată, eventual, de o secvenţădeclarativă. Numele funcţiei / procedurii poate fi urmat de o listă de parametri formali.Funcţia / procedura este referită prin simpla inserare a numelui ei în locurile dorite dinprogram avînd ca efect producerea în acele locuri a valorii / rezultatelor determinate deexecuţia instrucţiunii compuse. O astfel de referire se numeşte apel de funcţie / procedură.

Un număr de funcţii uzuale (sin. In, sqrt, axctan,...) şi de prelucrări standard(writeln, read,.. .)sînt disponibile utilizatorului ca funcţii, respectiv proceduri predefinite(vezi anexa 4). .

Conceperea programelor în termeni de funcţii / proceduri permite un nivel

superior de abstractizare faţă de expresii / instrucţiuni, furnizînd astfel un mijloc de controlal complexităţii programelor. Acestea pot fi descompuse convenabil în subprograme maisimple, rafinate succesiv ca funcţii / proceduri programate independent [Wi72].

Exprimarea unui algoritm ca program Pascal nu este unică. Conceperea structuriiprogramelor, fol osirea de funcţii sau proceduri, stabilirea parametrilor sînt, în bună măsură,la alegerea programatorului, cum se va vedea în exemplele din paragrafele următoare.

4.2. FuncţiiConceptul de funcţie corespunde celui uzual matematic şi extinde pe cel de

expresie Pascal.

4.2.1. Declararea funcţiilor

Definirea unei funcţii în Pascal se face în conformitate cu următoarele diagrame

de sintaxă: <functie>

—i—> <antet_functie> —> ; —,--------> <corp> -----,--,—> ; -- ->

! I—> <diiectivă> —' |

> function -> <identificator> -> ,• -> <corp> — 1

4.2. Funcţii

<ancet_functie> i-------- ; <--------1 —> function —<identificator> T ( —L <param foimal> J — ) -,—■

I_____

________________:-------------:____________________l1- -> : —> <identificator tip> ——>

. .-: . <UÎ4 sXv S?JJ JSÎÎ-'JS S j?. î;» ■JSAS : • .<corp>

--------------> <declaratii> —> <instructiune_compusa> — >

în general textul Pascal al unei declaraţii de funcţie are forma: function f (x , ; .

. . ; x_) : t; begin

f : = e;

end ; { f}

Primul rînd ilustrează antetul funcţiei cu:- f : identificator reprezentînd numele funcţiei;- (x i ( - . . . ; x n) : listă (opţională) de parametri formali reprezentînd argumentelefuncţiei;- t: identificator reprezentînd tipul rezultatului; acesta trebuie să fie un tipsimplu (scalar) sau pointer.

Antetul este urmat de corpul funcţiei, format din:- dx: declaraţii locale ale funcţiei (opţionale) grupate în secţiuni (eventual vide)scrise în ordinea

labeiconsttypevarfunction / piocedure

Aceste cerinţe sînt mai puţin stricte în Pascal Oregon — vezi 4.6.1. -begin. . . f := e; ...end; : instrucţiune compusă specificînd prelucrările de date ce seproduc prin execuţia funcţiei; numele f al funcţiei (fără parametri) apare cel puţino dată în partea stingă a unei instrucţiuni de atribuire care se execută: f: '- e.Rezultatul întors de funcţie, de tipul t, este ultima valoare atribuită lui f.

4.2.2. Apelul funcţiilorUtilizarea unei funcţii se specifică printr-un apel de forma:

f (a1( . .. ,a„)

•. -• fi

- f: numele funcţiei;- (a t , . . . ,an) : lista (opţională) de parametri actuali reprezentînd expresii ale căror valorisau adrese sînt furnizate funcţiei.

Apelul de funcţie este un operand într-o expresie; el se inserează în locul în careeste dorită valoarea produsă de funcţie. Cînd expresia este evaluată, funcţia este activată,iar valoarea operandului devine valoarea întoarsă de funcţie.

4.2.3. Exemple

Vom scrie pentru început un program extrem de simplu, pentru calculul ariei unuitriunghi ABC cunoscînd lungimile laturilor:

83



4. Proceduri, funcţii, programe, module

program PI;var a, b, c, p, s : real; bag in

a bc P swriteln (s)

and; {Pl}

Acest calcul poate fi realizat şi prin următoarea funcţie:

function aria : real ; varp: real; begin

p (a + b + c) / 2;aria sqrt(p * (p - a) * • (p - b) * (p - c)) end; {arial

Declaraţia acestei funcţii conţine antetul

function aria ! real;

în care specificaţia real stabileşte tipul valorii calculate. Restul textului reprezintă corpulfimeţiei, format dintr-o declaraţie şi o instrucţiune compusă. Numele funcţiei apare îninstrucţiunea compusă în partea stingă a unei instrucţiuni de atribuire. Asupra utilizăriivariabilei p facem următoarea observaţie. Dacă s-ar rescrie cele două instrucţiuni, înlocuindvariabila p prin ar ia, cele două instrucţiuni ar deveni:

aria:= (a+b+c)/2;aria:=sqrt(aria*(aria-a)*(aria-b)*(aria-c)).

Apariţia variabilei ar ia în membrul drept este incorectă, aceastaimplicînd apelul (recursiv) la funcţia ar ia.

Programul PI poate fi rescris acum în forma P2.

program P2; var a, b, c, s : real;function aria : real ;

var p: real; begin

p := (a + b + c) / 2;

aria := sqrt(p * (p-a) * (p-b) * (p-c)) end;{aria} begina := 3 ; b !» 5 ; c : - 6 ; s : =aria; writeln (s) end. {P21

Printre declaraţiile programului P2 apare şi cea care defineşte funcţiaar ia . Variabilele reale a, b , c, s ale programului sînt cunoscute şi în corpulfuncţiei; ele sînt variabile globale relativ la funcţia ar ia . Variabila p esteajutătoare pentru funcţie, ea servind doar la calculul unei valori intermediare fărăinteres pentru restul programului. Declaraţia ei

. . . var p: real ;

a fost deplasată în corpul funcţiei; p devine astfel o variabilă locală funcţiei şi nueste accesibilă în afara corpului funcţiei. Ea va fi creată (prin alocare de spaţiu

- 3; =5;- 6 ;

= (a + b + c) / 2;

84



4.2. Funcţii

pentru valorile sale) la fiecare activare a funcţiei şi desfiinţată (prin dealocareaspaţiului ei) la completarea execuţiei funcţiei şi revenirea în program.

Se previne astfel şi un efect secundar (vezi 4.5.3) nedorit ce s-ar fiprodus dacă p ar fi rămas globală: valoarea atribufă ei prin instrucţiunea

p : = ( a+b*c)/2

ar fi devenit, inutil, cunoscută în tot programul.Apariţia numelui funcţiei în expresia din partea dreaptă a instrucţiunii

s := ar ia

determină activarea funcţiei cu efecte echivalente instrucţiunii compuse: beginp := ( 3 + 5 + 6 ) / 2 ;aria := sqrt(p * (p - 3 ) * (p - 5 ) * (p - 6 ) )

end;

Valoarea astfel obţinută va fi inserată în locul numelui funcţiei şi atribuitălui s.

Comunicarea între program şi funcţie nu este specificată explicit; ea seface prin variabilele globale a, b, c, care sînt cunoscute şi în corpul funcţiei.

Limbajul permite o formă sintactică în care elementele de comunicaresînt desemnate explicit prin declararea lor în antet ca parametri formali aifuncţiei, de exemplu:

function aria {a , b, c : real) : real;

Prin specificarea ca parametri formali, a, b, c desemnează şi ei variabilelocale funcţiei.

Apelurile de funcţie vor conţine acum parametrii actuali care corespundcelor formali în număr şi tip, de exemplu:

aria(3 , 5 , 6 )aria( 6 , 4 , 9 ) .

Programul P3 include aceste modificări.

program P3;var a, b, c, s : real;function aria(a, b, c : real) : real;var p : real;begin

p :- (a * b + c) / 2 ;

aria := sqrt(p * (p - a ) * (p - b) * (p - c) ) end;{ariaî begin

a : = 3 ; b : = 5 ; c : = 6 ; s : = aria (a, b, c) end.{P3}

Identificatorii a, b, c apar acum în două declaraţii: în program şi înantetul funcţiei. în antetul funcţiei ei sînt declaraţi drept parametri formali. Acestedeclaraţii sînt valabile doar în corpul funcţiei; variabilele numite de ei nu există înafara acesteia. Aceste variabile sînt deci diferite de cele desemnate cu acelaşinume în program prin declaraţia

var a , b, c, s : real;

Variabilele a, b , c astfel declarate nu sînt cunoscute în corpul funcţiei.Doar s este cunoscută în tot textul programului P3, deci şi în corpul funcţiei

85

aria. Spre deosebire de a, b şi c, s nu a fost redefinită în corpul acesteia. Elrămâne o variabilă globală pentru funcţie.

Aceste observaţii sugerează că alegerea numelor parametrilor formalieste la latitudinea programatorului, fără grijă pentru coliziune de notaţii, fapt careuşurează mult programarea. Devine astfel posibilă realizarea de subprogramescrise ca funcţii Pascai de către persoane diferite. Pentru a asigura comunicarea

între aceste subprograme este suficient să se convină asupra arităţii lor, adicăasupra numărului de parametri formali şi asupra tipului lor, nu şi asupra numelorlor, care pot să coincidă sau nu în declaraţii diferite de funcţii.

Funcţia ar ia putea fi declarată folosind de exemplu parametrii formali x,y, z astfel:

function aria (x, y, z: real) : real; var p :real; begin

p := (x + y + z) / 2 ;aria := sqrt(p * (p - x) * (p - y) * (p - z)) end;

{aria}

şi invocată prin ar ia ( a, b , c) sau prin ar ia (3, 5, 6 ), etc.

Prin această ultimă chemare, valorile specificate de parametrii actuali 3,5, 6 sînt transmise drept valori ale parametrilor formali a, b, c cu efectelespecificate mai sus.

Exemplu. Funcţia compl din programul următor calculează complementaraunei mulţimi x relativ la o altă mulţime e. Tipul rezultatului este pointer, deoareceutilizarea unui tip structurat este interzisă în această situaţie.

type mu lti me= set of 0.. 255;pm= "mu lţi me; function

compl(e,x:mu lţ im e) : pm; var p: pm;begin

new(p); pA:=e - x ; compl: -p;

end;var a,b,e: mulţime;begin

a:-[0,5,7,3,9]; 'b:=[2,7,8,12,34,3] ; e:-[0. .255] ;{Verif icarea r eguli lor lu i De Morgan}writeln( compl(e, a + b) A = compl(e, a ) * * compl(e, b ) A ) ;wri tel n( compl (e, a * b) * = compl (e, a ) * + compl (e, b ) *') ;

end.

43. Proceduri

Conceptul de procedură extinde pe cel de instrucţiune. Formele sintacticeale declaraţiei şi apelului sînt similare celor pentru funcţii.

4.3.1. Declararea procedurilor

Definirea unei proceduri Pascal se face în conformitate cu următoarele

diagrame de sintaxă:<procedura>—i-------> <antet_piocedura> — ; —|--> <corp> ----1- -,—> ; -- ->

86

4.2. Funcţii

| l—> <directiva> —1 |> procedure —> <identificator> —> ; —> <corp> —1

<antet^procedura> i-----------; <---------^—------■> procedure—<identificatoi>—I—(—l—<param_formal >—■—)-,—>

Forma generală a textului unei declaraţii de procedură este: procedura p

(x1(\. . .; x„) ;Di;

begin

end;

{p}

în antetul procedurii apar:- p: numele procedurii;- (x1(- . . ;x„) : listă (opţională) de parametri formali, încorpul procedurii sînt incluse:- D x : declaraţii locale procedurii (opţionale) grupate după aceleaşi reguli ca încazul funcţiilor;- begin.. .end; : instrucţiune compusă; ea nu conţine vreo atribuire asupranumelui procedurii.

Procedura poate să întoarcă mai multe rezultate dar nu prin numele ei, ci

prin variabile desemnate special (cu prefixul var) în lista de parametri; tipurilerezultatelor se specifică în lista de parametri ca tipuri ale acestor variabile.

4.3.2. Apelul procedurilor- ■

Activarea unei proceduri se specifică printr-un apel de forma:p(a l f . . . ,an)

cu- p: numele procedurii;- (a£,... ,a„): lista (opţională) de parametri actuali.

Spre deosebire de funcţie, apelul de procedură este o instrucţiune; aceasta se inserează în

program în locul în care sînt dorite efectele produse de execuţia procedurii pentru eventualiiparametri actuali a lt . . . , an.

4.3.3. Exemple

Textul de program din 4.2.3 pentru calculul ariei unui triunghi poate fi rescris ca oprocedură Pascal astfel:

pxoceduxe aria(a, b, c : real ; var s : real); var p : real ; beginp := (a + b + c) / 2 ;

s := sqrt(p * (p - a ) * (p - b) * (p - c ) ) end;{aria} .

Anteml procedurii

87




procedure aria(a, b, c : real ; var s : real);

conţine numele ei şi declaraţiile parametrilor formali a, b, c şi s. Restul textului estecorpul procedurii; el conţine o declaraţie şi o instrucţiune compusă. Observăm că, spredeosebire de funcţii, în antet nu mai apare o specificaţie a tipului rezultatului; de asemenea,numele procedurii nu apare în partea stingă a unei instrucţiuni de atribuire din corpul ei.Notăm în sfîrşit forma specială în care este declarat parametrul formal s în antet:

var s : real ;

Acesta este acum parametru variabilă şi va fi folosit pentru întoarcerea unuirezultat din procedură; a , b, c sînt parametri valoare şi servesc, ca şi la funcţii, pentruacceptarea de valori transmise procedurii.

Programul are acum forma:

program P4;var si : real;

procedure aria (a, b, c : real; var s : real); var p : real ;begin

p (a + b + c) / 2;s := sqrt(p * (p - a) * (p - b) * (p - c ) ) end;

{aria}

beginaria( 3 , 4 , 6 , s i) ; wri teln(si) end; {P4}

Execuţia instrucţiunii ar ia (3 ,4 ,6 , s i ) determină transmiterea valorilorprimilor trei parametri actuali drept valori ale parametrilor'formali a, b, c şi a locaţiei

parametrului actual si drept locaţia parametrului formal s. Observăm că sl este ovariabilă. Ea corespunde parametrului formal s, declarat cu vax. Invocarea proceduriidetermină efecte echivalente următoarei instrucţiuni compuse:

beginp := (3 + 4 + 6) / 2;sl := sqrt(p * (p - 3) * (p - 4) * (p - 6) )

end;

4.4. Programe 4.4.1. Forme

sintactice; exemple

Sintactic, forma generală a unui program aminteşte pe cea pentru funcţii şiproceduri:

program P(x1( . . . ,xn) ; D;

begin

. end. {Pl unde P este numele

programului.

Ca şi la funcţii / proceduri declaraţiile D sînt grupate în secţiuni (eventual vide)labei, const, type, var, funct-ion / procedure, scrise în această ordine; similar se definescantetul şi corpul programului. în implementarea Oregon regulile pentru declaraţiiledin lista D sînt mai puţin stricte (vezi 4.6.1.2). De asemenea, antetul programuluieste opţional.

88



4.2. Funcţii

Parametrii formali specificaţi în lista (xv, .. . ,x„) denotă entităţi (de regulă fişiere)de comunicare a programului cu mediul său. Aceste entităţi (în afara fişierelor standardinput şi output) trebuie declarate în program.

Specificarea identificatorilor input sau output ca parametri formali aiprogramului are ca efect declararea implicită a acestora ca fişiere text şi executareaimplicită a apelurilor de procedură reset (input), respectiv rewri te (output) la

începutul fiecărei activări a programului (vezi 2.2.4.1.2).Corpul programului este urmat de ' . ' şi nu de ' ;" ca în cazul funcţiilor şi

procedurilor.

Exemple:

program copie ( f , g ) ;var f , g : fil e of real; begin

reset(f); rewrite(g); while noteof ( f ) do4.4.Programe

93

begin g " : = f * ;put(g) ; get( f)

endond. {copie}

Parametrii formali f şi g din antet sînt declaraţi în corpul programului drept fişiere denumere reale. Instrucţiunea compusă care urmează descrie partea de acţiune a programului:copierea fişierului f în fişierul g.

Programul copietext care urmează foloseşte parametrii formali i nput şi ou tputpredefiniţi ca fişiere standard de intrare / ieşire. Ei nu vor fi declaraţi în program. Partea deinstrucţiuni determină la execuţie copierea, linie cu linie, a fişierului de intrare în fişierul de ieşire,păstrînd structura liniilor.

program copietext ( input, output); varch: char; begin

while not eof do beginwhile not eoln dobegin

read(ch); write(ch)end;writeln; ieadln

end

end. {copietext}

4.4.2. Structura statică a programelor

Funcţiile / procedurile sînt declarate în programe şi pot să conţină, la rîndul lor, declaraţiiale altor funcţii / proceduri la orice nivel. Relaţia de incluziune a declaraţiilor de funcţii, procedurişi program defineşte structura statică a programului. Ei i se poate ataşa o reprezentarearborescentă în care:- programului / funcţiilor / procedurilor le corespund noduri marcate cu numele lor P, 0, R, . . . ;- dacă P conţine declaraţia lui Q, reprezentăm structura statică a lui P prin arborele

Q

89




- dacă P conţine declaraţiile lui Q şi R, în această ordine, reprezentăm structura statică a lui pprin arborele

PExemplu. Fie programul:

program P;procedura Q; begin

. . .end; { Q }

procedure R ;function S; begin

end; { S }

begin

end; { R } begin

end. { P 1

Reprezentăm structura statică a lui P prin arborele:

P

/ \Q R

I

s

4.4.3. Domenii de vizibilitate a declaraţiilor

într-un program care nu conţine declaraţii de funcţii / proceduri, pentru oriceidentificator x al său există o singură declaraţie dx. Orice referire rx a lui x în program are învedere obiectul definit de această declaraţie. Declaraţia şi referirile au loc în acelaşi program. Amvăzut cum declaraţii de funcţii / proceduri în alte funcţii / proceduri conduc la structuri deprograme cu mai multe nivele. Aceasta, împreună cu libertatea de alegere a numelor înprogram, fac posibil să existe, pentru acelaşi identificator x, mai multe declaraţii diferite în unităţide program diferite. Fiecare astfel de declaraţie defineşte un alt obiect Aceiaşi identificator poatedeci desemna (numi) obiecte diferite în diferite părţi ale programului.

De asemenea, în program pot să apară mai multe referiri r x ale identificatorului x.Fiecare astfel de referire are în vedere obiectai x definit de o anumită declaraţie d x .

4.43.1. Domenii de vizibilitate ale declaraţiilor de identificatori

Definiţia 1. Fie P un program / procedură / funcţie, x un identificator şi dx o declaraţiea lui x în P. Se numeşte domeniu de vizibilitate al lui dx textul de program în care pot aparereferiri rx la identificatorul x ce desemnează obiectul definit prin declaraţia dx.

Domeniul de vizibilitate al lui d^ începe imediat după terminarea declaraţiei şi sesfîrşeşte odată cu p. Trebuie precizat că declaraţia unei funcţii / proceduri se consideră terminatăla sfîrşitul antetului; acest fapt face posibil apelul recursiv: în corpul funcţiei / procedurii, aceastapoate fi referită, fiind vizibilă.

Exemplu: în programul următor, începuml domeniilor de vizibilitate este marcat princomentarii, program P; const n = 3 ;{de aici n devine vi zi bi li type natural =0..maxint; {de aici natural devine

vizibil} function f ( x : natural{de aici x devine vizibil} ) : natural; {de aici f devine vizibila} begin

90



4.2. Funcţii

if x - 0 then f := 1 {deci f poate fi referit} else f := x* f (x - l )end;beginend.

Exemplu. Următoarea declaraţie a tipului arbore este eronată:

type arbore - recordinfo: char;stingă: " arbore; {eroare, referinţă înainte

ca arbore să devină vizibil}dreapta:* arbore; end;

{numai de aici arbore devine vizibil}

Domeniul de vizibilitate al unei declaraţii dx nu este neapărat o porţiune continuă dintextul programului. Apariţia într-un subprogram Q, din domeniul de vizibilitate al declaraţiei d,, aunei alte declaraţii d' x (ce implică acelaşi identificator x) provoacă acoperirea domeniului devizibilitate al declaraţiei prin domeniul de vizibilitate al declaraţiei d' x . Acoperirea se produce dela începutul declaraţiei dx, în timp ce noul domeniu de vizibilitate începe de la terminareadeclaraţiei d;.

Exemplu. Re programul următor:

program P; const c =1;

{a ic i începe domeniul de vi zi bi li ta te al lu i d c} procedure q; const{aici începe acoperirea lui dc pr in d j }c = .

c + l ; {expr esie in corec ta} {aici începe domeniul de

vizibi l itate a lui d'c}

begin

end {q} ; beg in. . . end.

Expresia c + l este incorectă: referirea Ia c se face după acoperirea de-claraţiei din programul principal şi înainte de a deveni vizibilă declaraţia din proceduraq.

Exemplu. în programul

program P; type t =

0 . . 1 0 ; procedure q; var t : t ; {eroare}begin

end;

end.

declaraţia din procedura q este eronată. Intenţia a fost de a se declara o variabilăiocală t, de tipul global t (definit în programul principal). Referirea ia identificatorul t dedupă ' : ' nu este însă în nici un domeniu de vizibilitate; cel din programul principal afost acoperit (la începutul declaraţiei var t: t;), iar cel din procedura q începe de abia lasfîrşitul acestei declaraţii.

Deci în Pascal domeniul de vizibilitate ai unei declaraţii se deterrnină static; eldepinde doar de poziţia declaraţiei în textul programului şi se poate stabili lacompilare ca şi în Algol, PL/1 şi alte limbaje cu structură de bloc; conceptul de bloc din

91




aceste limbaje (instrucţiune compusă cu declaraţii locale ei) diferă însă de cel dinPascal (funcţie / procedură cu eventuale declaraţii locale şi o instrucţiune compusă). înalte limbaje de programare (Lisp, Snobol, APL,...) domeniile de vizibilitate se stabilescdinamic (la execuţie).

Exemplu. în programul

program P ; type i =integer; {1}procedure Q; var

x : i ;{2} i : real;{2.1} begin

end;{3} begin

end { 4 } .

mo

domeniul de vizibilitate al declaraţiei i - integer este textul cuprins intre punctele marcate{1} şi {4} mai puţin textul cuprins între punctele {2} şi {3}. Domeniul devizibilitate al declaraţiei i : real este cuprins între punctele {2.1} şi{3}.

. Exemplu. Stabilirea domeniului de vizibilitate este importantă pentru corec-titudinea apelurilor de funcţii / proceduri. în programul program p;

procedura q;procedura r;

procedura u;begin {u }u ; r ;q ; and;

{u } begin { r }U ; r ;q ; end;

{r } proceduie s;procedura t ; begin

t ; s ;q ; r ; end;{t } begin {s }s ;q ; r ; t ; and;

{s } begin { q }q ; r ; s ;

and; { q}

begin {p}

end. {p}

cu arborele de structură staticăP!q

■■'■'■> rot

XQ

r s

i l

sînt peimise numai apelurile specificate în program.

O consecinţă a regulii de stabilire a domeniului de vizibilitate este faptul că oricereferire r, în P trebuie precedată de o declaraţie d, în P sau într-un program / funcţie /procedură care include P. Singura excepţie o constituie referirea tipului dî bază T din

92



4.2. Funcţii

definiţia unui tip pointer, care poate precede declaraţia lui T; totuşi, declaraţia lui T trebuiesă apară în aceeaşi parte de declaraţii de tip cu tipul pointer.

Exemplu. Declaraţiile următoare:

typeptr = * nod;nod = xecoxd

Sting: ptr; informaţie:real; drept: ptr; end;tf

sînt corecte, deşi declaraţia tipului nod apare după referirea sa în declaraţia tipuluipointer ptr.

4.43.2. Domenii de vizibilitate pentru alte declaraţii

Ca şi identificatorii, etichetele pot fi definite şi referite în program. Domeniul devizibilitate al unei definiţii de etichetă se stabileşte similar cu cel al declaraţiiloridentificatorilor.

Specificaţia unui identificator constantă drept componentă a unui tip enumerareare acelaşi domeniu de vizibilitate cu declaraţia acestui tip.

Domeniul de vizibilitate pentru o specificaţie de identificator selector de cîmp(proiecţie canonică) într-o înregistrare este textul definiţiei tipului înregistrare în care apare.Acest domeniu poate fi extins la textul eventualei instrucţiuni with în care se specificănumele înregistrării. Un astfel de identificator poate fi referit şi în afara domeniului devizibilitate, dar nu direct ci calificat de numele înregistrării. O astfel de referire poate fifăcută în tot domeniul de vizibilitate al declaraţiei înregistrării.

Exemplu: în programulprogram p;typo rec = record

x: real;(1} y : record{2} x: integer;{2 .1} t : integer;

end; {3}end; {4}var x: boolean;{5} v : rec;

beginx:= true;v. x: = 1.2;v .y .x :=12; with v do

{6} beginx:= 12 .5 ;y . t := 7 ;end; {7}end. {8}

■■■■

- declaraţia x: real are ca domeniu de vizibilitate textul cuprins între punctele { l} -{4} cu excepţia celui dintre {2} - {3} ; el este extins cu textul {6}-{7} prininstrucţiunea with;

- declaraţia x: integer are domeniul de vizibilitate {2.1}-{3};- declaraţia x: boolean are domeniul de vizibilitate {5} - {8} cu excepţia celui dintre{6} - {7} .

93




- în afara domeniilor de vizibilitate (extinse), selectorii de cîmpuri x sînt referiţi princalificare completă cu numele îmegtetrărilor: v. x, v. y. x.

ik34.43.3. Context asociat unei unităţi de program

Prin unitate de program înţelegem un program, o funcţie sau o procedură.Fie P o unitate de program şi x un identificator declarat în P (în lista lşlf . . ., xn)

a parametrilor formali sau în declaraţiile D); x desemnează un obiect focal lui P. Dacăacest obiect este vizibil într-o funcţie / procedură o declarată în ?, atunci el este globalrelativ la Q, fiind "moştenit" din P.

Definiţia 2. Numim context asociat unei unităţi de program mulţimea obiectelor

vizibile în ea (locale sau globale).Conceptual, este util să considerăm ca predefinită o unitate de program fictivă încare este inclus (declarat) orice program. Entităţile locale acestui-program fictiv sîntconstantele, tipurile, variabilele, procedurile şi funcţiile predefinite (vezi anexa 4). Acesteadevin astfel globale relativ la orice unitate de program şi extind 2stfel contextul asociatacesteia. în lipsa unei precizări contrarii, o referire lâ contextul asociat are în vedereaceastă extensie, numită şi context (spaţiu) de execuţie.

Unei declaraţii îi corespunde pe lîngă domeniul de vizibilitate şi undomeniu de timp.

Definiţia 3. Se numeşte durată de viaţă ("extern") a unei declaraţii timpulcît există la execuţie obiectul definit prin declaraţie.

în Pascal, durata de viaţă a unui obiect declarat într-o unitate de programP este timpul cît durează execuţia lui P.

Durata de viaţă a unei variabile dinamice (vezi 2.7) este cuprinsă întremomentul creării sale (prin apelul procedurii naw) şi momentul dealocăriispaţiului să u (prin apelul procedurii dispose) sau, în lipsa unei dealocăriexplicite, pînă la sfîrşitul execuţiei programului.

4.5. Comunicarea între unităţi de program

Am văzut cum limbajul Pascal permite definirea de funcţii şi proceduripentru a descrie părţi autonome de program care asociază un nume cu declaraţiide obiecte locale şi cu o instrucţiune compusă.

Definiţia unei funcţii / proceduri se face în partea de declaraţii a uneiunităţi de program. Referirea ei se poate face prin apeluri în instrucţiuni aleunităţilor de program din domeniul de vizibilitate al definiţiei. Fiecare apel solicită

executarea acţiunilor din instmcţiunea compusă a funcţiei / procedurii asupra"datelor" particulare locului de chemare. Prezentăm în continuare mijloacele princare aceste date sînt comunicate funcţiei / procedurii, iar rezultatele produse sînt

întoarse în locul de apel. în Pascal comunicarea se poate face prin entităţi globale şi prinparametri.

4.5.1. Comunicarea prin identificatori globali

Un identificator global relativ la o procedură este declarat în afara ei într-un program / funcţie / procedură ce o cuprinde, fără a fi redeclarat în ea. El estecunoscut deci în procedură cu semnificaţia dobîndită în afara ei, constituind

astfel un mijloc de comunicare de la locul de apel la procedura apelată.

94



4.2. Funcţii

Comunicarea îrî sens invers este de asemenea asigurată: efectele asupraunui obiect global referit în procedură devin cunoscute în afara acesteia (în totdomeniul de vizibilitate al declaraţiei asociată referirii).

Procedeul se mai numeşte şi comunicare prin parametri impliciţi şi a fostilustrat prin exemplele de la începutul capitolului.

4.5.2. Comunicarea prin parametri

Limbajul permite şi specificarea explicită a interfeţei între funcţie / procedură şiprogramul / subprogramul care o apelează.O listă de identificatori locali ai funcţiei / procedurii specificaţi în antetul

acesteia drept parametri formali este pusă în corespondenţă biunivocă cu o listăde parametri actuali specificată în apel. Corespondenţa se realizează întreparametrii din aceeaşi poziţie în cele două liste, cei actuali avînd tipuri identice cucei formali corespunzători. .

La execuţia apelului valorile parametrilor actuali sînt substituite parametrilorformali astfel că acţiunile instrucţiunilor funcţiei / procedurii au loc asupra acestor valori, cuefecte la locul de chemare.

Există patru feluri de parametri formali:- parametri valoare- parametri variabilă- parametri funcţie

- parametri procedură.■ Parametrii valoare sînt cei obişnuiţi în Pascal. Ei nu sînt semnalaţi deci în vreun

mod special. Ceilalţi parametri sînt semnalaţi în antet prin prefixele var, f unction şirespectiv pzoceduze.

4.5.2.1. Parametri valoare

Parametrii valoare reprezintă mijlocul comun în Pascal pentru comunicarea datelorde la locul de apel spre funcţia / procedură apelată.

Un astfel de parametru se declară în antetul funcţiei / procedurii prin numele săuurmat de specificaţia de tip. De exemplu:

pzoceduze q (n: integer; x, y : real);

Parametrul actual corespunzător este o expresie a cărei valoare are tipul celuiformal (prin excepţie, unui parametru formal de tip real poate să-i corespundă şi o expresiecare se evaluează lâ o valoare de tip integer).

Exemplu. Apelurile următoare sînt corecte: ,

q (3, 1.3, 7.) ; :q(i, j, k) ; { i, j, k : real}q (7, j, 8 + 7 div 3) ;

Substituţia implicată de parametrii valoare are loc conceptual astfel: la apelulfuncţiei / procedurii se alocă spaţiu pentru parametrul formal, se evaluează expresiaparametrului actual şi valoarea rezultată se depune în acest spaţiu drept valoare curentă aparametrului formal. Acesta capătă de acum statut de variabilă locală. El poate fi referit în

funcţie / procedură, valoarea sa poate fi modificată aici, fără vreun efect în afara ei.Valoarea dobîndită astfel de parametrul formal se pierde la revenirea în program.

Observaţii: •

95




1.Această substituţie a parametrilor formali valoare este cunoscută sub numelede transmitere (referire, apel, chemare ...) prin valoare. Ea este folosită şi de alte limbaje deprogramare (ALGOL60, SIMULA, Ada...) [WaGo84].

2.Dacă parametrii actuali sint de tipuri structurate şi de dimensiuni mari, unspaţiu de memorie de aceeaşi mărime este irosit pentru parametrii formali, iar copiereavalorilor celor actuali în acest spaţiu consumă timp. Transferul prin parametrii variabili est»preferabil în astfel de cazuri, cu deosebire dacă nu se fac atribuiri asupra parametrilwformali (vezi 4.5.2.2 şi 4.5.3).

3.Fişierele sau Variabilele structurate cu componente fişiere nu pot fi parametriactuali valoare.

4.5.2.2. Parametri variabilă

Parametrii variabilă reprezintă mijlocul principal de recuperare a rezultatelor dinprocedura apelată.Parametrul formal se declară în antet sub forma

vai n : t;

unde n este numele iar t tipul său.

Exemplu: Antetul

procedure s(x : real; var y, z : integer);

conţine parametrii variabilă y şi z. Ei se recunosc ca atare prin prefixul var. Parametrul xnu ar» vreun prefix, el fiind deci un parametru valoare.

Parametrul actual corespunzător unui parametru formal variabilă este unidentificator de variabilă (simplă, componentă a unui tablou, a unei înregistrări sau a uneicombinaţii a acestora, dar nu o componentă a unei structuri de date împachetate).

Substituţia implicată de parametrii variabilă constă în asocierea locaţieiparametrului actual cu parametrul formal corespunzător, astfel încît, pe durata apelului,orice referire la parametrul formal este de fapt o referire la parametrul actualcorespunzător.

Astfel, o atribuire asupra parametrului formal devine cunoscută în afara proceduriiprin schimbarea valorii parametrului actual.

Observaţii:1. Acest mod de substituţie este cunoscut şi sub numele de transmitere

(referire, apel, chemare...) prin referinţă (adresă ...). El este folosit şi în alte

limbaje (FORTRAN, Ada...). Sînt, de asemenea, implementate şi alte mecanismede substituţie: apel prin nume (ALGOL60), prin rezultat (Ada), prin valoare -rezultat (FORTRAN, Ada) etc. [WaGo84].

2. Parametrilor formali variabilă li se vor asocia parametri actuali distincţi.

Parametrii actuali sinonimi produc efecte neaşteptate în program (vezi 4.5.3).3. Deşi destinaţi recuperării de rezultate din procedură, parametrii variabilă sîntfolosiţi ocazional şi pentru comunicarea spre procedură. Este cazul parametrilor actuali detipuri structurate (azzay, record sau combinaţii ale lor) care, transmise prin valoare, arimplica risipă de spaţiu (alocat parametrilor formali) şi de timp (pentru copierea în acestspaţiu a valorilor parametrilor actuali).4. Toate calculele de adrese se fac la intrarea în procedură (de exemplu evaluareaindicilor componentelor de tablouri).

Exemplu: Programul următor ilustrează comunicarea prin variabile globale,parametri valoare şi prin parametri variabilă.

program P;

96



4.2. Funcţii

var x, y , z : integer; procedure Q(y : integer; var z

begin x : = x + 1; y : = y +writeln (x , y, z)

end; {Q} begin x := 0; y : -0; z : - 0 ;

writeln (x , y, z) ;0 (x , y ) ;writejn (x, y , z) ; end. {P}

Relativ la procedura 0, identificatorul x este global, y este parametru valoare,iar z parametru variabilă.

în program x , y , z primesc valorile o care sînt scrise: 0, 0 , 0 .

Prin execuţia apelului Q (x, y), variabilele desemnate prin identificatorii x(global), y (din procedură şi din program) şi z (din procedură) primesc valorile l care sîntscrise: l , l , l. La revenirea în program variabila cu numele x (global) păstrează valoareal dobîndită în procedură; variabila y din procedură dispare, valoarea sa nefiind păstrată învreun fel, deci y din program continuă să aibă valoarea o pe care o dobîndise aici; z dinprogram dispare dar valoarea 1 atribuită lui în procedură se recuperează ca valoare a lui zdin program. Valorile lui x, y, z din program sînt scrise: 1, o, l. Valoarea lui y diferă decele ale lui x şi z, deşi de flecare dată s-au specificat transformări similare asupra identi-ficatorilor x, y, z. Chiar valorile variabilelor x şi z, deşi egale, sînt dobîndite pe căi diferite.

4.5.2.3. Parametri formali funcţie / procedură

O funcţie / procedură poate fi desemnată drept parametru formal al altei funcţii /proceduri prin specificarea ei în lista L din antetul acesteia. O specificaţie de funcţie /procedura ca parametru formal are forma antetului acelei funcţii / proceduri incluzîndparametrii săi formali şi tipurile lor, iar pentru funcţii şi tipul rezultatului. De exemplufunction f(x, y : integei) : real;Şi

procedure p(z : real) ;

apar ca parametri formali in antetul procedurii cp

procedura q (function f (x , y: integex) : rea l ;procedura p(z î rea l); vaxn : re al );

Un apel al lui q ar putea fi

q(u, r, a)unde parametrul actual u este numele unei funcţii

function u(m, n : integer) : real ; begin . . .and; {u}

iar parametrul actual r este numele unei proceduri r cu antetul

procedura r(b : real);

Observaţie. Funcţiile / procedurile predefinite nu pot fi transmise ca parametriactuali funcţie / procedură. De exemplu apelul procedurii p în forma p (s in) nu estecorect, deoarece sin este o funcţie predefinită. Inconvenientul poate f i însă depăşitdefinind o funcţie sini

function si nl (x : real) : re al ; beginsini != Sin(x)and; {sini}

: integer); 1;z := z + 1;

11,1,1}

{0 ,0 ,0}

{1,0,1}

97




care poate ti folosită în apelul p(sini) cu efectul doritExemplu. Programul Ecdif conţine declaraţia procedurii Runge care

specifică funcţia f drept unul din parametrii săi formali: .

procedura Runge(function f(x, y : real) : real ;xO, y0, h : real;

n -tt- integer;var vx, vy : vector) ;

De asemenea, în partea de declaraţii a corpului programului sînt definite douăfuncţii gl şi g2:

'":

function gl (x , y : real) : real ; function g2(x, y : real) : real;

Procedura Runge este apelată de două ori în partea de instrucţiuni a

corpului programului. Primul apel specifică, printre altele, pe gi drept parametru actualcorespunzind parametrului actual de tip funcţie f:

Runge(gl, 0, 1, 5.7, h, vl, v2);

Similar pentru cel de-al doilea apel şi funcţia g2. Urmează enunţul problemei, algoritmulfolosit şi programul Pascal autodocumentat prin comentarii.

Problema: Integrarea ecuaţiilor diferenţiale de forma y' - f(x, y) în condiţiile iniţiale y (x,,) -ye.Algoritmul: foloseşte metoda Runge-Kutta de ordinul patru cu pas constant h; pentru i - 0 ,1,. .. , n -l : Xi.i - x± + h şiyi.i ' Y i * 1/6- (ki + 2-kj + 2-k, + k4) + O( h) unde kx - h- f (Xj , yt) ka - h« £ ( X i ♦ 1/2-h, yj + 1/2-k,,) k, - h ' t (Xj + 1/2«h, yt + 1/2-k2) k t - h-f (Xi + h, yt + kj) Cîte n valori pentru xşi y smt acumulate în vectorii vx şi vy pentru a fi întoarse în punctul de apel.

progxan Ecdif;

{în piogram se declară procedura Runge şi funcţi i le gl şi g2; se apeleazăRunge de două o ri pentru integrarea ecuaţiilor diferenţiale y' = gl(x, y),respectiv y' - g2(x, y).1

• . • -

con«t h - 0.001; n - 10; e - 2.71828;typa vector - axray [ l . .n] of real ;var 3 : xnteger; v l, v2 : vector;

procedura Runge (function f(x, y: real): real; xO, yO, hs real;n: integer; var vx, vy : vector);

{Procedura pentru integrarea ecuaţiilor di ferenţiale de forma y' = f(x,y) in condiţiile iniţiale y( x0)« y0 prin metoda Runge-Kutta de ordinul 4 cupas constant h şi n iteraţii)

var x, y , kl , k2 , k3 , k4 : real; i: integer;

bagin x xO; y :- yO {iniţ ial izări] for i := 1to n do {n iteraţi i} bagin kl h * f (x,y);

k2 h * f(x + h/2, y + kl/2); k3 h * f (x + h/2, y + k2/2); k4 : -h * f( x + h, y + k3) ;

98



4.2. Funcţii

4.5 .4. Tablouri ca parametri

Definiţia iniţială a limbajului nu permite folosirea nemijlocită a tablourilor cudimensiuni variabile drept parametri formali în funcţii şi proceduri, făcînd necesarămodificarea şi recompilarea acestora pentru apeluri cu alte dimensiuni ale parametriloractuali tablouri.

Un remediu constă în declararea tablourilor cu dimensiuni specificate prinidentificatori de constante care sînt definite (şi modificate) anticipat.

Exemplu. (Vezi 4.52.3, programul Ecdif) . I nsecvenţa de program c o n s tn •

10;t y p e vector - a x x a y[l..n] o freal;

p r o c e d u r eRunge (... v a r vx,, vy : vector; ...)• • ■

tablourile vx şi vy de tip vector sînt folosite ca parametri formali ai procedurii Runge.Valoarea 10 este asociată cu n dar ea poate fi modificată (la 100 de exemplu) prinsimpla redefinire a constantei (const n - 100), fără vreo modificare în textul procedurii.

Acelaşi efect s-ar obţine definind tipul în forma

type vector - axray [1..10] of real

şi redefinindu-1 cu

type vector = axzay [1..100] of real.

Prima variantă este desigur preferabilă. Un apel al procedurii ar putea avea

99

end;{for}end; {Runge}■ '. • ■ .. rfunctiongl(x,y: real): real;begin•gi :•■ -2 * x* sin(x)end;{gi}function g2(x, y :real) :real;beging2 î- 1 + (x-y) / (x +ln(y))end;{g2}•beginRunge(gi, o,1.57,

h.n, vl, v2);lapel al lui

y :- y + f(kl + 2 * k2,2*k3+k4)/6; x x + h; {semodifică x} vx[i] := x; {se reţinx şi y) vy[i] := y

Runge pentru integrarea ecuaţiei y' - gl(x,y) in condiţiile iniţiale y(0) - 1.57 }

writeln (' x y(x) pentru y''-gl(x,y)');for j := 1 to n do writeln (vl[j ], v2[j ]) ;writeln;Runge (g2, e., e + 1, 1E-2, n, vl, v2); {apel al lui

Runge pentru integrarea ecuaţiei y'=g2(x,y) in condiţiile iniţiale y'te) = e + 1 }

write (' x y(x) pentru y''-g2(x,y)');fox j 1 to n do writeln (vl[j], v2[j ]) and.{Ecdif}

forma

Runge {. . . v i , v2, .. .)

unde tipul tablourilor vl şi v2 este definit anticipat prin

var vl, v2 : vector;

Ultimul standard al limbajului oferă ca soluţie alternativă (nepreluată în PascalOregon) folosirea drept parametri formali valoare sau variabilă a schemelor de tablouri,adică a specificaţiilor de tablouri cu dimensiuni parametrizate definite prin diagramele desintaxă:

<schema de tablou>—|—|—packad mxxmy— [—<dimensiuni>—]—of-^—rrj—><id_de_tip>^>

| 1----> azzay------[—{—<dimensiuni>—]—]—of—|—'I ;<-----H II-----------!--------------i----------------------------------.-----------------•-- - -'

<dimensiuni>----■.—> identificator—>..—> identifica tor—> : —> <id_de_tip> >

4.5.2.5. Structura dinamică a programelor

în 4.4.2. am mtrodus structura statică a programelor. Ea are în vedere textulsursă* al programului, punînd în evidenţă unităţile de program componente şi este unicăpentru un program dat. Toate consderaţiile care au urmat au avut în vedere aceastăstructură statică şi este remarcabil că principalele informaţii necesare la compilare

(domeniile de vizibilitate a declaraţiilor, legarea identificatorilor la declaraţii ..) sînt obţinuteprin explorarea acestei structuri.

Folosirea funcţiilor /procedurilor face utilă luarea în considerare şi a structuriidinamice (la execuţie) a programelor.

Structura dinamică este unică pentru o activare a programului (a părţii sale deinstrucţiuni) în condiţii iniţiale date, dar poate să difere la schimbarea condiţiilor iniţiale. Eaare în vedere succesiunea activărilor unităţilor de program (funcţii / proceduri) componente(a părţii lor de instrucţiuni) şi poate fi reprezentaţi folosind graful apelurilor (pentru exemplevezi 4.5.4.2) sau modelul conturului al mi Dijksrra [WaGo84].

Fiecare activare a unei funcţii / proceduri produce ipostaze proprii ale contextului asociat(vezi 4.4.3) obţinute prin:

a) crearea de copii proprii ale entităţilor locale (etichete, variabile, funcţii,proceduri);

b) crearea de variabile proprii pentru identificatorii folosiţi ca parametriformali valoare;c)stabilirea de legături (referinţe) de la identificatorii folosiţi ca parametri formali

variabilă / funcţie / procedură la parametrii actuali corespunzători.Copii multiple de entităţi cu declaraţii identice pot să existe în acelaşi timp, în

contexte proprii ale activărilor recursive (vezi 4.5.4).Dacă Q este declarat în p, atunci contextul propriu unei activări a lui Q este

scufundat în contextul asociat (declaraţiei) lui p, nu în contextul propriu activării unităţii deprogram care a provocat activarea lui Q.

O referire r x a identificatorului x într-o activare a unităţii de program Pare în vedere obiectul specificat prin declaraţia dx vizibilă în acel loc; el sedetermină la compilare explorînd structura statică a programului. Specificareaatributelor acestui obiect este însă, de regulă, incompletă la momentul compilării.Astfel, pentru o variabilă definită prin cvadruplul ■ '

<nume, tip, locaţie, valoare>

100

4.2. Funcţii

doar numele şi tipul sînt specificate în declaraţia corespunzătoare din textul programului;locaţia şi valoarea vor fi determinate la execuţie, folosind structura dinamică a programuluicorespunzătoare acelei execuţii. ;:.

Regulile de completare a informaţiei de legare a identificatorilor l a entităţile ce lecorespund se numesc reguli de activare şi, pentru Pascal, ele sînt următoarele:

- dacă identificatorul este local, el corespunde ipostazei conţinute în contextulpropriu al activării;

- dacă identificatorul este parametru formal valoare, el se referă la variabila creatăpentru acesta, în contextul propriu al activării;

- dacă identificatorul este un parametru formal variabilă / funcţie / procedură, else referă la entitatea la care conduce legătura (referinţa) stabilită în contextul propriu alactivării.

Observaţie. Dacă identificatorul numeşte o entitate externă, legarea lui la aceaentitate se completează la momentul editării task-ului (vezi 4.7 şi 7).

4.5.3. Efecte secundare Ia execuţia funcţiilor şiprocedurilor

Singurul mod în care execuţia unei funcţii trebuie să influenţeze mediul (contextul)din care este apelată este prin valoarea pe care o întoarce, atribuită numelui ei, în locul deapel. Orice altă schimbare în acest; mediu produsă de execuţia ei este un efect secundarcare poate influenţa în mod neaşteptat execuţia programului.

Prezentăm în continuare practici defectuoase de programare care produc funcţiicu efecte secundare la execuţie.

4.5.3.1. Atribuiri asupra variabilelor globale •;:-

vrt-:.{.

Valorile dobîndite de variabilele globale în corpul func ţiei devincunoscute în afara ei (în unităţile de program din domeniile de valabilitate aleacestor variabile). Execuţia unei astfel de funcţii va influenţa mediul de chemarenu doar prin valoarea întoarsă, ci şi prin alterarea valorilor variabilelor globale.

Exemplu.

program p;var a , b : integer; var x : real; ].

. function f(c : real) : real; -begin

a : - 7 ; b : - 3; f : » a + h.. . '.• . end; { f}

,-, . •begina : - X ; b : - 2; X := f '<5)/10| .wr i te ln (a ,b ,x )end.

în programul p variabilele a şi b -s în t globale relativ la funcţia f.Fun cţ ia este invocată în program în expresia f (5) /10; la execuţie ea întoarcevaloarea 15 atribuită numelui ei f. Pe lîngă aceasta însă, atribuirile făcute asupravariabilelor globale a şi b produc, ca efect secundar, alterarea valorilor acestorvariabile în tot programul.

4.5.3.2. Atribuiri asupra parametrilor formali variabilă

, • . ■ tr.i ■ ■ -. :-jft<a

101




Valorile dobîndite în program de parametrii formali variabilă devin cu-noscute în locul de chemare ca valori a le variabilelor globale folosite dreptparametri actuali în apel.

Execuţia unei funcţii cu parametri formali variabilă produce deci şiefectul secundar de alterare a valorilor acestor variabile globale.

Folosirea va ri ab il el or globale ca parametri actuali corespunzătoriparametrilor formali variabilă este deci descurajată în cazu l funcţiilor.Comunicarea standard a funcţiilor cu mediul de chemare constă deci în :transmiterea de valori spre funcţie prin parametri v alo ar e şi întoarcerea unui(s in gur) rezultat din funcţie prin numele ei.

Folosirea variabilelor globale c a mijloc suplimentar de comunicare estepermisă. Variabilele globale pot fi deci folosite în funcţii, dar se recomandă cavalorile lor să nu fi e schimbate de acestea.

Observaţii:

1. Spre deosebire de funcţie, o procedură poate să întoarcă mai mult decît ovaloare în mediul de chemare. Procedura nu conţine vreo atribuire asupra numelui ei, decinici o valoare nu este întoarsă din procedură prin acest nume. Mijlocul standard de

întoarcere de valori din procedură este prin parametri formali variabilă: valorile dobîndite deaceştia în procedură devin cunoscute în afara ei ca valori ale parametrilor actualicorespunzători.

2. Atribuirile în procedură asupra variabilelor globale produc efecte secundaresimilare celor discutate pentru astfel de atribuiri la funcţii. Ele nu sînt recomandate nici înacest caz. Astfel de atribuiri introduc abateri de la procedeul standard de comunicaredinspre procedură prin care variabilele participante sînt desemnate explicit ca parametriformali variabilă (în declaraţie) şi parametri actuali (în apel). Efectele lor se propagă ladistanţă (în domenii de vizibilitate a le variabilelor globale) şi pot interfera cu cele similareproduse la execuţia altor proceduri din acelaşi program, făcînd riscantă utilizarea acestorvariabile.

4.53.3. Parametri actuali cu acelaşi nume pentru parametri formali variabilă distincţi

Folosirea de parametri actuali cu acelaşi nume nu este recomandată dacă eicorespund la parametri formali variabilă. Se evită astfel o sursă de efecte secundare subtile.

Parametrii actuali cu acelaşi nume ar desemna cîte o singură variabilă, care laexecuţia apelului ar fi cunoscută sub mai multe nume (ale parametrilor formalicorespunzători celor actuali cu acelaşi nume). O atribuire asupra unuia din aceşti parametriformali ar avea ca efect secundar şi alterarea valorilor celorlalţi.

Exemplu. Programul următor ilustrează efectele secundare produse de folosireade parametri actuali cu acelaşi nume pentru parametri formali variabilă.

program P ; var a : real;

procedure p l 2 (var x , y : rea l ) ; begin

x : = 1 ; y 2 and;f p l 2 l procedure p21 (var x, y : rea l ) ; begin

y := 2 ; X := 1end;{p21}

begin

pl2( a , a ) ; w r i t e ln ('a- ', a ) ; p21(a , a ); writeln ('a =

' , a ) end. {P}

■

r. ;

102



4.2. Funcţii

Procedurile pl2 şip21 diferă doar prin simpl a permutare ainstrucţiunilor de atribuire x : = l şi y : - 2. După apelul lui pl2 se scrie a - 2.După apelul lui p?l se scrie a = l.

în si tuaţ ii normale (chemări de fonna'pl2 ( a , b ) , p21 (a, b)această permutare nu ar f i produs vreun efect pentru că x şi y ar fi referitvariabile diferite (a, respectiv b).

Multe implementări, inclusiv cea pentru Pascal Oregon, nu semnaleazăastfel de defecte în programe nici la compilare, nici la execuţie.

Cele de mai sus sugerează că pentru o procedură cu antetul

procedura p(var x , v :

rea l ) nu este indicat un apel de forma

p(a [ i ] , a ! i I > unde a | i ] este o componentă de tablou. Chiar un

apel de forma

pta[e l l , a Ie2] )

unde el şi e2 sînt expresii, este susceptibil de a produce efecte secundare dacăel şi e2 conduc la aceeaşi valoare.

:; -l X: ■' ■ :.

. ■ •- . • • ■ :■ ■ .

4.5.4. Recursie 4.5.4.1.

Recursia indirectă

într-o structură de program reprezentată prin arborele

P

Q R .

? poate să apeleze pe Q, dar Q nu poate să apeleze pe k pentru că R nu este încă declarat. Limbajul prevede tot uşi o facilitate prin c ar e această referirede vi ne posibilă. Pentru aceasta:

1.R va fi preanunţată în P înaintea lui Q prin antetul său complet,urmat de direc ti va f or wa xd ("înainte").

2. în declaraţia propriu-zisă a lui R care urmează după Q, se foloseşteun antet redus în care se specifică doar numele lui K , tară parametri şi tipuri.

Programul p va avea, de exemplu, forma:

program P ;

procedure R(x : rea l ; vai y : i n teqer ) ; forward;

procedure Q(x: rea l ) ;

var a: i nt eger ; b eg in

¿(2.1, a); and; ÎQ?

procedure R; begin end; {R}

begin

I

103




end. {P$

Reprezentăm noua structură a programului prin arboreleP

/ I \ Rforward Q R

Desigur, referirea lui R în Q era posibilă şi fără folosirea directivei forward, prinsimpla inversare a ordinei declaraţiilor Iui Q şi R în P. Ar rezulta programul

P/ \ R

QDacă însă atît 0 apelează pe R cît şi R apelează pe 0, o astfel de inversare nu

rezolvă problema, fiind necesară folosirea directivei forward. Ea face deci posibil acest fel dereferire mutuală a două funcţii / proceduri care se numeşte recursie indirectă.

Cazul mai general de recursie indirectă al unui lanţ finit închis de n > 2 chemăride funcţii / proceduri se specifică similar.

4.5.4.2. Recursia directă

Discutăm acum cazul recursiei directe în care o funcţie / procedură se apeleazănemijlocit pe ea însăşi. Conceptual, un astfel de apel nu diferă de apelul între funcţii /proceduri distincte şi se implementează în translatoare, de regulă, prin mijloace similare.

Pentru programator recursia este încă o posibilitate, foarte elegantă, de exprimarea controlului asupra succesiunii prelucrărilor repetitive şi ea permite scrierea naturală aprogramelor care folosesc algoritmi şi structuri de date prin esenţă recursive. Ea este de

aceeaşi natură cu iteraţia care se exprimă cu ajutorul instrucţiunilor de control (în Pascal:while, repe at, for, vezi 3.2). în cazul iteraţiei repetiţia este exprimată şi controlată explicit folosind variabile sau

predicate desemnate special acestui scop. In cazul recursiei, repetiţia este implicită. Ea esteprovocată de execuţia unei funcţii / proceduri care conţine un apel al ei însăşi în partea sade instrucţiuni: cînd execuţia ajunge la acel apel, o nouă execuţie este declanşată ş.a.m.d..Desigur, o condiţie de oprire a acestui proces (potenţial infinit repetitiv) trebuieprevăzută şi programată.

Ilustrăm prin cîteva exemple simple mecanismul recursiei şi meritele relative alerecursiei şi iteraţiei. De fiecare dată presupunem definit tipul

type natural = 0..maxint;

Exemplul 1. Funcţia factorial

f 1 dacă n - of :N ----> N, f (n) = \

X n- f (n-1) dacă n >= 1

poate fi exprimată în Pascal, urmînd direct definiţia, în forma

function f (n : natural) : natural;begin

i f n = 0 then f : = 1else f 2= n * f(n-1)

end; {f}

Efectul unui apel de forma f (1 o) este declanşarea unui lanţ de apeluri alelui f pentru parametrii actuali 9 , 8 , 7 , 2 , l , 0 :

f'(10)

104



4.2. Funcţii

10 f (9 ) î i

î i2 f (1) î l1 f ( 0 ).. 1

■ • •

Apelul f (o) determină evaluarea directă a funcţiei oprind astfel procesul repetitiv;urmează revenirile din apeluri şi evaluarea lui f pentru l , 2 , 9 , 10 ,ultima valoare fiind întoarsă la locul primului apel f (l o). Se observă că apelul recursiv allui f este ultima acţiune care se execută la activarea funcţiei factorial. Acesta este un

exemplu de recursie la sfîrşit ("tail - end recursion") care, în general, poate f i uşor înlocuităprin iteraţie [Kru84] şi implementată eficient. Funcţia factorial poate fi rescrisă iterativfolosind două variabile auxiliare i şi p pentru controlul procesului repetitivi respectivpentru acumularea rezultatelor

intermediare:

function f(n:natural): natural; vari, p: natural; begin

pi- i;for i:« 2 to n do p:- p*i;

f:= p i ffl

Exemplul 2. Funcţia

fib: N --->,fib(n) 0 dacă n -

o1 dacă n - 1fib(n-i) + fib(n-2) dacă n >-2

are ca valori numerele lui Fibonacci. Forma ei Pascal derivată nemijlocit din definiţie nuilustrează cazul recursiei la sfîrşit:

function fib(n: natural): natural;begin

if n - 0 then fib:= 0

elae if n = 1 then fib:= 1elae fib:- fib(n-l) + fib(n-2)

end; {fib}Fiecare apel al funcţiei pentru n > - 2 generează două apeluri ş.a.m.d., de exemplu:

fib(4)/ \

fib(3) fib(2)/ \ / \

fib(2) fib(l) fib(l) fib(O)/ \ I I I

fib(l) fib(O) 1 1 oI I1 o

Introducînd variabile suplimentare, se poate obţine o variantă eficientă cu recursie

la sfîrşit (vezi exerciţiul 1). O formă nerecursivă care evită calculul repetat al valorilorfuncţiei pentru aceeaşi valoare a argumentului se obţine folosind trei variabile auxiliare i,a, b (pentru controlul iteraţiei, pentru valoarea curentă

end; {f}

105

a funcţiei şi pentru păstrarea unei valori precedente):. . . f . ■ . ■ . . ■ < ■ ■

function f ib(n:natural): natural;-var i,a,b: natural; begin

if n-0 then fib:= oelae if n-1 then fib:- 1else begin

a:= 0; b:= 1; fori:= 2 to n do bogin

b:= a+b;a:= b-a

and;fib:- b

ondond;

Exemplul 3. Funcţia lui Ackermann [Bro77] (exemplu celebru de funcţie recursivăcare nu este primitiv recursivă), redefinită de R. Peter m forma

n + l dacă m = oa(m-i, 1 ) dacă n - 0

L a(m-.l, a(m, n-l)) dacă m >0 şi n>0' ' ■ •

poate f i exprimată cu uşurinţă ca o funcţie Pascal recursivă:

function a(m,n: natural): natural;begin

if m - 0 then a:= n+1elae if n - 0 then a:= a(n-l, 1)elsa a:= a(m-l, a(m, n-D)

end; {a}

Funcţia ia valori foarte mari chiar pentru valori mici ale parametrilor, de exemplua (4,2) » i o20000. AmM programată, execuţia ei necesită timp de calcul mare (datoritănumărului mare de apeluri recursive) şi un spaţiu de memorie prohibitiv (datorită"adineimii" rscursiei), astfel că a devenit un test al calităţii implementării recursiei ,în>limbaje de programare [Wic82]; graful apelurilor ei pentru m =2, n=l este sugestiv înacest sens:

a:NxN ---> N, a(m,n) =

106

cartea de programare

Documents