Programming Languages andTranslatorsCOMS W4115Pieter Bruegel, The Tower of Babel, 1563Prof. Stephen A. EdwardsSpring 2007Columbia UniversityDepartment of Computer ScienceInstructorProf. Stephen A. [email protected]://www1.cs.columbia.edu/˜sedwards/462 Computer Science BuildingOffice Hours: 3–4 PM Tuesday, 4–5 PM WednesdayScheduleMondays and Wednesdays, 1:10 PM to 2:25 PM627 MuddLectures: January 17 to April 30Midterm: March 7Final: April 30 (in-class)Final project report: May 7Holidays: March 12-16, Spring BreakObjectivesTheory of language design•Finer points of languages•Different languages and paradigmsPractice of Compiler Construction•Overall structure of a compiler•Automated tools and their use•Lexical analysis to assembly generationRequired TextAlfred V. Aho, Monica S. Lam, RaviSethi, and Jeffrey D. Ullman.Compilers: Principles, Techniques,and Tools.Addison-Wesley, 2006. SecondEdition.Assignments and Grading40% Programming Project20% Midterm (near middle of term)30% Final (at end of term)10% Individual homeworkProject is most important, but most students do well on it.Grades for tests often vary more.Prerequisite: Java FluencyYou and your group will write perhaps 5000 lines of Java;you will not have time to learn it.We will be using a tool that generates fairly complicatedJava and it will be necessary to understand the output.Prerequisite: COMS W3157Advanced ProgrammingTeams will build a large software systemMakefiles, version control, test suitesTesting will be as important as developmentPrerequisite:COMS W3261 Computability andModels of ComputationYou need to understand grammarsWe will be working with regular and context-freelanguagesClass WebsiteOff my home page,http://www1.cs.columbia.edu/˜sedwards/Contains syllabus, lecture notes, and assignments.Schedule will be continually updated during the semester.CollaborationCollaborate with your team on the project.Do your homework by yourself.Tests: Will be closed book with a one-page “cheat sheet”of your own devising.Don’t cheat on assignments: If you’re dumb enough tocheat, I’m smart enough to catch you.The ProjectThe ProjectDesign and implement your own little language.Five deliverables:1. A proposal describing and motivating your language2. A language reference manual defining it formally3. A compiler or interpreter for your language running onsome sample programs4. A final project report5. A final project presentationTeamsImmediately start forming four-person teams to work onthis project.Each team will develop its own langauge.Suggested division of labor: Front-end, back-end, testing,documentation.All members of the team should be familiar with the wholeproject.First Three Tasks1. Decide who you will work withYou’ll be stuck with them for the term; choose wisely.2. Elect a team leaderLanguages come out better from dictatorships, notdemocracies. Besides, you’ll have someone to blame.3. Select a weekly meeting timeHarder than you might think. Might want to discusswith a TA you’d like to have so it is convenient forhim/her as well.Project ProposalDescribe the language that you plan to implement.Explain what problem your language can solve and how itshould be used. Describe an interesting, representativeprogram in your language.Give some examples of its syntax and an explanation ofwhat it does.2–4 pagesLanguage Reference ManualA careful definition of the syntax and semantics of yourlanguage.Follow the style of the C language reference manual(Appendix A of Kernighan and Ritchie, The CProgramming Langauge; see the class website).Final Report Sections1. Introduction: the proposal2. Language Tutorial3. Language Reference Manual4. Project Plan5. Architectural Design6. Test Plan7. Lessons Learned8. Complete listingDue DatesProposal February 7 soonReference Manual March 5Final Report May 7Design a language?A small, domain-specific language.Think of awk or php, not Java or C++.Examples from earlier terms:Quantum computing languageGeometric figure drawing languageProjectile motion simulation langaugeMatlab-like array manipulation languageScreenplay animation languageOther language ideasSimple animation languageModel train simulation languageEscher-like pattern generatorMusic manipulation language (harmony)Web surfing languageMathematical function manipulatorSimple scripting language (`a l´a Tcl)Petri net simulation languageWhat’s in aLanguage?Components of a language: SyntaxHow characters combine to form words, sentences,paragraphs.The quick brown fox jumps over the lazy dog.is syntactically correct English, but isn’t a Java program.class Foo {public int j;public int foo(int k) { return j + k; }}Is syntactically correct Java, but isn’t C.Specifying SyntaxUsually done with a context-free grammar.Typical syntax for algebraic expressions:expr → expr + expr| expr − expr| expr ∗ expr| expr/expr| digit| (expr)Components of a language:SemanticsWhat a well-formed program “means.”The semantics of C says this computes the nth Fibonaccinumber.int fib(int n){int a = 0, b = 1;int i;for (i = 1 ; i < n ; i++) {int c = a + b;a = b;b = c;}return b;}SemanticsSomething may be syntactically correct but semanticallynonsensical.The rock jumped through the hairy planet.Or ambiguousThe chickens are ready for eating.SemanticsNonsensical in Java:class Foo {int bar(int x) { return Foo; }}Ambiguous in Java:class Bar {public float foo() { return 0; }public int foo() { return 0; }}Specifying SemanticsDoing it formally beyond the scope of this class, butbasically two ways:•Operational semanticsDefine a virtual machine and how executing theprogram evolves the state of the virtual machine•Denotational semanticsShows how to build the function representing thebehavior of the program (i.e., a transformation ofinputs to outputs) from statements in the language.Most language definitions use an informal operationalsemantics written in English.Great Moments inProgramming Language EvolutionAssemblyBefore: numbers5589E58B45088B550C39D0740D39D07E0829D039D075F6C9C329C2EBF6After: Symbolsgcd: pushl %ebpmovl %esp, %ebpmovl 8(%ebp), %eaxmovl 12(%ebp), %edxcmpl %edx, %eaxje .L9.L7: cmpl %edx, %eaxjle .L5subl %edx, %eax.L2: cmpl %edx, %eaxjne .L7.L9: leaveret.L5: subl %eax, %edxjmp .L2FORTRANBeforegcd: pushl %ebpmovl %esp, %ebpmovl 8(%ebp), %eaxmovl 12(%ebp), %edxcmpl %edx, %eaxje .L9.L7: cmpl %edx, %eaxjle .L5subl %edx, %eax.L2: cmpl %edx, %eaxjne .L7.L9: leaveret.L5: subl %eax, %edxjmp .L2After: Expressions,
View Full Document
Unlocking...