CPS323 Lecture: Programming Language Implementation4/19/09Objectives:1. To overview the spectrum of options ranging from pure compilation to direct interpretation2. To overview the structure of a compiler or interpreter3. To overview the processes of tokenization and parsing4. To introduce “optimization” strategies5. To overview operations performed after compilation is complete (linking, loading)Materials:1. Projectable of Compiler Phases2. Projectable of Pipe and Filter Architecture for a Compiler3. Projectable of calculator.l and Scanner.java4. Handout of Syntax Diagrams, parse tree, flex/bison grammar rules and Java interpreter code for a simple desk calculator5. Projectable of parsing tables generated by bison for this grammar6. Projectable of recursive descent parser for this grammar 7. Projectable of Java compileer for this grammar 8. Demonstration programs - interpreter for simple desk calculator produced from flex/bison rules (in calculator.l, calculator.y); interpreter produced from recursive descent parser (Scanner.java, Interpreter.java, InterpreterMain.java); “compiler” produced from recursive descent parser (Scanner.java, Compiler.java, CompilerMain.java). 9. Projectable of Figure 15.1I. IntroductionA. Thus far in the course, we have focussed on programming language features with limited attention given to how these features are actually implemented. Now, we are shifting our focus to iimplementation.B. Larger CS programs often offer full-blown courses - or even sequences of courses - relating to issues like compilation. Our approach here, though, will be very much a quick overview, since this is not really a “programming language implementation” course.1C. Nonetheless, some understanding of implementation issues is important for a variety of reasons.1. Efficiency of implementation issues may influence what features are included or excluded from a programming language.a) Example: Many programming languages incorporate some sort of “switch” statement [ e.g. FORTRAN computed goto, C/C++/Java switch; Ada case ]. Typically, it is required that the expression to be switched on be of an ordinal (discrete) type. We saw earlier in the course that such a construct has an efficient implementation using a jump table. OTOH, allowing the expression to be switched on to be of a non-discrete type would require explicit tests for each possible value (as in the LISP case), and is generally disallowed (LISP being the exception).b) Bjarne Stroustrup has this to say about the inclusion of virtual functions in C++ (the first C family language to offer dynamic dispatch)“The idea was borrowed from Simula and presented in a form that was intended to make a simple and efficient implementation easy” (The Design and Evolution of C++ p. 72)2. Appreciation of implementation issues may affect how one uses a particular featureExample: Knowledge of how two-dimensional arrays are stored in memory should influence which subscript is used for the outer loop and which for the inner loop when doing some operation on every element of an array.II. Compilation and InterpretationA. One sometimes hear’s a particular programming language described as “a compiled language” or an “interpreted language”. Examples:ASKThe distinction is an important one, but not as simple as the use of these terms may sound. 1. There is, in fact, a spectrum of approaches.22. It is better to think of compiled versus interpreted implementations of a language, rather than compiled versus interpreted languages, since virtually any language could, in principle, be implemented either way (though usually one alternative is a lot cleaner for a given language).B. We begin with a basic definition: what does it mean to “interpret” a program?ASK(From CPS112 intro lecture): “We say that a computer system interprets a program when it carries out the actions specified by that program.”1. Thus, there is a sense in which all computer programs are interpreted. In part, the distinction between “compiled” and “interpreted” relates to the question of what does the interpretation - the hardware, or a software interpreter that is itself interpreted by the hardware? Thus, a more precise usage of the term “interpreted” (as that term is commonly used) would be “software interpreted.”2. A compiler is basically a translator that translates the source form of a program into a form that is more easily interpreted by hardware.C. Perhaps a clearer way to look at the distinction is to look at two issues:1. The user’s perspective:a) One typically thinks of an implementation of a language as being a compiled implementation if the user must carry out an explicit compilation step between writing a program and running it.Examples from this course: FORTRAN, Adab) OTOH, one typically thinks of an implementation of a language as being an interpreted implementation if the user can enter a statement and see the result of executing it immediately.Examples from this course: LISP, Prolog, Python, Ruby2. The computer memory perspectivea) One typically thinks of an implementation of a language as being a compiled implementation if there is a software component (the compiler) that is not (or at least does not need to be) present in memory when the program is running.3b) One typically thinks of an implementation of a language as being an interpreted implementation if the full implementation of the language needs to be present in memory when the program is running.c) Notice that, under either model, there will be some components of the implementation present in memory when the program is running - e.g. a library of runtime support routines, or perhaps even a virtual machine implementation. The distinction is whether all the components of the implementation need to be present.D. I mentioned earlier that there is really a spectrum of approaches - with the classic notions of compilation and interpretation being the ends of the spectrum.1. Classically, compilers were designed to translate all the way to the machine language of some platform - which meant that a compiler would need to be both language and platform specific. Some newer language implementations are based on a compiler that generates code for a “virtual machine” which is then interpreted by a platform-specific virtual machine interpreter. (The target language is commonly referred to as “bytecodes”).Examples?ASKa) A key advantage of this