CSE 5317Lecture'1:'Introduc.on19'Jan'2010Nate'NystromUniversity'of'Texas'at'ArlingtonFriday, February 5, 2010What is a programming language?Medium'for'communica.ng'our'inten.ons'to'machines,'and'to'other'people,'and'to'ourselvesA'language'should'express'computa.on:◾precisely◾at'a'high'level◾so'we'(and'the'machine)'can'reason'about'themMake'it'easier'to'write'programs'that&really&work2Friday, February 5, 2010Compilers◾Compiler◾a'program'that'tran slates'an'executable'program'in'on e'language'into'an'executable'program'in'another'language◾usually'higherKlevel'to'lowerKlevel◾e.g.,%C%to%x86,%Java%to%JVM%bytecode,%C++%to%C◾lower'to'higher'='“decompiler”,'“disassembler”◾Interpreter◾a'program'that'reads'an'executable'program'and'produces'the'results'of'running'that'program◾This'course'deals'mainly'with'compilers,'but'much'applies'to'both3Friday, February 5, 2010Why study compilers?◾Where'the'rubber'meets'the'road◾Understand'h ow'highKlevel'code'is'implemented'on'hardware◾Understand'wh at'the'compiler'can'do'for'you◾makes'you'a'bePer'programmer◾avoid%unnecessary%op<miza<on,%help%the%compiler%generate%beAer%code◾and'what'it'can’t'do◾“why%won’t%this%method%get%inlined?”◾Compilers'are'i nteres.ng'programs'in'their'own'right◾complex'data'structures,'algorithms◾transforma.ons'between'data'structures4Friday, February 5, 2010Microcosm◾Compiler'construc.on'is'a'microcosm'of'computer'science◾AI◾greedy'algorithms,'learning'algorithms,'search◾Algorithms◾graph'algorithms,'unionKfind,'dynamic'programming◾Theory◾DFAs'for'scanning,'parser'generators,'laUce'theory◾Systems◾alloca.o n'an d'n aming,'locality,'synchroniza.on◾Architecture◾pipeline'management,'hierarchy'management,'instruc.on'set'use5Friday, February 5, 2010Solved problem?◾Machines'are'constantly'changing◾Changes'in'architecture'=>'changes'in'compilers◾new'features'pose'new'probl ems◾changing'costs'lead'to'different'concerns◾old'solu.on'need'reKengineering◾Full'Employment'Theorem'for'Compiler'Writers◾Changes'in'compilers'should 'prompt'changes'in'architecture◾new'languages'and'features6Friday, February 5, 2010Intrinsic merit◾Compiler'construc.on'is'challenging'and'fun◾interes.ng'problems◾primary'responsibili ty'(blame)'for'performance◾new'architectures'=>'new'challenges◾real'results◾extremely'complex'interac.ons◾Compilers'have'an'impact'on'how'computers'are'used◾Compiler'construc.on'poses'some'of'the'most'interes.ng'problems'in'compu.ng7Friday, February 5, 2010Translators◾You'probably'won’t'write'a'compiler'ever'again,'but'you'probably'will'write:◾a'parser◾commandGli ne%arguments◾network%protocols◾marshaling/unmarshaling%of%data%structures◾file%I/O◾a'state'machin e◾distributed%systems%algorithms◾an'interpreter◾any%code%that%reads%d ata%and%does%something%based%on%that%data◾a'transforma.on◾any%code%that%translates%one%data%structure%into%another%“equivalent” %data%structure8Friday, February 5, 2010Qualities◾What'quali.es'are'important'in'a'compiler?◾correct'code◾output'runs'fast◾compiler'runs'fast◾compile'.me'propor.onal'to'program'size◾support'for'separate'compila.on◾good'diagnos.cs'for'syntax'errors◾works'well'with'debugger◾good'diagnos.cs'for'seman.c'errors◾cros s'lan guage'calls◾consistent,'predictable'op.miza.on◾Each 'of'th ese'shapes'your'feelings'about'the'correct'contents'of'this'course9Friday, February 5, 2010AdministriviaFriday, February 5, 2010Things to doStart'brushing'up'on'JavaReview'Java'development'toolsFind'hPp://ran ger.uta.edu/~nystrom/courses/531711Friday, February 5, 2010Grading◾homework'15'(5+5+5)◾project'50'(10+10+10+10+10)◾midterm'15◾final'2012Friday, February 5, 2010Assignments◾3'small'wriPen'assignments◾submit'electronically◾late'penalty:'10*2floor(n)'percent'if'n'days'late◾readability'and'speling'counts!13Friday, February 5, 2010ProjectWrite'a'compiler'for'a'subset'of'Java5'parts◾type'checking◾IR'lowering◾IR'canonicaliza.on◾register'alloca.on◾MIPS'code'genera.oneach'part'depends'on'previous'partswork'in'groups'of'2I'will'provide'much'of'the'code14Friday, February 5, 2010“Honesty'may'not'be'the'best'policy,'but'it'is'worth'trying'once'in'a'while.”–Richard'Nixon,'1970You'may'discuss'concepts'with'others'in'the'classBut'cite'your'sourcesAll'wri.ng'must'be'your'ownAll'code'must'be'you r'own'(or'your'group’s)Do'not'show'others'your'codeDo'not'copy'code'from'other'students,'the'web,'books,'etc.Do'not'collaborate'on'examsIf'caught'chea.ng,'you'will'get'K100%'on'the'assignment'or'exam'and'I'will'file'paper work'with'the'Office'of'Academic'IntegrityFriday, February 5, 2010About me◾Programming'language'research◾focus'on'extensibility,'concurrency,'type'systems◾Polyglot'K'an'extensible'compiler'framework◾Thorn'K'a'scalable'scrip.ng'language◾X10'K'a'concurrent'OO'language'for'highKperf'compu.ng◾Compiler'experience◾BLOAT'Java'bytecode'op.mizer◾HP'lowKlevel'op.mizer'for'PAKRISC◾HP'Java'compiler,'VM◾Polyglot'Java'compiler◾Thorn'compiler'at'IBM◾X10'compiler'at'IBM16Friday, February 5, 2010Compiler architectureFriday, February 5, 2010Abstract view◾recognize'legal'(and'illegal)'programs◾generate'correct'code◾manage'sto rage'of'all'variables'and'code◾agree'on'format'for'target'(object,'assembly)'code18compilersource%codetarget%codeerrorsFriday, February 5, 2010Traditional two-pass compiler◾intermediate'representa.on'(IR)◾fro nt'end'maps'legal'code'to'IR◾back'end'maps'IR'onto'target'machine◾simplify'retarge.ng◾allow'mul.ple'front'ends◾mul.ple'passes'=>'bePer'code19front%endsource%codetarget%codeerrorsback%enderrorsIRFriday, February 5, 2010A fallacy◾Can'we'build'n *m'compilers'with'n+m'components?◾must'encode&all'knowledge'in'each'front'end◾must'represent'all'the'features'in'on e'IR◾must'handle'all'the'features'in'each'back'end20front%endFortranx86back%endC++JavaPrologMIPSJVMback%endback%endfront%endfront%endfront%endMLfront%endFriday, February 5, 2010Front end◾Responsibili.es:◾recognize'legal'code◾report'errors◾produce'IR◾preliminary'storage'map◾shape'the'code'for'the'back'end◾Much'of'the'front'end'construc.on'can'be'automated21scannersource%codeIRerrorsparsererrorstokensFriday, February 5,
View Full Document