طراحی و پیاده سازی زبانها

طراحی و پیاده سازی زبانها

اسلاید 1: Narges S. Bathaeianطراحي و پیاده سازی زبانهاکنترل زیربرنامه

اسلاید 2: Narges S. Bathaeianشكل كلي حافظه بعد از load برنامه ...Code segmentData segmentحافظه تخصيص داده شده به يك برنامهكد تابع main……كد تابع 1........كد تابع 2........متغيرهاي global……پارامترهاي تابع xآدرس برگشتمتغيرهاي محلي تابع xمتغيرهاي موقت تابع x........

اسلاید 3: Narges S. BathaeianActivation recordمتغيرهاي global……پارامترهاي تابع xآدرس برگشتمتغيرهاي محلي تابع xمتغيرهاي موقت تابع x........پارامترهاي تابع yآدرس برگشتمتغيرهاي محلي تابع yمتغيرهاي موقت تابع y……..Activation record تابع xActivation record تابع y

اسلاید 4: 4activation recordRemember that data storage for subprograms is in an activation record.var X: integer;X is of type integer.L-value of X is some specific offset in an activation record.Goal is to look at locating activation record for P.Given an expression: X = Y + Z1. Locate activation record containing Y.2. Get L-value of Y from fixed location in activation record.3. Repeat process for Z and then X.

اسلاید 5: Narges S. Bathaeianانواع محيطهاي اجراكاملا ايستا (fully static): simple call-returnFORTRAN77مبتني بر پشته (stack based)C, PASCALكاملا پويا (fully dynamic)LISP

اسلاید 6: Narges S. BathaeianFully staticقبل از اجراي برنامه, يك Activation record براي هر تابع , در نظر گرفته مي شود.همه متغيرها (global, local) از يك آدرس ثابت قابل دستيابي هستند.پارامترهاي توابع تنها اشاره گر به مكانهايي از تابع صدا زننده هستند. توابع بازگشتي نمي توانيم داشته باشيم.پوينتر نمي توانيم داشته باشيم.

اسلاید 7: Narges S. Bathaeianشكل كلي حافظه در محيط كاملا ايستا(الگوی اول)

اسلاید 8: Narges S. Bathaeianشكل كلي حافظه در محيط كاملا ايستا(الگوی دوم)

اسلاید 9: Narges S. Bathaeianمثال از يك برنامه FORTRAN PROGRAM TESTCOMMON MAXSIZEINTEGER MAXSIZEREAL TABLE(10), TEMPMAXSIZE = 10READ *, TABLE(1), TABLE(2), TABLE(3)CALL QUADMEAN(TABLE,3,TEMP)PRINT *, TEMPENDSUBROUTIN QUADMEAN(A, SIZE, QMEAN)COMMON MAXSIZEINTEGER MAXSIZE, SIZEREAL A(SIZE), QMEAN, TEMPINTEGER KTEMP = 0.0IF(( SIZE.GT.MAXSIZE).OR.(SIZE.LT.1)) GOTO 99 DO 10 K=1, SIZETEMP = TEMP+ A(K) * A(K)10 CONTINUE99 QMEAN = SQRT(TEMP/SIZE)RETURNEND

اسلاید 10: Narges S. Bathaeianمثال از يك برنامه FORTRAN PROGRAM TESTCOMMON MAXSIZEINTEGER MAXSIZEREAL TABLE(10), TEMPMAXSIZE = 10READ *, TABLE(1), TABLE(2), TABLE(3)CALL QUADMEAN(TABLE,3,TEMP)PRINT *, TEMPENDSUBROUTIN QUADMEAN(A, SIZE, QMEAN)COMMON MAXSIZEINTEGER MAXSIZE, SIZEREAL A(SIZE), QMEAN, TEMPINTEGER KTEMP = 0.0IF(( SIZE.GT.MAXSIZE).OR.(SIZE.LT.1)) GOTO 99 DO 10 K=1, SIZETEMP = TEMP+ A(K) * A(K)10 CONTINUE99 QMEAN = SQRT(TEMP/SIZE)RETURNENDMAXSIZETABLE(1)…TABLE(10)TEMP3ASIZEQMEANRETURN ADDRESSTEMPKAct. rec تابع TESTAct. rec تابع QUADMEANReturn addr. (IP = PC)

اسلاید 11: Narges S. BathaeianStack basedبا فراخواني تابع activation record مربوط به آن در stack , push مي شود و هنگام بازگشت به تابع صدازننده, از stack , pop مي شود.دو نوعStatic scopeبدون local procedure : مانند زبان Cبا local procedure : مانند زبان PascalDynamic Scope...Code segmentStackHeap

اسلاید 12: PZ09A Programming Language design and Implementation -4th EditionCopyright©Prentice Hall, 2000Activation record structure

اسلاید 13: Narges S. Bathaeianمثال از يك برنامه C #include <stdio.h>int x , y ;int gcd ( int u , int v ){if (v==0) return u;else return gcd(v , u % v);}main(){scanf(“%d%d”, &x , &y );printf(“%dn”,gcd(x,y));return 0;} x: 15 y: 10 Act. rec تابع mainu : 15v : 10EPIPu : 10v : 5EPIPu : 5v : 0EPIPCEPspControl link = EP: Environment Pointer

اسلاید 14: Narges S. BathaeianتوضيحاتCEP (Current Environment Pointer) = FP (frame pointer): رجيستري كه در آن آدرس activation record جاري در آن است.sp : stack pointer: رجيستري كه در آن آدرس سر stack در آن است.EP: آدرس activation record قبلي را دارد.آدرس متغيرهاي push شده مي تواند با توجه به CEPو اندازه بايت لازم تعيين شوند.متغيرهاي محلي تابع و موقت بعد از return address در تابع push مي شوند.CEP ها تشکیل یک زنجیره بنام DCP (Dynamic chain pointer) می دهند.

اسلاید 15: Narges S. Bathaeianهنگام فراخواني يك تابع (prologue):آرگومانها محاسبه شده و در stack , push مي شوند.مقدار CEP در stack , push مي شود.(EP)مقدار جديد CEP برابر sp جاري مي شود.آدرس بازگشت (PC) در stack , push مي شود. (IP)يك jump به ابتداي كد تابع فراخواني شده انجام مي شود.

اسلاید 16: Narges S. Bathaeianهنگام بازگشت از يك تابع (Epilogue):مقدار CEP در sp ريخته مي شود.مقدار EP به داخل CEPريخته مي شود.يك پرش با توجه به آدرس موجود در return address به كد انجام مي شود.آرگومانها از stack , pop مي شوند تا مقدار sp تصحيح شود.

اسلاید 17: Narges S. Bathaeianمثال از يك برنامه C #include <stdio.h>int x , y ;int gcd ( int u , int v ){int t;if (v==0) return u;else { t= gcd(v , u % v); return t;}}main(){scanf(“%d%d”, &x , &y );printf(“%dn”,gcd(x,y));return 0;} x: 15 y: 10 Act. rec تابع mainCEP= XX00sp = XX04pc = X0X0

اسلاید 18: Narges S. Bathaeianمثال از يك برنامه C #include <stdio.h>int x , y ;int gcd ( int u , int v ){ int t;if (v==0) return u;else { t= gcd(v , u % v); return t;}}main(){scanf(“%d%d”, &x , &y );printf(“%dn”,gcd(x,y));return 0;} x: 15 y: 10 Act. rec تابع mainu : 15v : 10XX00X0X0t : CEP=XX0Bsp=XX11pc = X0XA

اسلاید 19: Narges S. Bathaeianمثال از يك برنامه C #include <stdio.h>int x , y ;int gcd ( int u , int v ){ int t;if (v==0) return u;else { t= gcd(v , u % v); return t;}}main(){scanf(“%d%d”, &x , &y );printf(“%dn”,gcd(x,y));return 0;} x: 15 y: 10 Act. rec تابع mainu : 15v : 10XX00X0X0t : CEP=XX0Bsp=XX0Fpc = X0XD

اسلاید 20: Narges S. Bathaeianمثال از يك برنامه C #include <stdio.h>int x , y ;int gcd ( int u , int v ){int t;if (v==0) return u;else { t= gcd(v , u % v); return t;}}main(){scanf(“%d%d”, &x , &y );printf(“%dn”,gcd(x,y));return 0;} x: 15 y: 10 Act. rec تابع mainu : 15v : 10XX00X0X0t : u : 10v : 5XX0B X0XDt : CEPsp

اسلاید 21: Narges S. Bathaeianمحاسبه offset متغيرها در زمان كامپايلآدرس EP در هر activation record مبنا در نظر گرفته مي شود.آدرس متغير هايي كه در بالاي EP هستند (پارامترهاي تابع) با مقدار مثبت و بقيه با مقدار منفي نمايش داده مي شوند.

اسلاید 22: Narges S. Bathaeianمثالv: +4u: +6t: -6فرض: Int : 2 byteFloat : 4 byteAddress : 4 byteChar : 1 byteDouble : 8 byte x: 15 y: 10 Act. rec تابع mainu : 15v : 10XX00X0X0t : u : 10v : 5XX0B X0XDt : CEP

اسلاید 23: Narges S. BathaeianProcedure هاي تودر تودر هر حوزه (scope) به اسامی تعریف شده در آن حوزه میتوان دسترسی داشت. پس:هر procedure به procedure هاي فرزند و برادر خود دسترسي دارد و مي تواند آنها را فراخواني كند.حوزه متغيرهاي تعريف شده در يك حوزه, آن حوزه و حوزه های فرزند آن حوزه است. پياده سازي:SCP (static chain pointer) یا Access link : آدرس Act. Rec پدر (دسترسي به procedure پدر)فراخواني شده از پدرفراخواني شده از برادر

اسلاید 24: Narges S. Bathaeianمثال 1 از يك برنامه Pascalprogram test; Var x,y:integer; Procedure p;…procedure q;begin…r;…end;procedure r;… begin… end;Begin…p;…End; x: 15 y: 10 Act. rec تابع maintestPqrاجازه دسترسيها در زمان كامپايل نگهداري مي شود.

اسلاید 25: Narges S. Bathaeianمثال 1 از يك برنامه Pascal program test;Var x,y:integer;Procedure p;…procedure q;begin…r;…end;procedure r;…begin…end;Begin…p;…End; x: 15 y: 10Act. rec تابع main …No SCPDCP…Act. Rec p

اسلاید 26: Narges S. Bathaeianمثال 1 از يك برنامه Pascal program test;Var x,y:integer;Procedure p;…procedure q;begin…r;…end;procedure r;…begin…q;…end;Begin…p;…End; x: 15 y: 10Act. rec تابع main …No SCPDCP……SCPDCP…Act. Rec pAct. Rec qفراخواني از طرف پدر:مقدار CEP در SCP قرار داده مي شود.

اسلاید 27: Narges S. Bathaeianمثال 1 از يك برنامه Pascal program test;Var x,y:integer;Procedure p;…procedure q;begin…r;…end;procedure r;…begin…q;…end;Begin…p;…End; x: 15 y: 10Act. rec تابع main …No SCPDCP……SCPDCP……SCPDCP…Act. Rec pAct. Rec qAct. Rec rفراخواني از طرف برادر:مقدار SCP برادر در SCP قرار داده مي شود.

اسلاید 28: Narges S. Bathaeianمثال 2 از يك برنامه Pascal program test;Var x,y:integer;Procedure p;…procedure q;procedure r;…begin…r;…end;begin…q;…end;Begin…p;…End; x: 15 y: 10Act. rec تابع main …No SCPDCP……SCPDCP……SCPDCP…Act. Rec pAct. Rec qAct. Rec rزنجيره SCP

اسلاید 29: DisplaysThe idea: Put the static links in a separate stack called a display. The entries in the display are pointers to the Act_recs that have the variables in the referencing environment. Represent references as (display_offset, local_offset)where display_offset is the same as chain_offsetNarges S. Bathaeian

اسلاید 30: DisplaysFor a call to procedure P with a static_depth of k: Save, in the new Act_rec, a copy of the display pointer at position k Put the link to the Act_rec for P at position k in the display Narges S. Bathaeian

اسلاید 31: Displays (Example)Narges S. Bathaeian program MAIN_3; procedure BIGSUB; procedure SUB1; end; { SUB1 } procedure SUB2; procedure SUB3; end; { SUB3 } end; { SUB2 } end; { BIGSUB } end. { MAIN_3 }

اسلاید 32: Displays (Example)Narges S. Bathaeianprogram MAIN_3; procedure BIGSUB; procedure SUB1; end; { SUB1 } procedure SUB2; procedure SUB3; end; { SUB3 } end; { SUB2 } end; { BIGSUB }end. { MAIN_3 }Case 1: SUB2 calls SUB1 Before the call, we have: A.R. for SUB2 A.R. for BIGSUB 21 A.R. for MAIN_30 Stack Display After the call, we have: A.R. for SUB1 A.R. for SUB2 A.R. for BIGSUB21 A.R. for MAIN_30 Stack Display

اسلاید 33: Displays (Example)Narges S. Bathaeianprogram MAIN_3; procedure BIGSUB; procedure SUB1; end; { SUB1 } procedure SUB2; procedure SUB3; end; { SUB3 } end; { SUB2 } end; { BIGSUB }end. { MAIN_3 }Case 2: SUB2 calls SUB3 Before the call, we have: AR. for SUB2 AR. for BIGSUB 21 AR. for MAIN_30 StackDisplay After the call, we have: AR. for SUB3 AR. for SUB2 3 AR. for BIGSUB 21 AR. for MAIN_30 StackDisplay

اسلاید 34: Displays (Example)Narges S. Bathaeianprogram MAIN_3; procedure BIGSUB; procedure SUB1; end; { SUB1 } procedure SUB2; procedure SUB3; end; { SUB3 } end; { SUB2 } end; { BIGSUB }end. { MAIN_3 }Case 3: SUB3 calls SUB1 Before the call, we have: AR. for SUB3 AR. for SUB23 AR. for BIGSUB 21 AR. for MAIN_30 StackDisplay After the call, we have: AR. for SUB1 AR. for SUB3 AR. for SUB23 AR. for BIGSUB 21 AR. for MAIN_30 StackDisplay

اسلاید 35: Dynamic scope rulerefers to most recent activation record (DCP)Not fully stack basedStack: function callsEamplesLisp…Narges S. Bathaeian

اسلاید 36: slide 36Static vs. Dynamic ScopeExamplevar x=1;function g(z) { return x+z; }function f(y) { var x = y+1; return g(y*x);}f(3);x1x4y3z12outer blockf(3)g(12)Which x is used for expression x+z ?static scopedynamic scope

اسلاید 37: Retention vs. DeletionRetention FortranStatic and global variables in CDeletionLocal variables in C, PascalNarges S. Bathaeian

اسلاید 38: 38Parameter passingParameter: A variable in a procedure that represents some other data from the procedure that invoked the given procedure.Parameter transmission: How that information is passed to the procedure.The parameter is also called the formal argument.The data from the invoking procedure is called the actual argument or sometimes just the argument.Usual syntax: Actual arguments: call P(A, B+2, 27+3)Parameters: Procedure P(X, Y, Z)What is connection between the parameters and the arguments?Call by nameCall by referenceCall by valueCall by result (or value-result)

اسلاید 39: 39Language dependentDifference languages have different mechanisms:ALGOL - name, valuePascal - value, referenceC - value (BUT pointers give us referenceConstant tension between desire for efficiency and semantic correctness in defining parameter transmission.

اسلاید 40: 40Call by nameSubstitute argument for parameter at each occurrence of parameter:Invocation: P(A, B+2, 27+3)Definition: procedure P(X,Y,Z) {int I; I=7; X = I + (7/Y)*Z;}Meaning: P(X,Y,Z) {int I; I=7; A=I+(7/(B+2))*(27+3);}This is a true macro expansion. Simple semantics, BUT:1. Implementation. How to do it?2. Aliases. What if statement of P were: I = A?3. Expressions versus statements: If we had D=P(1,2,3) and a return(42) in P, what does semantics mean?4. Error conditions: P(A+B, B+2, 27+3)

اسلاید 41: 41Implementation of call by nameA thunk is the code which computes the L-value and R-value of an argument.For each argument, pass code address that computes both L-values and R-values of arguments.P(A, B+2, 27+3) generates:jump to subroutine Paddress of thunk to return L-value(A)address of thunk to return R-value(A)address of thunk to return L-value(B+2)address of thunk to return R-value(B+2)address of thunk to return L-value(27+3)address of thunk to return R-value(27+3) To assign to X, call thunk 1, To access X, call thunk 2To assign to Y, call thunk 3, To access Y, call thunk 4To assign to Z, call thunk 5, To access Z, call thunk 6Issue: Assignment to (B+2): How?Call by name is conceptually convenient, but inefficient.

اسلاید 42: 42Examples of Call by Name1. P(x) {x = x + x;}Seems simple enough …Y = 2;P(Y); write(Y)  means Y = Y+Y write(Y)  prints 42. int A[10];for(I=0; I<10; I++) {A[I]=I;};I=1; P(A[I])  A[1] = A[1] + A[1]  A[1] set to 23. But: F {I = I + 1; return I;}What is: P(A[F])?P(A[F])  A[F] = A[F]+A[F]  A[I++] = A[I++]+A[I++]  A[2] = A[3]+A[4]4. Write a program to exchange values of X and Y: (swap(X,Y))Usual way: swap(x,y) {t=x; x=y; y=t;}Cannot do it with call by name. Cannot handle both of following: swap(I, A[I]) swap(A[I],I)One of these must fail.

اسلاید 43: 43Call by referencePass the L-value of the argument for the parameter.Invocation: P(A, B+2, 27+3)Implementation:Temp1 = B+2Temp2 = 27+3jump to subroutine PL-value of AL-value of Temp1L-value of Temp2This is the most common parameter transmission mechanism. In the procedure activation record, parameter X is a local variable whose R-value is the L-value of the argument.

اسلاید 44: 44Call by valuePass the R-value of the argument for the parameter.Invocation: P(A, B+2, 27+3)Implementation: Temp1 = B+2Temp2 = 27+3jump to subroutine PR-value of AR-value of Temp1R-value of Temp2In procedure activation record, parameter X is a local variable whose R-value is the R-value of the argument.

اسلاید 45: 45Call by reference in CC only has call by value,BUT pointer variables allow for simulating call by reference:P(i, j)  passes i and j by value.P(&i, &j)  passes L-values of i and j.P(*x, *y) {*x = *y + 1;}  arguments are addresses (pointers)

اسلاید 46: Call by result (or value-result)Call by value, AND pass back the final value to argument upon return.Parameter is a local value in procedure.Similar to call by reference, except for aliasing.Narges S. Bathaeian

اسلاید 47: Narges S. BathaeianPass by valuevoid inc2(int x){++x; ++x; }void inc2(int *x){++(*x); ++(*x); }مقدار يك پارامتر قبل از فراخواني تابع محاسبه شده و نتيجه فرستاده مي شود.تغيير پارامتر در تابع فراخواني شده, تاثيري در تابع فراخواني كننده ندارد. مگر اينكه اشاره گر به متغير فرستاده شده باشد.C , Pascal , ADAبي تاثير موثر

اسلاید 48: Narges S. BathaeianPass by referencevoid inc2(int &x){++x; ++x; }مقدار آدرس پارامتر فرستاده مي شود.عنوان پارامتر در تابع فراخواني شده, مجازي است.C++ : &Fortran77Pascal : varدر تابع فراخواني شده, آدرس پارامتر كه بطور نسبي فرستاده شده بايد با توجه به SCP دوباره محاسبه شود.

اسلاید 49: Narges S. BathaeianPass by value-resultvoid p(int x, int y){++x; ++y; }main(){ int a=1; p(a,a); printf(“%d”, a); return 0;}مقدار يك پارامتر قبل از فراخواني تابع محاسبه شده و نتيجه فرستاده مي شود. سپس مقدار پارامتر پس از تغيير در تابع فراخواني شده, دوباره در مكان اول خود كپي مي شود.ADA : in outپياده سازي؟ a=2

اسلاید 50: Narges S. BathaeianPass by nameint a[10];int i;void p(int x){++i; ++x; }main(){ i=a[1]=a[2]=1; p(a[i]); printf(“%d %d”, a[1],a[2]); return 0;}مقدار يك پارامتر قبل از فراخواني تابع محاسبه نشده و در تابع فراخواني شده محاسبه مي شود.هر پارامتر, خود يك procedure است. Algol60نتايج غير منتظرهپياده سازي مشكلLazy evaluating a[1]=1a[2]=2i=2;

اسلاید 51: Narges S. BathaeianBlock برخي زبانها مانند C بلوك بندي مي شوند. Scope متغيرهاي تعريف شده در يك بلوك, آن بلوك و بلوكهاي فرزند آن بلوك است....main(){int i,j;{int k=0;i=j=1;…}k=… //undefined variable k…}

اسلاید 52: Narges S. Bathaeianپياده سازي بلوكبا وارد شدن به يك بلوك متغيرها در stack, push مي شوند.با خارج شدن از يك بلوك متغيرها از stack, pop مي شوند.در محاسبه offset متغيرها در زمان كامپايل بايد دقت شود. بلوكهاي برادر از offset يكساني شروع مي شوند.

اسلاید 53: Narges S. BathaeianFully Dynamic در Modula2 مي توان يك procedure را به عنوان آرگومان برگشتي procedure ديگر داشت.كاملا در heap پياده سازي مي شود.مثال صوري:typedef int (*proc)(void);proc g(int x){int f(void) {return x; }return f;}main(){proc c;c = g(2);printf(“%d”,c());return 0;}

اسلاید 54: Narges S. Bathaeianتخصيص حافظهدر خواست تخصيص حافظه توسط برنامهmalloc , newپيدا كردن فضاي مناسب خالي در حافظهدر خواست آزادسازي حافظه توسط برنامهfreeآزادسازي حافظه و اضافه كردن آن به ليست فضاهاي خالي

اسلاید 55: Narges S. BathaeianDynamic environmentبراي مواقعي كه طول عمر يك متغير بيشتر از procedure مربوطه است.بخاطر pop شدن procedure با stack قابل پياده سازي نيست.مثال:int *dangle(void){int x;return &x;}آدرس x یک آرگومان برگشتي است. پس بايد در قسمتي جدا از stack تعريف شده باشد....Code segmentStackHeap