Different languages and paradigms Finer points of languages Lexical analysis to assembly generation Automated tools and their use Overall structure of a compiler We will be using a tool that generates fairly complicated Java and it will be necessary to understand the output You and your group will write perhaps 5000 lines of Java you will not have time to learn it Prerequisite Java Fluency Practice of Compiler Construction Theory of language design Objectives Prof Stephen A Edwards Fall 2005 Columbia University Department of Computer Science Pieter Bruegel The Tower of Babel 1563 COMS W4115 Programming Languages and Translators Testing will be as important as development Makefiles version control test suites Teams will build a large software system Prerequisite COMS W3157 Advanced Programming Alfred V Aho Ravi Sethi and Jeffrey D Ullman Compilers Principles Techniques and Tools Addison Wesley 1985 Required Text Tuesdays and Thursdays 11 00 AM to 12 15 PM Prof Stephen A Edwards sedwards cs columbia edu http www1 cs columbia edu sedwards 462 Computer Science Building Office Hours 1 2 PM Tuesday 2 3 PM Thursday We will be working with regular and context free languages You need to understand grammars Prerequisite COMS W3261 Computability and Models of Computation Project is most important but most students do well on it Grades for tests often vary more 10 Individual homework 30 Final at end of term 20 Midterm near middle of term 40 Programming Project Assignments and Grading Holidays November 8 Election day November 24 Thanksgiving Final project report December 20 Final December 8 in class Midterm November 10 Lectures September 6 to December 6 Room 702 Hamilton Hall Schedule Instructor 2 4 pages Give some examples of its syntax and an explanation of what it does Follow the style of the C language reference manual Appendix A of Kernighan and Ritchie The C Programming Langauge see the class website 8 Complete listing 7 Lessons Learned 6 Test Plan 5 Architectural Design 4 Project Plan 3 Language Reference Manual 2 Language Tutorial 1 Introduction the proposal A careful definition of the syntax and semantics of your language Describe the language that you plan to implement Explain what problem your language can solve and how it should be used Describe an interesting representative program in your language Final Report Sections Harder than you might think Might want to discuss with a TA you d like to have so it is convenient for him her as well 3 Select a weekly meeting time Languages come out better from dictatorships not democracies Besides you ll have someone to blame 2 Elect a team leader Language Reference Manual Exception CVN students do the project by themselves All members of the team should be familiar with the whole project Suggested division of labor Front end back end testing documentation You ll be stuck with them for the term choose wisely 1 Decide who you will work with First Three Tasks The Project Project Proposal 5 A final project presentation 4 A final project report 3 A compiler or interpreter for your language running on some sample programs 2 A language reference manual defining it formally 1 A proposal describing and motivating your language Each team will develop its own langauge Immediately start forming four person teams to work on this project Design and implement your own little language Five deliverables Teams Don t cheat on assignments If you re dumb enough to cheat I m smart enough to catch you Tests Will be closed book with a one page cheat sheet of your own devising Do your homework by yourself The Project Schedule will be continually updated during the semester Exception CVN students do the project by themselves Collaborate with your team on the project Off my home page http www1 cs columbia edu sedwards Contains syllabus lecture notes and assignments Collaboration Class Website October 20 December 20 Reference Manual Final Report The semantics of C says this computes the nth Fibonacci number 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 What a well formed program means Components of a language Semantics What s in a Language September 27 soon Proposal Due Dates Mathematical function manipulator Simple scripting language a la Tcl Petri net simulation language Specifying Syntax Usually done with a context free grammar Projectile motion simulation langauge Matlab like array manipulation language Screenplay animation language Components of a language Syntax How characters combine to form words sentences paragraphs The chickens are ready for eating Or ambiguous expr expr expr expr digit expr expr expr expr expr class Bar public float foo return 0 public int foo return 0 Ambiguous in Java class Foo int bar int x return Foo Nonsensical in Java Something may be syntactically correct but semantically nonsensical The rock jumped through the hairy planet Semantics expr Semantics Is syntactically correct Java but isn t C class Foo public int j public int foo int k return j k is syntactically correct English but isn t a Java program Typical syntax for algebraic expressions Web surfing language Geometric figure drawing language The quick brown fox jumps over the lazy dog Music manipulation language harmony Quantum computing language Model train simulation language Think of awk or php not Java or C Escher like pattern generator Simple animation language A small domain specific language Examples from earlier terms Other language ideas Design a language Shows how to build the function representing the behavior of the program i e a transformation of inputs to outputs from statements in the language Denotational semantics Define a virtual machine and how executing the program evolves the state of the virtual machine Operational semantics Source Jim Weigang http www chilton com jimw gsrand html Algol 68 source http www csse monash edu au lloyd tildeProgLang Algol68 treemerge a68 PROC trav INT switch TREE t SCANNER continue alternative VOID traverse the root node and right sub tree of t only IF t IS NIL THEN continue switch alternative ELIF e OF t switch THEN print e OF t traverse switch r OF t continue alternative ELSE e OF t switch PROC defer INT sw SCANNER alt VOID trav sw t continue alt alternative e OF t defer FI PROC insert INT e REF TREE t VOID NB inserts in t as a side effect IF TREE t IS NIL THEN t HEAP NODE e TREE NIL TREE NIL ELIF e e OF t THEN insert e l OF t ELIF e e OF t THEN insert e r OF t FI Imperative block structured language
View Full Document
Unlocking...