Curs 13: Agenda - profs.info.uaic.rodlucanu/cursuri/ap/resurse/curs13.pdf · Dorel Lucanu...
Transcript of Curs 13: Agenda - profs.info.uaic.rodlucanu/cursuri/ap/resurse/curs13.pdf · Dorel Lucanu...
Dorel Lucanu Algoritmica si programare
Curs 13: Agenda
continurea exemplului Convoiun exemplu de testanaliza statica a programeloristoric
Dorel Lucanu Algoritmica si programare
Q#1
a)există erori de sintaxa în definiţia funcţiei add()b)funcţia add() nu poate fi utilizată în expresiic)utilizarea funcţiei add() poate produce pierderi de memoried)funcţia add() este definită corect şi poate fi utilizată sigur totdeauna
typedef int vec[2];vec* add(const vec v1,
const vec v2) {
vec *v =(vec*)calloc(1,sizeof(vec));
(*v)[0] = v1[0] + v2[0];(*v)[1] = v1[1] + v2[1];return v;
}
• exemplupv = add(*add(v1, v2), v3);spatiul de memorie alocat de add(v1, v2)nu mai este accesibil
Dorel Lucanu Algoritmica si programare
Q#2
a) este corect şi la execuţie va afişa Test 2
b) va da erori la compilare
c) va da erori la editarea de legături
d) este corect sintactic dar la executie va avea o comportare nedeterminată
#include<stdio.h>#include<stdlib.h>char *myStrcpy(char *s1,
const char *s2) {
char *p=s1;while(*p++ = *s2++) ;return s1;
}int main(void) {
char *p = "Test 2", *q;myStrcpy(q, p);printf("%s\n", q);return 0;
}Nu este alocat spatiu de memorie pentru sirul destinatie din functia de copiere, spatiu ce ar fi trebuit sa fie referit q a
Dorel Lucanu Algoritmica si programare
Q#3
a)1370b)1368c)348160d)nimic deoarece
conţine erori de sintaxă
#include<stdio.h>#include<stdlib.h>int main(void) {
unsigned a = 0xAA;unsigned b = a << 3 | 010;printf("%d\n", b);return 0;
}
0xAA = ...00010101010 = 170a << 3 = ...10101010000 = 170*8 = 1360010 = 1000 = 8b = ...10101011000 = 1368
Dorel Lucanu Algoritmica si programare
Q#4
a)este corect şi la execuţie va afişa 2, 4
b)este corect şi la execuţie va afişa 3, 6
c) conţine erori de sintaxa la declararea structurilor de date
d)conţine erori de sintaxă în funcţia main()
#include<stdio.h>#include<stdlib.h>struct Cplx {
int x,y;};typedef struct Cplx Vct[3];int main(void) {
Vct v = {1, 2, 3, 4, 5, 6};printf("%d, %d\n", v[1].x, v[2].y);return 0;
}
v[0].x = 1, v[0].y = 2, v[1].x = 3, v[0].y = 4, v[2].x = 5, v[2].y = 6
Dorel Lucanu Algoritmica si programare
Q#5
a) este corect şi la execuţie va afişa 2 3
b) este corect şi la execuţie va afişa 4 1
c) conţine erori de sintaxa in functia sel()
d) conţine erori de sintaxă în funcţia main()
#include<stdio.h>#define swap(t,a,b){t temp = a; a = b; b =
temp;}int cresc(int x, int y){return x < y;}int a[] = {2,4,1,3};int N = sizeof(a)/sizeof(int);void sel(int comp(int, int)){int i, j, min;for(i=0; i<N-1; ++i){min = i;for(j = i+1; j<N; j++)
if(comp(a[j], a[min])) min = j;swap(int,a[min], a[i]);
}}int main(void) {
sel(cresc);printf("%d %d\n", a[1], a[2]);return 0;
}
-declaratia variabilei temp este OK deoareceswap defineste un bloc- functia sel() ordoneaza crescator tabloul global a relativ la relatia de ordine data de comp()- main() apeleaza sel() cu relatia uzuala peste nr naturale
Dorel Lucanu Algoritmica si programare
Q#6
a)este corect şi la execuţie va afişa a b c d
b)este corect şi la execuţie va afişa b c d e
c) conţine erori de sintaxă
d)este corect şi la execuţie va afişa a b c d e
#include<stdio.h>typedef enum {a = 'a', b = 'b',
c = 'c'} abc;int main(void) {
abc i;for(i = a + 1; i <= c + 3; ++i)
printf("%c ", i-1);return 0;
}
• tipul abc este compatibil cu char•i = a+1 =‘a’+1 = ‘b’•c+3 = ‘c’ + 3 = ‘f’• i-1 va lua pe rand valorile ‘a’, ‘b, ‘c’, ‘d’, ‘e’
Dorel Lucanu Algoritmica si programare
Q#7
a) este corectşi la execuţie va afişa
97 98 9 97b) este corect
şi la execuţie va afişa
97 98 9 9c) conţine erori
la declararea tipurilor si variabilelor
d) este corectşi la execuţie va afişa 9 98 9 9
#include<stdio.h>typedef struct {int a; int b;} ab;typedef enum {unu = 1, doi = 3, trei = 5}
e135;typedef union{
ab x;e135 y;int z;
} xyz;int main(void) {
ab i = {97,98};e135 j = doi*doi;xyz u;u.x=i;u.y = j;printf("%d %d %d %d ",u.x.a, u.x.b, u.y, u.z);return 0;
}
• i = (97, 98)• j = 9• u.x = i => u = u.x
= (97, 98)• u.y = j => u = ( 9, 98) • u.x.a = 9, u.x.b = 98,
u.y = 9, u.z = 9
u
u.x
u.x.b
u.y
u.x.a
u.z
Dorel Lucanu Algoritmica si programare
Q#8
a)mkigecb) kigecc)ljhfdb
d)mjgd
#include <stdio.h>int main(void) {
int c;FILE *ifp;ifp = fopen("finput.txt", "r+"); fseek(ifp, 0, SEEK_END); fseek(ifp, -1, SEEK_CUR); while (ftell(ifp) > 0) {
c = getc(ifp); putchar(c);fseek(ifp, -3, SEEK_CUR);
}fclose(ifp);return 0;
}
• fisierul este deschis pentru actualizare• primul apel fseek() pozitioneaza pointerul de fisier la sfarsitul fisierului (dupa ult. car.)•al doilea apel fseek() pozitioneaza pointerul pe ultimulcaracter, adica ‘m’•in while:
•getc deplaseaza pointerul cu 1 poz la dreapta•fseek() deplaseaza pointerul cu 3 poz la stanga•deci se vor sari 2 caractere
Daca fisierul finput.txt are continutul “abcdefghijklm”, care este rezultatul executiei programului?
Dorel Lucanu Algoritmica si programare
Q#9-10
Se consideră următoarele declaraţii pentru coadă:typedef struct NodCoada {
Elt *elt;struct NodCoada *leg;
} NodCoada;typedef struct Coada{
NodCoada *prim, *ultim;} Coada;a) Să se scrie o funcţie revCopy(Coada c1, Coada *c2)
care copie în mod eficient elementele din c1 în c2 în ordine inversă.
b) Să se scrie o secvenţă de program care creează coada a = (2, 5, 7, 8) şi apoi coada b = (8, 7, 5, 2). Se vor utiliza numai operaţiile tipului Coada şi revCopy.
Dorel Lucanu Algoritmica si programare
Q#9-10
int revCopy(Coada c1, Coada *c2){NodCoada *p, *q, *sq;if (c1.prim == NULL){ c2->prim = c2->ultim = NULL; return 0;}
p = c1.prim; sq = c2->ultim = NULL; while (p != NULL) {q = (NodCoada *)malloc(sizeof(NodCoada);if (q == NULL) return 1;q->elt = (Elt *)malloc(sizeof(Elt));if (q->elt == NULL) return 1;*(q->elt) = *(p->elt); // copyElt(q->elt, p->elt);q->leg = sq;sq = q;if (c2->ultim == NULL) c2->ultim = q;
}c2->prim = q;return 0;
}
Dorel Lucanu Algoritmica si programare
Q#9-10
int doi = 2, cinci = 5, sapte = 7, opt = 8;coadaVida(&a);insereaza(&a, &doi);insereaza(&a, &cinci);insereaza(&a, &sapte);insereaza(&a, &opt);revCopy(a, &b);
Dorel Lucanu Algoritmica si programare
Analiza statica a programelor
analizatoarele clasice sunt simple si eficientedar descoper numai anomalii simple (de ex. variabile neinitializate)limitarea vine din lipsa de informatie privindintentia programatoruluila cealalta extrema, verificatoarele suntutilizate pentru a verifica daca un program implementeaza corect o specificatie; acesteasunt foarte complicate si greu de utilizat pentruprograme marila mijloc se gasesc
instrumente de analiza statica“model checker”eInterpretare abstracta
Dorel Lucanu Algoritmica si programare
Splint
este un instrument de analiza staticaeste versiunea actuala a LCLint-ului (care extinde lint)face parte dintr-un proiect mai larg: LARCHmoduri de utilizare
adnotand fisierele sursa cu informatii privindintentia de utlizarescriind speificatiile in fisiere separate utilizand LCL (Larch interface Language for C)
poate fi downloadat de la adreselehttp://lclint.cs.virginia.edu/http://www.splint.org/
Dorel Lucanu Algoritmica si programare
Splint
Probleme detectate de Splint:derefentierea pointerilor NULLutilizarea de memorie nedefinitanepotrivirea tipurilorviolarea principiului ascunderii informatieiutilizarea periculoasa de alias-urimodificarea variabilelor globale cu valoriinconsistente cu specificatiile din interfataprobleme de control a fluxului de calcul(cicluri infinite)depasirea dimensiunii bufferuluiimplementari de macrouri periculoaseviolari ale conventiilor de notarepersonalizate
Dorel Lucanu Algoritmica si programare
Ex: derefentierea pointerilor NULL
vreo problema cu urmatorul cod?char firstChar1 (char *s){
return *s;}
codul adnotat pentru SPLINTchar firstChar1 (/*@null@*/ char *s){
return *s;} specifica faptul ca
parametrul poate fi siNULL
Dorel Lucanu Algoritmica si programare
Ex: deferentierea pointerilor NULL
rezultatul analizarii codului cu SPLINT
D:\users\dlucanu\cursuri\ap\ex\splint>splint frstChar1.cSplint 3.1.1 --- 02 May 2003
frstChar1.c: (in function firstChar1)frstChar1.c:3:11: Dereference of possibly null pointer s: *s
Dorel Lucanu Algoritmica si programare
Ex: deferentierea pointerilor NULL
O posibila remedierechar firstChar2 (/*@null@*/ char *s){
if (s == NULL) return '\0';return *s;
}
rezultatul analizarii codului cu SPLINT
D:\users\dlucanu\cursuri\ap\ex\splint>splint frstChar2.cSplint 3.1.1 --- 02 May 2003
Finished checking --- no warnings
Dorel Lucanu Algoritmica si programare
Ex: deferentierea pointerilor NULL
putem specifica ca totdeauna parametrul estenenul
char firstChar1 (/*@notnull@*/ char *s){
return *s;}
rezultatul analizarii codului cu SPLINT
D:\users\dlucanu\cursuri\ap\ex\splint>splint frstChar1.cSplint 3.1.1 --- 02 May 2003
Finished checking --- no warnings
Dorel Lucanu Algoritmica si programare
Ex: deferentierea pointerilor NULL
… dar atentie la apelarechar firstChar1 (/*@notnull@*/ char *s){
return *s;}
int main(void){
char *w = NULL, x;x = firstChar1(w);return 0;
}
Dorel Lucanu Algoritmica si programare
Ex: deferentierea pointerilor NULL
rezultatul analizarii codului cu SPLINT
D:\users\dlucanu\cursuri\ap\ex\splint>splint apelFrstChar1.cSplint 3.1.1 --- 02 May 2003
apelFrstChar1.c: (in function main)apelFrstChar1.c:9:18: Null storage w passed as non-null
param: firstChar1 (w)apelFrstChar1.c:8:13: Storage w becomes nullapelFrstChar1.c:1:6: Function exported but not used
outside apelFrstChar1:firstChar1
a doua avertizare poate fi eliminata declarandfirstChar1 ca fiind statica
Dorel Lucanu Algoritmica si programare
Ex: Parametri nedefiniti
extern void setVal (int *x);extern int getVal (int *x);extern int mysteryVal (int *x);
int dumbfunc (int *x, int i){
if (i > 3)return *x;
else if (i > 1)return getVal (x);
else if (i == 0)return mysteryVal (x);
else{
setVal (x);return *x;
}}
Dorel Lucanu Algoritmica si programare
Ex: Parametri nedefiniti
nu stim rolul parametrilor functiilor declarateexterndin acest motiv nu putem sa analizam dacaapelul functiilor este corect semanticSPLINT permite precizarea roulului fiecaruiparametru
Dorel Lucanu Algoritmica si programare
Ex: Parametri nedefiniti
extern void setVal (/*@out@*/ int *x);extern int getVal (/*@in@*/ int *x);extern int mysteryVal (int *x);
int dumbfunc (/*@out@*/ int *x, int i){
if (i > 3)return *x;
else if (i > 1)return getVal (x);
else if (i == 0)return mysteryVal (x);
else{
setVal (x);return *x;
}}
Dorel Lucanu Algoritmica si programare
Ex: Parametri nedefiniti
D:\users\dlucanu\cursuri\ap\ex\splint>splint paramNedef.cSplint 3.1.1 --- 02 May 2003
paramNedef.c: (in function dumbfunc)paramNedef.c:10:13: Value *x used before definition
paramNedef.c:12:21: Passed storage x not completely defined (*x is undefined): getVal (x)
paramNedef.c:14:25: Passed storage x not completely defined (*x is undefined): mysteryVal (x)
Finished checking --- 3 code warnings
Dorel Lucanu Algoritmica si programare
Ex: verificarea tipurilor (bool)
bool.h#ifndef BOOL_H#define BOOL_H#ifndef FALSE#define FALSE 0#endif#ifndef TRUE#define TRUE (!FALSE)#endif/* bool is a keyword in C++ *//*@-cppnames@*/typedef int bool;...
Dorel Lucanu Algoritmica si programare
Ex: verificarea tipurilor (bool)
# include "bool.h"
int f (int i, char *s,bool b1, bool b2)
{if (i = 3)
return b1;if (!i || s)
return i;if (s)
return 7;if (b1 == b2)
return 3;return 2;
}
Dorel Lucanu Algoritmica si programare
Ex: verificarea tipurilor (bool)
D:\users\dlucanu\cursuri\ap\ex\splint>splint bool.cSplint 3.1.1 --- 02 May 2003
bool.h:14:13: Datatype bool declared with inconsistent type: intload file standard.lcd: Specification of bool: booleanbool.c: (in function f)bool.c:6:7: Test expression for if is assignment expression: i = 3bool.c:6:7: Test expression for if not boolean, type int: i = 3bool.c:7:12: Return value type bool does not match declared
type int: b1. Types are incompatible.bool.c:8:8: Operand of ! is non-boolean (int): !ibool.c:8:13: Right operand of || is non-boolean (char *): !i || sbool.c:12:7: Use of == with boolean variables (risks inconsistency
because of multiple true values): b1 == b2The file bool.h (included in splint/lib) provides bool_equalfor safe bool comparisons. Finished checking --- 7 code warnings
Dorel Lucanu Algoritmica si programare
Istoric: C
Parinti:BCPL (Basic Combined Programming Language ) , Martin Richards, la mijloculanilor 1960 in timpul vizitei la MITB, Ken Thompson, 1969
Proiectarea limbajului C: 1969-1973 1972 cel mai semnificativIn paralel cu dezvoltarea sistemului UNIX
1973-1980S-au adaugat tipurile: unsigned, long, union, enumStructurile au devenit “first-class objects”
Dorel Lucanu Algoritmica si programare
Istoric: C
1977,1979 – s-a demonstrat portabilitateasistemului UNIX1978: B. W. Kernighan and D. M. Ritchie, The C Programming LanguageANSI C: 1989
Sintaxa pentru signatura functiilor a fostimprumutata din C++Alte imbunatatiri dar care au pastratcaracterul limbajului
ANSI-ISO standard: 1999
Dorel Lucanu Algoritmica si programare
Istoric: C
Succesori: Concurrent C, Objective C, C*, C++, C#Critici:
Confuzia intre pointeri si tablouriNetipizatAtribuire intre intregi si pointeri
Operatorul de indirectareint *fp(); int (*pf)();int *(*pfp)();
Ostilitate fata de “garbage collection”automata
Dorel Lucanu Algoritmica si programare
Istoric: C
De unde vine succesul?Succesul sistemului Unix (si apoi Linux)Simplu si relativ micPortabilitateIn acelasi timp “low-level” si “high-level”(independent de masina)stabil
Dorel Lucanu Algoritmica si programare
ACM/A.M. Turing Award 1983: Dennis M. Ritchie
CitationFor their development of generic operating systems theory and specifically for the implementation of the UNIX operating system.
Dorel Lucanu Algoritmica si programare
Brian Kernighan
Bell Labs