CSE 5317Lecture'7:'Seman.c'analysis'of'OO'programs9'Feb'2010Nate'NystromUniversity'of'Texas'at'ArlingtonWednesday, February 10, 2010ProjectPA'1'due'Feb'25Type'checking'of'MiniJava◾Given'parser'+'ASTs'+'visitor'interfaces◾Implement'class'table'classes◾Write'a'pass'to'traverse'the'AST'to'populate'the'class'table◾Implement'type'descriptor,'typing'environment'classes◾Write'a'pass'to'traverse'the'AST◾to'compute'types'for'each'expression◾to'check'types'for'each'node◾to'save'the'computed'types'in'a'HashMap<Node,Type>◾you'will'need'this'for'the'next'project◾if'an'error'is'caught,'report'it'and'just'exit2Wednesday, February 10, 2010ProjectWork'in'groups'of'twoLet'me'know'your'partner'by'next'Tuesday'(email'me)You'may'not'change'partnersHow'to'work:◾divide'up'the'work'so'that'you'can'work'in'parallel'as'much'as'possible◾e.g.,'work'on'independent'modules,'one'codes'while'other'tests3Wednesday, February 10, 2010How not to do it4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself2.Be(lazy(and(let(your(partner(do(all(the(work4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself2.Be(lazy(and(let(your(partner(do(all(the(work3.Have(a(different(person(implement(each(assignment,(ensuring(that(no(one(has(a(clue(what’s(going(on(in(the(end4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself2.Be(lazy(and(let(your(partner(do(all(the(work3.Have(a(different(person(implement(each(assignment,(ensuring(that(no(one(has(a(clue(what’s(going(on(in(the(end4.Spend(all(your(Dme(talking(rather(than(coding4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself2.Be(lazy(and(let(your(partner(do(all(the(work3.Have(a(different(person(implement(each(assignment,(ensuring(that(no(one(has(a(clue(what’s(going(on(in(the(end4.Spend(all(your(Dme(talking(rather(than(coding5.Spend(all(your(Dme(coding(rather(than(talking4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself2.Be(lazy(and(let(your(partner(do(all(the(work3.Have(a(different(person(implement(each(assignment,(ensuring(that(no(one(has(a(clue(what’s(going(on(in(the(end4.Spend(all(your(Dme(talking(rather(than(coding5.Spend(all(your(Dme(coding(rather(than(talking6.Spend(all(your(Dme(coding(and(talking(rather(than(tesDng4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself2.Be(lazy(and(let(your(partner(do(all(the(work3.Have(a(different(person(implement(each(assignment,(ensuring(that(no(one(has(a(clue(what’s(going(on(in(the(end4.Spend(all(your(Dme(talking(rather(than(coding5.Spend(all(your(Dme(coding(rather(than(talking6.Spend(all(your(Dme(coding(and(talking(rather(than(tesDng7.Start(three(days(before(the(deadline4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself2.Be(lazy(and(let(your(partner(do(all(the(work3.Have(a(different(person(implement(each(assignment,(ensuring(that(no(one(has(a(clue(what’s(going(on(in(the(end4.Spend(all(your(Dme(talking(rather(than(coding5.Spend(all(your(Dme(coding(rather(than(talking6.Spend(all(your(Dme(coding(and(talking(rather(than(tesDng7.Start(three(days(before(the(deadline8.Ignore(what(is(taught(in(class4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself2.Be(lazy(and(let(your(partner(do(all(the(work3.Have(a(different(person(implement(each(assignment,(ensuring(that(no(one(has(a(clue(what’s(going(on(in(the(end4.Spend(all(your(Dme(talking(rather(than(coding5.Spend(all(your(Dme(coding(rather(than(talking6.Spend(all(your(Dme(coding(and(talking(rather(than(tesDng7.Start(three(days(before(the(deadline8.Ignore(what(is(taught(in(class9.Don’t(ask(the(prof(or(the(TA(any(quesDons4Wednesday, February 10, 2010How not to do it1.Decide(your(partner(is(useless(and(do(all (the(work(yourself2.Be(lazy(and(let(your(partner(do(all(the(work3.Have(a(different(person(implement(each(assignment,(ensuring(that(no(one(has(a(clue(what’s(going(on(in(the(end4.Spend(all(your(Dme(talking(rather(than(coding5.Spend(all(your(Dme(coding(rather(than(talking6.Spend(all(your(Dme(coding(and(talking(rather(than(tesDng7.Start(three(days(before(the(deadline8.Ignore(what(is(taught(in(class9.Don’t(ask(the(prof(or(the(TA(any(quesDons10.Assume(the(prof(is(merciful4Wednesday, February 10, 2010ProjectSubmit:◾your'code◾your'test'cases◾be'sure'to'check'the'corner'casesShould'run'with:◾java'Typecheck'<'C.java5Wednesday, February 10, 2010Symbol tablesThe'“symbol'table”'is'implemented'with'mul.ple'data'structuresEach'compiler'pass'needs'different'a^ributes'for'symbolsNeed'to'preserve'only'some'of'this'info rma.on'across'passes◾Class'table◾stores'informa.on'about'each'class' in' the'program◾Typing'environment◾maps'variable'names'to'type'descriptors◾implemented'as'a'stack'of'scopes◾Type'map◾maps'AST'nodes'for'expressions'to'their'types'for'later'passes'to'use◾Others◾during'register'alloca.on:'loca.ons'of'spilled'temporaries◾during'code'gen:'map'of'labels'names'to'code'addresses6Wednesday, February 10, 2010Semantic analysis passesClass'table'builder◾traverses'the'AST,'builds'class'tableType'checker◾traverses'the'AST,'computes'types,'checks'types◾uses'class'table'to'lookup'field,'method'types◾saves'types'of'AST'nodes'in'type'map◾instead,'could'save'types'in'AST'nodes'themselves,'but'JTB'doesn’t'allow'thisIR'lowering◾convert'AST'to'lowerclevel'IR'(“Piglet”'in'the'project)◾uses'type'map'and'class'table'to'lookup'methods7Wednesday, February 10, 2010Class tableMaps'class'names'to'class'table'entries:◾class'name◾enclosing'class,'package'(if'any)◾superclass'name'(used'to'lookup'class'table'entry)◾superinterface'names◾method'names,'parameter'types,'return'type,'access'flags,'excep.ons'thrown,'other'modifiers'(synchronized,'na.ve)◾field'names,'types,'constant'values,'access'flags◾member'class'names8Wednesday, February 10, 2010Hash consing names9Symbol'table'lookups'happen'frequently!String'comparisons'are'expensiveOhen'be^er'to'hash$cons'the'symbols◾Share'values'that'are'structurally'equal◾Go'through'hash'table'to'map'each'symbol'to'a'uniqu