Programming Language Translation

Course Description

The processes of incremental hierarchical translation of end-user languages, high-level languages, and languages of virtual machines into target language of given computer system are studied. The techniques and principles of language translation processes in modern pervasive, ubiquitous, and invisible distributed systems are described. Brief survey and history of programming languages and language translators are given. Language translation is explained through basic processes of source program analysis and target program synthesis. Major phases of analysis (lexical, syntax, and semantic analysis) and synthesis (intermediate code generation, optimization, and target code generation) are included. Run-time and load-time support for program execution is presented. Language translator generators are studied.

Learning Outcomes

  1. breakdown the design of a computer system into problem analysis phase and solution synthesis phase
  2. describe lexical, syntax, and semantic properties of a programming language using formal grammar
  3. select optimal formal grammar for formal description of a programming language
  4. select optimal parsing technique for programming language translation
  5. design and implement a compiler from formal specification of a programming language
  6. design an efficient language translation process with respect to processor resources and memory hierarchy

Forms of Teaching

Lectures

Lecturer-driven classroom presentations of theoretical concepts with examples and problem solving

Laboratory

Software implementation of specific parts of compiler or compiler in general. Students individually implement given assignment in a recommended programming language or tool, and submit their solutions to automatic online evaluation.

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Threshold Percent of Grade
Laboratory Exercises 50 % 30 % 50 % 0 %
Mid Term Exam: Written 50 % 35 % 0 %
Final Exam: Written 50 % 35 %
Exam: Written 50 % 100 %
Exam: Oral 100 %

Week by Week Schedule

  1. Programs that take (other) programs as input such as interpreters, compilers, type-checkers, documentation, generators, Data structures to represent code for execution, translation, or transmission, Interpretation vs; compilation to native code vs; compilation to portable intermediate representation, Language translation pipeline: parsing, optional type-checking, translation, linking, execution
  2. Lexical analysis using regular expressions, Lexical analyser generators
  3. Top-down parsing (S, Q, and LL(k) grammar, recursive descent parsing)
  4. Bottom-up parsing (shift-identify, shift-reduce, LR parsing)
  5. Parser generators
  6. Abstract syntax trees, Attributed syntax trees, High-level program representations such as abstract syntax trees, Scope and binding resolution
  7. Type checking, Attribute and attribute-translation grammars
  8. Midterm exam
  9. Run-time representation of core language constructs such as objects (method tables) and first-class functions (closures), Run-time layout of memory: call-stack, heap, static data, Procedure calls and method dispatching
  10. Memory management, Manual memory management: allocating, de-allocating, and reusing heap memory, Automated memory management: garbage collection as an automated technique using the notion of reachability, Dynamic memory management approaches and techniques: malloc/free, garbage collection
  11. Data layout for objects and activation records, Just-in-time compilation and dynamic recompilation, Other common features of virtual machines, such as class loading, threads, and security, Static and dynamic linking
  12. Basic blocks, Static single assignment, Source code, native code, and virtual machine code, Separate compilation; Linking, Absolute, relocatable, and virtual machine target code, Syntax-driven code generation, Intermediate code generation
  13. Control-flow graphs, Def-use chains, Instruction scheduling, Instruction selection, Register allocation
  14. Implementing loops, recursion, and tail calls, Machine-independent optimization, Machine-dependent optimization, Peephole optimization
  15. Final exam

Study Programmes

University undergraduate
Computer Science (module)
Specialization courses (5. semester)
Computing (study)
(5. semester)
Information Processing (module)
Specialization courses (5. semester)
Software Engineering and Information Systems (module)
(5. semester)
Telecommunication and Informatics (module)
Specialization courses (5. semester)

Literature

Siniša Srbljić (2009.), Prevođenje programskih jezika, Element
Dick Grune, Kees van Reeuwijk, Henri E. Bal, Ceriel J.H. Jacobs, Koen Langendoen (2012.), Modern Compiler Design, Springer Science & Business Media
Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman (2007.), Compilers: Principles, Techniques, and Tools, Pearson College Division
Keith Cooper, Linda Torczon (2011.), Engineering a Compiler, Elsevier
Steven Muchnick, Muchnick and Associates (1997.), Advanced Compiler Design Implementation, Morgan Kaufmann
O. G. Kakde (2003.), Algorithms for Compiler Design, Charles River Media

Associate Lecturers

For students

General

ID 183425
  Winter semester
5 ECTS
L1 English Level
L2 e-Learning
60 Lectures
10 Laboratory exercises

Grading System

88 Excellent
75 Very Good
63 Good
50 Acceptable

Similar Courses