slide2 - PDF 무료 다운로드

Program P ::= CL CommandList CL ::= C C ; CL Command C ::= L = E while E : CL end print L Expression E ::= N ( E + E ) L &L LefthandSide L ::= I *L Variable I ::= <strings> Numeral N ::= <strings of digits> PTREE ::= CLIST CLIST ::= [ CTREE+ ] CTREE ::= ["=", LTREE, ETREE] ["while", ETREE, CLIST] ["print", LTREE] ETREE ::= NUM LTREE [ &, LTREE] [ +, ETREE, ETREE] LTREE ::= ID [ *, LTREE]

y = 5; z = 0; x = (6 + y) [["=", "y", "5"], ["=", "z", "0"], ["=", "x", [ +, 6, y ]] ] program interpclist interpctree interpetree interpltree environment namespace 0 1 2... memory

y = 5; z = 0; x = (6 + y) [["=", "y", "5"], ["=", "z", "0"], ["=", "x", [ +, 6, y ]] ] program interpclist interpctree interpetree interpltree y 0 environment namespace 0 1 2 5... memory

y = 5; z = 0; x = (6 + y) [["=", "y", "5"], ["=", "z", "0"], ["=", "x", [ +, 6, y ]] ] program interpclist interpctree interpetree interpltree y 0 z 1 environment namespace 0 1 2 5 0... memory

y = 5; z = 0; x = (6 + y) [["=", "y", "5"], ["=", "z", "0"], ["=", "x", [ +, 6, y ]] ] program interpclist interpctree interpetree interpltree y 0 z 1 x 2 environment namespace 0 1 2 5 0 11... memory

y = 4; z = &y; x = (7 + *z); *z = (y + 1) program [["=", "y", "4"], ["=", "z", ["&", "y"]], ["=", "x", [ +, 7, [ *, z ]]], [ =, [ *, z ], [ +, y, 1 ]] ] interpclist interpctree interpetree interpltree environment namespace 0 1 2... memory

L = E

memory = [] # memory = [5,0,11] env = {} # env = { y =0, z =1, x =2} def interpc(program): # pre: program == PTREE ::= [ CTREE+ ] # post: memory == program () global env, memory env = {} memory = [] interpclist(program) print( final env =, env) print( final memory =, memory) def interpclist(program): # pre: program == CLIST ::= [ CTREE+ ] # post: memory == program () for command in program: interpctree(command)

def interpltree(x): # pre: x == LTREE ::= ID [ *, LTREE] # post: ans == x # returns: ans if isinstance(x,str): if x in env: ans = env[x] else: memory.append( err ) env[x] = len(memory) - 1 ans = env[x] else: y = interpltree(x[1]) ans = memory[y] return ans

def interpctree(c): # pre: c == CTREE ::= [ =, LTREE, ETREE] [ while, ETREE, CLIST] [ print, LTREE] # post: memory == c () op = c[0] if op == = : lval = interpltree(c[1]) rval = interpetree(c[2]) memory[lval] = rval elif op == while : expr = c[1] body = c[2] while (interpetree(expr)!= 0) interpclist(body) elif op == print : print(interpetree(c[1])) else: crash( invalid command )

def interpetree(e): # pre: e == ETREE ::= NUM LTREE [ &, LTREE] [OP, ETREE, ETREE] # post: val == e () # returns: val if isinstance(e,str) and e.isdigit(): val = int(e) elif isinstance(e,list) and e[0] == + :: val1 = interpetree(e[1]) val2 = interpetree(e[2]) val = val1 + val2 elif isinstance(e,list) and e[0] == & : val = interpltree(e[1]) else: x = interpltree(e) val = memory[x] return val

declare y : int; declare z : *int; y = 4; z = &y; declare x : int; x = (7 + *z) *z = (y + 1) declare x : int; x = 0; declare y : int; y = (6 + &x) declare x : int; x = 0; *x = 999

Program P ::= CL CommandList CL ::= C C ; CL Command C ::= L = E while E : CL end print L declare I : T Type T ::= int *T Expression E ::= N ( E1 + E2 ) L &L LefthandSide L ::= I *L Variable I ::= <strings> Numeral N ::= <strings of digits> PTREE ::= [ CTREE+ ] CTREE ::= ["=", LTREE, ETREE] ["while", ETREE, CLIST] ["print", LTREE] [ dec, ID, TYPE] TYPE ::= [ ptr *, int ] ETREE ::= NUM LTREE [ &, LTREE] [ +, ETREE, ETREE] LTREE ::= ID [ *, LTREE]

declare y : int; declare z : *int; y = 4; z = &y; declare x : int; x = (7 + *z) *z = (y + 1) program interpclist interpctree interpetree interpltree environment namespace [[ dec, y, [ int ]], [ dec, z, [ ptr, int ]], ["=", "y", "4"], ["=", "z", ["&", "y"]], [ dec, x, [ int ]], ["=", "x", [ +, 7, [ *, z ]]], [ =, [ *, z ], [ +, y, 1 ]] ] 0 1 2... memory

declare y : int; declare z : *int; y = 4; z = &y; declare x : int; x = (7 + *z) *z = (y + 1) program interpclist interpctree interpetree interpltree y [ int ], 0 environment namespace [[ dec, y, [ int ]], [ dec, z, [ ptr, int ]], ["=", "y", "4"], ["=", "z", ["&", "y"]], [ dec, x, [ int ]], ["=", "x", [ +, 7, [ *, z ]]], [ =, [ *, z ], [ +, y, 1 ]] ] 0 1 2... memory

declare y : int; declare z : *int; y = 4; z = &y; declare x : int; x = (7 + *z) *z = (y + 1) program interpclist interpctree interpetree interpltree y [ int ], 0 z [ ptr, int ], 1 environment namespace [[ dec, y, [ int ]], [ dec, z, [ ptr, int ]], ["=", "y", "4"], ["=", "z", ["&", "y"]], [ dec, x, [ int ]], ["=", "x", [ +, 7, [ *, z ]]], [ =, [ *, z ], [ +, y, 1 ]] ] 0 1 2... memory

declare y : int; declare z : *int; y = 4; z = &y; declare x : int; x = (7 + *z) *z = (y + 1) program interpclist interpctree interpetree interpltree y [ int ], 0 z [ ptr, int ], 1 x [ int ], 2 environment namespace [[ dec, y, [ int ]], [ dec, z, [ ptr, int ]], ["=", "y", "4"], ["=", "z", ["&", "y"]], [ dec, x, [ int ]], ["=", "x", [ +, 7, [ *, z ]]], [ =, [ *, z ], [ +, y, 1 ]] ] 0 1 2 4 0... memory

memory = [] # memory = [5,0,11] env = {} # env = { y =([ int ],0), # z =([ ptr, int ],1), # x =([ int ],2)} def interpct(program): # pre: program == PTREE ::= [ CTREE+ ] # post: memory == program () global env, memory env = {} memory = [] interpclist(program) print( final namespace =, namespace) print( final memory =, memory) def interpclist(program): # pre: program == PTREE ::= [ CTREE+ ] # post: memory == program () for command in program: interpctree(command)

def interpltree(x): # pre: x == LTREE ::= ID [ *, LTREE] # post: ans == x (, ) # returns: ans if isinstance(x,str): if x in env: ans = env[x] else: crash( variable,x, undeclared ) else: datatype, loc = interpltree(x[1]) if datatype[0] == ptr : ans = (datatype[1:],memory[loc]) else: crash( variable not a pointer ) return ans

def interpctree(c): # pre: c == CTREE ::= [ =, LTREE, ETREE] [ while, ETREE, CLIST] [ print, LTREE] [ dec, ID, TYPE] TYPE ::= [ ptr *, int ] # post: memory == c () op = c[0] if op == = : type1,lval = interpltree(c[1]) type2,rval = interpetree(c[2]) if type1 == type2: memory[lval] = rval else: crash( incompatible types for assignment ) elif op == while : expr = c[1] body = c[2] type,val = interpetree(expr) while (val!= 0) interpclist(body) type,val = interpetree(expr) elif op == print : type,num = interpltree(c[1]) print(num) elif op == dec : x = c[1] if x in env : crash( variable,x, redeclared ) else: memory.append( err ) env[x] = (c[2],len(memory)-1) else: crash( invalid command )

def interpetree(e): # pre: e == ETREE ::= NUM LTREE [ &, LTREE] [ +, ETREE, ETREE] # post: ans == e (,) # returns: ans if isinstance(e,str) and e.isdigit(): ans = ([ int ],int(e)) elif isinstance(e,list) and e[0] == + :: type1,val1 = interpetree(e[1]) type2,val2 = interpetree(e[2]) if type1 == [ int ] and type2 == [ int ]: ans = ([ int ],val1 + val2) elif isinstance(e,list) and e[0] == & : type,val = interpltree(e[1]) ans = ([ ptr ]+type,val) else: type,loc = interpltree(e) ans = (type,memory[loc]) return ans

x = 7; y = new {f, g}; y.f = x; y.g = new {r}; y.g.r = y.f program interpclist interpctree interpetree interpltree α α heap

x = 7; y = new {f, g}; y.f = x; y.g = new {r}; y.g.r = y.f program interpclist interpctree interpetree interpltree α α x 7 heap

x = 7; y = new {f, g}; y.f = x; y.g = new {r}; y.g.r = y.f program interpclist interpctree interpetree interpltree α α x 7 y β heap β f g

x = 7; y = new {f, g}; y.f = x; y.g = new {r}; y.g.r = y.f program interpclist interpctree interpetree interpltree α α x 7 y β heap β f 7 g

x = 7; y = new {f, g}; y.f = x; y.g = new {r}; y.g.r = y.f program interpclist interpctree interpetree interpltree α α x 7 y β heap β f 7 g ɣ ɣ r

x = 7; y = new {f, g}; y.f = x; y.g = new {r}; y.g.r = y.f program interpclist interpctree interpetree interpltree α α x 7 y β heap β f 7 g ɣ ɣ r 7

Program CommandList Command Expression FieldNames LefthandSide Variable Numeral P ::= CL CL ::= C C ; CL C ::= L = E if E : CL1 else CL2 end print L E ::= N L ( E1 + E2 ) new { F } F ::= I I, F L ::= I L. I I ::= <string> N ::= <string of digits> PTREE ::= CLIST CLIST ::= [ CTREE+ ] CTREE ::= ["=", LTREE, ETREE] ["if", ETREE, CLIST, CLIST] ["print", LTREE] ETREE ::= NUM [ deref, LTREE] [ +, ETREE, ETREE] [ new, OB] OB ::= [ ID+ ] LTREE ::= ID [ dot, LTREE, ID ] ID ::= <string> NUM ::= <string of digits> a = new { f,g }; a.f = 3; a.g = (1 + a.f) [ ["=", ["a"], ["new", ["f","g"]]], ["=", [ dot, "a", "f"], "3"], ["=", [ dot, "a", "g"], ["+", "1", ["deref", [ dot,"a", "f"]]]] ]

L = E α heap x 7 y β β f 7 g ɣ ɣ r β

heap = {} # { ( = )+ } heap_count = 0 # x = 7; y = new {f,g,h}; y.g = 5; z = new {r}; z.r = (y.g + x); y.h = z heap h0 ns h0

heap = {} # { ( = )+ } heap_count = 0 # heap ns x = 7; y = new {f,g,h}; y.g = 5; z = new {r}; z.r = (y.g + x); y.h = z h0 x 7 h0

heap = {} # { ( = )+ } heap_count = 0 # heap ns x = 7; y = new {f,g,h}; y.g = 5; z = new {r}; z.r = (y.g + x); y.h = z h0 x 7 y h1 h0 h1 f nil g nil h nil

heap = {} # { ( = )+ } heap_count = 0 # heap ns x = 7; y = new {f,g,h}; y.g = 5; z = new {r}; z.r = (y.g + x); y.h = z h0 x 7 y h1 h0 h1 f nil g 5 h nil

heap = {} # { ( = )+ } heap_count = 0 # heap ns x = 7; y = new {f,g,h}; y.g = 5; z = new {r}; z.r = (y.g + x); y.h = z h0 x 7 y h1 z h2 h0 h1 f nil g 5 h nil h2 r nil

heap = {} # { ( = )+ } heap_count = 0 # heap ns x = 7; y = new {f,g,h}; y.g = 5; z = new {r}; z.r = (y.g + x); y.h = z h0 x 7 y h1 z h2 h0 h1 f nil g 5 h nil h2 r 12

heap = {} # { ( = )+ } heap_count = 0 # heap ns x = 7; y = new {f,g,h}; y.g = 5; z = new {r}; z.r = (y.g + x); y.h = r heap = { "h0": {"x":7, "y":"h1", "z":"h2"}, "h1": {"f":"nil", "g":5, h : h2 }, h0 h1 x 7 y h1 z h2 f nil g 5 h h2 h0 "h2": {"r":12} } heap_count = 3 h2 r 12

def cleartheheap(): global heap_count, heap heap_count = 0 heap = {} def allocatens(): global heap_count newhandle = h + str(heap_count) heap[newhandle] = {} heap_count = heap_count + 1 return newhandle def lookup(lval): ans = nil handle,fieldname = lval if handle in heap and fieldname in heap[handle] : ans = heap[handle][fieldname] else : crash( lookup error: lval =,str(lval)) return ans def store(lval,rval): handle, fieldname = lval if handle in heap : heap[handle][fieldname] = rval else: crash( store error: lval =,str(lval))

def interpret(program): # pre: program == PTREE ::= [ CTREE+ ] # post: memory == program () global ns cleartheheap() ns = allocatens() interpclist(program) print( final namespace =,namespace) print( final heap =,heap) def interpclist(program): # pre: program == PTREE ::= [ CTREE+ ] # post: memory == program () for command in program: interpctree(command)

def interpctree(c): # pre: c == CTREE ::= [ =, LTREE, ETREE] [ if, ETREE, CLIST, CLIST] [ print, LTREE] # post: heap == c () op = c[0] if op == = : lval = interpltree(c[1]) rval = interpetree(c[2]) store(lval,rval) elif op == if : test = interpetree(c[1]) if test!= 0: interpclist(c[2]) else: interpclist(c[3]) elif op == print : val = lookup(interpltree(c[1])) print(val) else: crash( invalid command )

def interpetree(e): # pre: e == ETREE ::= NUM [ deref, LTREE] [ +, ETREE, ETREE] [ new OBJ] OBJ ::= [ ID+ ] # post: ans == or or nil (+) # returns: ans ans = nil if isinstance(e,str) and e.isdigit(): ans = int(e) elif e[0] == + :: val1 = interpetree(e[1]) val2 = interpetree(e[2]) if isinstance(val1,int) and isinstance(val2,int): ans = val1 + val2 else: crash( addition error - non-int value used ) elif e[0] == deref : lval = interpltree(e[1]) ans = lookup(lval) elif e[0] == new : handle = allocatens() fields = e[1] for f in fields: store((handle,f), nil ) ans = handle else: crash( invalid expression ) return ans

def interpltree(ltree): # pre: x == LTREE ::= ID [ dot, LTREE, ID ] # post: ans == (,) # returns: ans if isinstance(ltree,str) : # ID ans = (ns,ltree) else: # [ dot, LTREE, ID ] lval = interpltree(ltree[1]) handle = lookup(lval) ans = (handle,ltree[2]) return ans

L y y.f y.h.r LTREE ["y"] [ dot, "y", "f"] [ dot, [ dot,"y", "h"], r ] ( h0, y ) ( h1, f ) ( h2, r ) heap h0 x 7 y h1 z h2 ns h0 h1 f nil g 5 h h2 h2 r 12