פרק 7 סביבת הריצה

  • View
    58

  • Download
    0

Embed Size (px)

DESCRIPTION

7 . ( analysis ). lexical analyser. syntax analyser. semantic analyser. intermediate code generator. code optimizer. ( synthesis ). code generator. - PowerPoint PPT Presentation

Transcript

  • intermediate code generator

  • (Routines) (routine) , () () (routine)- (subroutine) (procedure) (function)

  • (header) , , . (body) ( ") (definition) (declaration) (call) " (caller) ( ) (callee)

  • 2 (formal parameters) , (actual parameters, arguments)

  • ( ) -Pascal program sort (input, output); var a : array [0..10] of integer;

    procedure readarray; var i : integer; begin for i := 1 to 9 do read ( a [ i ] ) end;

    function partition (y, z : integer) : integer; var i, j, x, v: integer; begin ... end; procedure quicksort (m, n: integer); var i : integer; begin if ( n > m ) then begin i := partition (m, n); quicksort (m,i-1); quicksort (i+1,n) end end;

    begin a[0] := -9999; a[10] := 9999; readarray; quicksort(1,9) end.

  • ,

    ,

  • (activation) (lifetime) , :

  • (Recursion) (non-recursive routine) (recursive routine) (self-recursion) (mutual-recursion) ' ' ' '

  • (Activation Tree) : ( ) ( ) ' ' ' ' ' ' ' '

  • (Control Stack) (DFT) : (control stack)

  • (Declaration) (declaration) (, , ) (name) (type) (static, auto, register) (const, volatile) (explicit declaration) (implicit declaration) -Fortran -I..N INTEGER REAL ( )

  • (Scope of Declaration) (scope of definition) (scope rules) (local) ( ) - (non-local) ( )

  • (Binding of Names) (environment) ( ) (state)

    (binding) " X s -X -s (X is bound to s)

  • ? ? -? ? ? ? ? ?

  • = heap stack

  • (Activation Record) (activation record) (frame) (" ) :

    -

    ( ) ""

  • ,

  • PROGRAM CNSUMECHARACTER 50 BUFINTEGER NEXTCHARACTER C, PRDUCEDATA NEXT /1/, BUF / /6 C = PRDUCE( ) BUF ( NEXT : NEXT ) = C NEXT = NEXT + 1 IF ( C .NE. ) GOTO 6 WRITE ( , (A) ) BUF END

    CHARACTER FUNCTION PRDUCE( )CHARACTER 80 BUFFERINTEGER NEXTSAVE BUFFER, NEXTDATA NEXT /81/ IF ( NEXT .GT. 80 ) THEN READ (, (A) ) BUFFER NEXT = 1 END IF PRODUCE = BUFFER ( NEXT : NEXT ) NEXT = NEXT + 1 END

  • , , -sp VAX: Frame Pointer, Argument Pointer8086: Base Pointer : + (base-displacement), ( )

  • , : , + " " "

  • (Calling end Return Sequence) " (calling sequence) " (return sequence)

    :

  • . . .

    . ( ) . . .

  • . . . .

    . ( ). , .

  • C, " ( " ) , ( printf), ( ) ( ) " "

  • :int func ( int n, char a[n] ){char b[n];...} " , - ""

  • (Dangling References) :main(){int p;p = dangle( );}

    int dangle( ){int i = 23;return &i;} : i static int i = 23; : i return new int(23);

  • : (process) (task) (thread)

  • r

  • (fragmentation) , (lisp, java) (garbage collection) , usedfreeusedfreeusedfreeused

  • - - (lexical scope) (static scope) C, Pascal, Ada, Perl (dynamic scope) Lisp, APL, Snobol, Perl

  • (Block) (block) " C { }Pascal begin end

  • B B

    x B, x -B x 'B B :. x 'B.'B x B

  • main( ){int a = 0 ;int b = 0 ;{int b = 1 ;{int a = 2 ;printf (%d %d\n, a, b);}{int b = 3 ;printf (%d %d\n, a, b);}printf (%d %d\n, a, b);}printf (%d %d\n, a, b);}

  • : ( ) / ( )

  • C , (1) int a[11];(2) readarray( ){ a }(3) int partition(int y,int z) { a }(4) quicksort(int m,int n) { }(5) main( ){ a } - () ,

  • Pascal program sort(input, output); vara : array [0..10] of integer; x : integer; procedure readarray; var i : integer; begin . . . a . . . end { readarray } ;procedure exchange(i, j : integer); begin x := a[i]; a[i] := a[j]; a[j] := x end { exchange };procedure quicksort(m, n: integer); var k, v : integer; function partition(y, z: integer):integer; var i, j :integer; begin . . . a . . . . . . v . . . . . . exchange(i, j); . . . end { partition } ; begin . . . end { quicksort }; begin . . . end { sort } .

  • (Nesting Depth) 1 p, q, q

    sort1readarray2exchange2quicksort2partition3

  • (Access Link) n n-1 n-1 (),

  • / / p - a np ( p) -na ( a)

  • 2 np na , -a () a " a (-) " (np na, offset) ( )

  • p np q nqnp < nq " q p, np +1 = nq q pnp nq" , 1,2 nq-1 p -q q nq-1 " np-nq+1 pnp-nq+1

  • program param(input, output); procedure b(function h(n:integer): integer); begin writeln(h(2)) end { b }; procedure c; var : integer; function f(n : integer) : integer; begin f := + n end { f }; begin := 0; b(f) end { c }; begin c end.c b f

  • (Display) d d[i] ( ) i

  • i: d[i] d[i] i: d[i] "

  • (Dynamic Scope)#!/usr/local/bin/perl$s = 10;$d = 20;

    sub show {print $s $d ;}

    sub small {my$s = 11;local $d = 21;&show;}

    &show; &small;print \n;&show; &small;print \n;output: 1020 1021 1020 1021

  • (deep access) " ( ) , (shallow access) p n, -n

  • " (call by value) " (call by reference) " (call by name)

  • " (Call By Value)int min (int a, int b) { return a < b ? a : b ;}int x = 10, y = 20;min (x, y) 10min (y, 30) 20min (30, 10) 10 (r-value)

  • " void swap(int a, int b){ int t; t = a; a = b; b = t;}

    int x = 10, y = 20;swap (x, y); a -b x -y

  • " (copy-in copy-out) (copy-restore) (value-result)swap(x, y) push ypush x " call swappop xpop y " Fortran:

  • " (Call By Pointer) Cvoid swap( int a, int b) { int t; t = a; a = b; b = t;}int x = 10, y = 20 ;swap(&x,&y); ( ) x -y

  • " (Call By Reference) -Fortran, Pascal; C++void swap( int &a, int &b){ int t; t = a; a = b; b = t;}int x = 10, y = 20 ;swap(x,y);

    " " x -y

  • - program copyout(input,output); var a : integer; procedure unsafe(var x : integer); begin x := 2; a:= 0 end; begin a := 1; unsafe(a); writeln(a) end. - 2 0

  • " (Call By Name) , - Algol swap(i, a[i] ) : t = i; i = a[i]; a[i] = t; t ( i) a[a[i]] a[i] ( i )

  • " swap "

    " " thunk l-value / r-value

  • Inline inline "

    inline void swap(int &a, int &b){ int t; t = a; a = b; b = t;} " t1 = a ;t2 = b ;t = t1 ;t1 = t2 ;t2 = t ;b = t2 ;a = t1 ;

  • (Symbol Table) ( int int double) " "

  • (" ) () : ( )

  • -L (L = 6, L = 8, . . . ) L (L = 31, . . . ) (L < 256, L < 1024, . . .)

  • , , , O(n) ( ) O(n) n e O(n(n+e)) n < 100 ( ) n > 1000 ( " )

  • (Hash Table) , n -e O(n(n+e)/m) m ( -) cpmatchlastactionws n

  • , (debugger) "" lookup insert delete ( ) ( )

  • 2 : ( ") ( ) ( )

  • 7