PLaC-0.1 Programming Languages and Compilers Prof. Dr. Uwe Kastens WS 2013 / 2014 (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 001 In the lecture: Welcome to the lecture! -------------------------------------------------------------------------------- PLaC-0.2 0. Introduction Objectives The participants are taught to * understand properties and notions of programming languages * understand fundamental techniques of language implementation, and to use generating tools and standard solutions, * apply compiler techniques for design and implementation of specification languages and domain specific languages Forms of teaching: Lectures Tutorials Exercises Homeworks Running project (c) 2008 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 002 Objectives: Understand the objectives of the course. In the lecture: The objectives are explained. Questions: * What are your objectives? * Do they match with these? * When did you last listen to a talk given in English? -------------------------------------------------------------------------------- PLaC-0.3 Contents Week Chapter 1 0. Introduction 2 1. Language Properties and Compiler tasks 3 - 4 2. Symbol Specification and Lexical Analysis 5 - 7 3. Context-free Grammars and Syntactic Analysis 8 - 10 4. Attribute Grammars and Semantic Analysis 11 5. Binding of Names 12 6. Type Specification and Analysis 13 7. Specification of Dynamic Semantics 13 8. Source-to-Source Translation 9. Domain Specific Languages Summary (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 003 Objectives: Overview over the topics of the course In the lecture: Comments on the topics. -------------------------------------------------------------------------------- PLaC-0.4 Prerequisites from Lecture Topic here needed for Foundations of Programming Languages: 4 levels of language properties Language specification, compiler tasks Context-free grammars Grammar design, syntactic analysis Scope rules Name analysis Data types Type specification and analysis Modeling: Finite automata Lexical analysis Context-free grammars Grammar design, syntactic analysis -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 004 Objectives: Identify concrete topics of other courses In the lecture: Point to material to be used for repetition Suggested reading: * Course material for Foundations of Programming Languages * Course material for Modeling Questions: * Do you have the prerequisites? * Are you going to learn or to repeat that material? -------------------------------------------------------------------------------- PLaC-0.5 References Material for this course PLaC: http://ag-kastens.upb.de/lehre/material/plac for the Master course Compilation Methods: http://ag-kastens.upb.de/lehre/material/compii Modellierung: http://ag-kastens.upb.de/lehre/material/model Grundlagen der Programmiersprachen: http://ag-kastens.upb.de/lehre/material/gdp John C. Mitchell: Concepts in Programming Languages, Cambridge University Press, 2003 R. W. Sebesta: Concepts of Programming Languages, 4. Ed., Addison-Wesley, 1999 U. Kastens: Übersetzerbau, Handbuch der Informatik 3.3, Oldenbourg, 1990 (not available on the market anymore, available in the library of the University) A. W. Appel: Modern Compiler Implementation in Java, Cambridge University Press, 2nd Edition, 2002 (available for C and for ML, too) W. M. Waite, L. R. Carter: An Introduction to Compiler Construction, Harper Collins, New York, 1993 U. Kastens, A. M. Sloane, W. M. Waite: Generating Software from Specifications, Jones and Bartlett Publishers, 2007 (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 005 Objectives: Useful references for the course In the lecture: Comments of the course material and books Questions: * Find the material in the Web, get used to its structure, place suitable bookmarks. -------------------------------------------------------------------------------- PLaC-0.5a References forReading Week Chapter Kastens Waite Eli Carter Doc. 1 0. Introduction 2 1. Language Properties 1, 2 1.1 - 2.1 and Compiler tasks 3 - 4 2. Symbol Specification 3 2.4 + and Lexical Analysis 3.1 - 3.3 5 - 7 3. Context-free Grammars 4 4, 5, 6 + and Syntactic Analysis 8 - 10 4. Attribute Grammars 5 + and Semantic Analysis 11 5. Binding of Names 6.2 7 + 12 6. Type Specification and Analysis (6.1) + 13 7. Specification of Dynamic Semantics 13 8. Source-to-Source Translation 9. Domain Specific Languages (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 005a Objectives: Associate reading material to course topics In the lecture: Explain the strategy for using the reading material -------------------------------------------------------------------------------- PLaC-0.6 Course material in the Web (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 006 Objectives: The root page of the course material. In the lecture: The navigation structure is explained. Assignments: Explore the course material. -------------------------------------------------------------------------------- PLaC-0.7 Commented slide in the course material (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 007 Objectives: A slide of the course material. In the lecture: The comments are explained. Assignments: Explore the course material. -------------------------------------------------------------------------------- PLaC-0.8 Organization of the course (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 008 Objectives: Know how the course is organized In the lecture: Comments on exams and registration Assignments: Explore the course material. -------------------------------------------------------------------------------- PLaC-0.9 What does a compiler compile? A compiler transforms correct sentences of its source language into sentences of its target language such that their meaning is unchanged. Examples: Source language: Target language: Programming language Machine language C++ Sparc code Programming language Abstract machine Java Java Bytecode Programming language Programming language (source-to-source) C++ C Domain specific language Application language LaTeX HTML Data base language (SQL) Data base system calls Application generator: Domain specific language Programming language SIM Toolkit language Java Some languages are interpreted rather than compiled: Lisp, Prolog, Script languages like PHP, JavaScript, Perl (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 009 Objectives: Variety of compiler applications In the lecture: Explain examples for pairs of source and target languages. Suggested reading: Kastens / Übersetzerbau, Section 1. Assignments: * Find more examples for application languages. * Exercise 3 Recognize patterns in the target programs compiled from simple source programs. Questions: What are reasons to compile into other than machine languages? -------------------------------------------------------------------------------- PLaC-0.10 What is compiled here? class Average class Average { private: { private int sum, count; int sum, count; public: public Average (void) Average () { sum = 0; count = 0; } { sum = 0; count = 0; } void Enter (int val) void Enter (int val) { sum = sum + val; count++; } { sum = sum + val; count++; } float GetAverage (void) float GetAverage () { return sum / count; } { return sum / count; } }; }; --------------- -------------- 1: Enter: (int) --> void _Enter__7Averagei: Access: [] pushl \%ebp Attribute quotesingle Codequotesingle (Length 49) movl \%esp,\%ebp Code: 21 Bytes Stackdepth: 3 Locals: 2 movl 8(\%ebp),\%edx 0: aload_0 movl 12(\%ebp),\%eax 1: aload_0 addl \%eax,(\%edx) 2: getfield cp4 incl 4(\%edx) 5: iload_1 L6: 6: iadd movl \%ebp,\%esp 7: putfield cp4 popl \%ebp 10: aload_0 ret 11: dup 12: getfield cp3 15: iconst_1 16: iadd (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 010 Objectives: Recognize examples for compilations In the lecture: Anwer the questions below. Questions: * Which source and target language are shown here? * How did you recognize them? -------------------------------------------------------------------------------- PLaC-0.11 What is compiled here? program Average; \documentstyle[12pt]{article} var sum, count: integer; \begin{document} aver: integer; \section{Introduction} procedure Enter (val: integer); This is a very short document. begin sum := sum + val; It just shows count := count + 1; \begin{itemize} \item an item, and end; \item another item. begin \end{itemize} sum := 0; count := 0; \end{document} Enter (5); Enter (7); aver := sum div count; ------------- end. ----------- \%\%Page: 1 1 void ENTER_5 (char *slnk , int VAL_4) 1 0 bop 164 315 a Fc(1)81 { b(In)n(tro)r(duction) 164 425 y Fb(This)16 {/* data definitions: */ b(is)g(a)h(v)o(ery)e(short) /* executable code: */ i(do)q(cumen)o(t.)j(It)c(just)g { (sho)o(ws)237 527 y Fa(\017)24 b SUM_1 = (SUM_1)+(VAL_4); Fb(an)17 b(item,) COUNT_2 = (COUNT_2)+(1); c(and)237 628 y Fa(\017)24 b ; Fb(another)17 b(item.) } 961 2607 y(1)p }}/* ENTER_5 */ eop (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 011 Objectives: Recognize examples for compilations In the lecture: Anwer the questions below. Questions: * Which source and target language are shown here? * How did you recognize them? -------------------------------------------------------------------------------- PLaC-0.12 Languages for specification and modeling SDL (CCITT) UML Specification and Description Language: Unified Modeling Language: (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 012 Objectives: Be aware of specification languages In the lecture: Comments on SDL and UML Suggested reading: Text Questions: What kind of tools are needed for such specification languages? -------------------------------------------------------------------------------- PLaC-0.13 Domain Specific Languages (DSL) A language designed for a specific application domain. Application Generator: Implementation of a DSL by a program generator Examples: * Simulation of mechatronic feedback systems * Robot control * Collecting data from instruments * Testing car instruments * Game description language: game BBall { size 640 480; background "pics/backgroundbb.png"; Ball einball; int ballsize; initial { ballsize=36; } events { pressed SPACE: { einball = new Ball(<100,540>, <100,380>); (c) 2006 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 013 Objectives: Understand DSL by examples In the lecture: Explain the examples Suggested reading: * C.W. Krueger: Software Reuse, ACM Computing Surveys 24, June 1992 * Conference on DSL (USENIX), Santa Babara, Oct. 1997 * ACM SIGPLAN Workshop on DSL (POPL), Paris, Jan 1997 Questions: Give examples for tools that can be used for such languages. -------------------------------------------------------------------------------- PLaC-0.14 Programming languages as source or target languages Programming languages as source languages: * Program analysis call graphs, control-flow graph, data dependencies, e. g. for the year 2000 problem * Recognition of structures and patterns e. g. for Reengineering Programming languages as target languages: * Specifications (SDL, OMT, UML) * graphic modeling of structures * DSL, Application generator => Compiler task: Source-to-source compilation (c) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 014 Objectives: Understand programming languages in different roles In the lecture: * Comments on the examples * Role of program analysis in software engineering * Role of Source-to-source compilation in software engineering Questions: Give examples for the use of program analysis in software engineering. -------------------------------------------------------------------------------- PLaC-0.15 Semester project as running example SetLan: A Language for Set Computation SetLan is a domain-specific language for programming with sets. Constructs of the the language are dedicated to describe sets and computations using sets. The language allows to define types for sets and variables and expressions of those types. Specific loop constructs allow to iterate through sets. These constructs are embedded in a simple imperative language. A source-to-source translator translates SetLan programs into Java programs. { set a, b; int i; The SetLan translator is implemented using the methods i = 1; and tools introduced in this course. a = [i, 3, 5]; The participants of this course get an implementation of a b = [3, 6, 8]; sub-language of SetLan as a starting point for their print a+b; printLn; work towards their individual extension of the language print a*b <= b; and the implementation. printLn; } (c) 2012 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Programming Languages and Compilers WS 2013/14 / Slide 015 Objectives: Get an idea of the task In the lecture: * Comment the task description. * Explain the role of the running example. Assignments: In the tutorial * Explain the application domain. * What may a game description contain? * Give examples for typical language constructs. * Explore the language. * Use the language. --------------------------------------------------------------------------------