LW - Grammatica CF Prog::=Decs main() Stats. Decs::=Dec | Dec Decs. Dec::=VDec | FDec. VDec::=PDec | Type Id = Exp; PDec::=Type Id; FDec::= Type Id(PDecs)

  • Published on
    26-Mar-2015

  • View
    215

  • Download
    2

Transcript

  • Slide 1

LW - Grammatica CF Prog::=Decs main() Stats. Decs::=Dec | Dec Decs. Dec::=VDec | FDec. VDec::=PDec | Type Id = Exp; PDec::=Type Id; FDec::= Type Id(PDecs) {[with Decs do] Stats result Exp} | void Id(PDecs) {[with Decs do] Stats} PDecs::=PDec | PDec PDecs. Type::=int | bool. Stats::=Stat | Stat Stats. Stat::=Exp; | while (Exp) {Stats} | if (Exp) {Stats} else {Stats}| ?Id | !Exp. Exp::=Id | Id = Exp | Id(Exps) | Exp + Exp | Exps ::=Exp | Exp Exps. Slide 2 Funzioni di Semantica Statica [_] s Prog :L Prog (LW) P {*} [_] s Decs :L Decs (LW) Env s Env s P Env s [_] s Dec :L Dec (LW) Env s Env s P Env s [_] s Dec (d,, l ) = [_] s Decs (d,, l ) [_] s VDec :L VDec (LW) Env s Env s P Env s [_] s VDec (d,, l ) = [_] s Decs (d,, l ) [_] s PDecs :L PDecs (LW) Env s Env s P Env s [_] s PDecs (d,, l ) = [_] s Decs (d,, l ) [_] s PDec :L PDec (LW) Env s Env s P Env s [_] s PDec (d,, l ) = [_] s Decs (d,, l ) [_] s FDec :L FDec (LW) Env s Env s P Env s [_] s FDec (d,, l ) = [_] s Decs (d,, l ) [_] s Stats :L Stats (LW) Env s P {*} [_] s Stat :L Stat (LW) Env s P {*} [_] s Stat (st, ) = [_] s Stats (st, ) [_] s Exp :L Exp (LW) Env s P Types [_] s Exp (e, ) = [_] s Exps (e, ) [_] s Exps :L Exps (LW) Env s P Types + Env s = [L Id (LW) P Types] Fin, dove Types = BTypes (BTypes + RTypes), dove BTypes = {int, bool} e RTypes = BTypes {void} Notazione per funzioni parziali a dominio finito f [X P A] Fin se f [], Dom(f) = se f [a 1 /x 1,, a n /x n ] con tutte le x i distinte, Dom(f) = {x 1,,x n } e f(x i )=(a i ) se f g[a/x], Dom(f) = Dom(g) x} e f(x)= g(x) se x x, altrimenti f(x)=a se f g[h], Dom(f) = Dom(g) Dom(h) e f(x)= h(x) se x Dom(h), altrimenti f(x)= g(x) se f g\X, Dom(f) = Dom(g)\X e f(x)= g(x) Slide 3 Regole della Sem. Statica per Decs [d] s ( l ) = loc [ds] s ( loc ) = 0 _____________________________________________________ [d ds] s ( l ) = 0 [e] s ( l )=t _________________________________ id Dom( l ) [t id = e;] s ( l ) = l [t/id] ______________________________ id Dom( l ) [t id;] s ( l ) = l [t/id] [pl] ( l ],[(lt,void)/f]) = loc [sts] ( l ] loc ]) = * lt=types(pl) __________________________________________________________________ f Dom( l ) [void f(pl) {sts}] ( l ) = l [(lt,void)/f] [pl] ( l ],[(lt,t)/f]) = loc [sts] ( l ] loc ]) = * [e] ( l ] loc ]) = tlt=types(pl) _____________________________________________________________________________________ f Dom( l ) [t f(pl) {sts result e}] ( l ) = l [(lt,t)/f]t void [pl] ( l ],[(lt,t)/f]) = loc [ds] ( l ], loc ) = loc [sts] ( ) = * [e] ( ) = t lt=types(pl) __________________________________________________________________________________________ f Dom( l ) [t f(pl) {with ds do sts result e}] ( l ) = l [(lt,t)/f] = l ] loc ] t void [pl] ( l ],[(lt,void)/f]) = loc [ds] ( l ], loc ) = loc [sts] ( ) = *lt=types(pl) ________________________________________________________________________________ f Dom( l ) [void f(pl) {with ds do sts}] ( l ) = l [(lt,void)/f] = l ] loc ] Slide 4 Regole della Sem. Statica per Exps, Stats e Prog [e] s ( ) = t [es] s ( ) = lt ____________________________________ [e es] s ( ) = t lt [e] s ( ) = t __________________________ (id) = t [id = e] s ( ) = t ________________________ id Dom( ) [id] s ( ) = (id) (id) BTypes [es] ( ) = lt _____________________ (id) = (lt,t) [id(es)] ( ) = t [e 1 ] ( ) = int [e 2 ] ( ) = int ____________________________________ [e 1 + e 2 ] ( ) = int etc... [e] s ( ) = t ________________ [e;] s ( ) = * [e] s ( ) = bool [sts] s ( ) = * _________________________________________ [while (e) {sts} ] s ( ) = * [e] s ( ) = bool [sts 1 ] s ( ) = * [sts 2 ] s ( ) = * ______________________________________________________________ [if (e) {sts 1 } else {sts 2 } ] s ( ) = * [e] s ( ) = t ________________ [!e] s ( ) = * ____________________ (id) BTypes [?id] s ( ) = * [ds] ( ],[]) = [sts] s ( ) = * ________________________________________________ [ds main() sts] s ( ) = * Slide 5 Funzioni di Semantica Denotazionale [_] Prog :L Prog (LW) Input P Output [_] Decs :L Decs (LW) Env States P Env States [_] Dec :L Dec (LW) Env States P Env States [_] Dec (d,r,s) = [_] Decs (d,r,s) [_] VDec :L VDec (LW) Env States P Env States [_] VDec (d,r,s) = [_] Decs (d,r,s) [_] PDecs :L PDecs (LW) Env States P Env States [_] PDecs (d,r,s) = [_] Decs (d,r,s) [_] PDec :L PDec (LW) Env States P Env States [_] PDec (d,r,s) = [_] Decs (d,r,s) [_] FDec :L FDec (LW) Env States P Env States [_] FDec (d,r,s) = [_] Decs (d,r,s) [_] Type :L Type (LW) Set [_] Stats :L Stats (LW) Env States P States [_] Stat :L Stat (LW) Env States P States [_] Stat (st,r,s) = [_] Stats (st,r,s) [_] Exp :L Exp (LW) Env States P Value States [_] Exp (e,r,s) = [_] Exps (e,r,s) [_] Exps :L Exps (LW) Env States P Value + States Env = [L Id (LW) p Fun Loc ] Fin, dove Loc = T BTypes Loc T Fun = [Arg p Res], Arg = [Z| B] + States e Res = [Z| B|{ * }] States States = Input Output [Loc p Value] Fin, dove Value = T BTypes [T] e [int] = Z, [bool] = B, [void] = {*} Input = Output = Value * Nuova Loc Env States definito da Nuova(l,r,s) sse l (Im(r) Dom(s)) Slide 6 Regole della Sem. Denot. per Decs 1 ____________________________________________ [RT f(T x) {[with ds do]sts return e}](r,s) = (r[F/f],s) ______________________________________ [void f(T x) {[with ds do]sts}](r,s) = (r[F/f],s) F definita induttivamente da tutte le regole della semantica pi le seguenti 2 A [A w se c il with] e B, per leggibilit riportate nel riquadro [sts] (r[ /f,l x /x],s c [v/l x ] ) = s A _____________________________________ Nuova(l x,r,s c ) F(v,s c ) = ( *,s\{l x }) [e](r 0 [ /f],s 0 ) = (u,s) F(u,s) = ( *,s) B __________________________________________________ [f(e)] (r 0 [ /f],s 0 ) = ( *,s) [ds](r[ /f,l x /x],s c [v/l x ] ) = r 1,s 1 [sts] (r 1,s 1 ) = s A w ________________________________________________________ Nuova(l x,r,s c ) F(v,s c ) = ( *,s\{l x }) F definita induttivamente da tutte le regole della semantica pi le seguenti 2 A [A w se c il with] e B, per leggibilit riportate nel riquadro [sts] (r[ /f,l x /x],s c [v/l x ] ) = s 1 [e](r [ /f,l x /x],s 1 ) = (u,s) A ________________________________________________________ Nuova(l x,r,s c ) F(v,s c ) = (u,s\{l x }) [e](r 0 [ /f],s 0 ) = (v,s) F(v,s) = (u,s) B __________________________________________________ [f(e)] (r 0 [ /f],s 0 ) = (u,s) [ds](r[ /f,l x /x],s c [v/l x ] ) = r 1,s 1 [sts] (r 1,s 1 ) = s 2 [e](r 1,s 2 ) = (u,s) A w _____________________________________________________________________________ Nuova(l x,r,s c ) F(v,s c ) = (u,s\{l x }) Slide 7 Regole della Sem. Denot. per Decs ed Exps [d](r,s) = (r,s) [ds] (r,s) = (r,s) ___________________________________________________ [d ds] (r,s) = (r,s) ________________________________ Nuova(l,r,s) [t x](r,s) = (r[l/x],s[ /l]) l Loc T [e](r,s) = (v,s) ______________________________________ Nuova(l,r,s) [t x = e](r,s) = (r[l/x],s[v/l]) l Loc T [e] (r,s) = (v,s) [es] (r,s) = (lv,s) ___________________________________________________ [e es] (r,s) = (v lv,s) ___________________________ r(x) Loc [x](r,s) = (s(r(x)),s) [es](r,s) = (lv,s) ______________________________ [f(es)](r,s) = r(f)(lv,s) [e] (r,s) = (v,s) [e] (r,s) = (v,s) __________________________________________________ v + v = a [e + e] (r,s) = (a,s) [e](r,s) = (v,s) ______________________________________ [x = e](r,s) = (v,s[v/r(x)]) etc... Slide 8 Regole della Sem. Denot. per Stats e Prog [st] (r,s) = s [sts] (r,s) = s __________________________________________ [st sts ] (r,s) = s [e](r,s) = (v,s) _______________________ [e;](r,s) =s [e](r,s) = (tt,s) [sts] (r,s) = s ____________________________________________ [ if (e) {sts} else {sts} ] (r,s) = s [e](r,s) = (ff,s) ___________________________________ [ while (e) {sts} ] (r,s) = s [e](r,s) = (tt,s) [sts] (r,s) = s [ while (e) {sts} ] (r,s) = s 0 ___________________________________________________________________________________ [ while (e) {sts} ] (r,s) = s 0 [e](r,s) = (ff,s) [sts] (r,s) = s ____________________________________________ [ if (e) {sts} else {sts} ] (r,s) = s [ds]([],(i,,[])) = (r,s) [sts] (r,s) = (i,o,m) __________________________________________________________ [ ds main() sts ] (i) = o

Recommended

View more >