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.

General Competencies

The course prepares students for application of the analysis-synthesis design model, which is widely used in software engineering. Acquired knowledge of algorithms, data structures, and translation methods are applicable in a wide range of computer applications. Students will be able to build efficient software products by optimally exploiting language translators and other software tools. Furthermore, students will be able to design and build their own language translators for end-user languages.

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 of an efficient language translation process with respect to processor resources and memory hierarchy

Forms of Teaching

Lectures

Lecturer-driven classroom presentations, examples of practical application of formal languages, automata, and grammars during the compiler construction

Exams

Two written exams

Exercises

Lecturer-driven classroom problem solving, preparation for written exams

Laboratory Work

Compiler construction for a simplified C-like programming language. Individual work or work in a small team comprised of fellow students. Online submission and evaluation of student work.

Consultations

Individual office hours with lecturers and assistants are organized on student's request.

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Comment: Percent of Grade
Laboratory Exercises 50 % 40 % 50 % 0 %
Class participation 0 % 5 % 0 % 0 %
Mid Term Exam: Written 0 % 30 % 0 %
Final Exam: Written 0 % 30 %
Exam: Written 50 % 100 %
Comment:

Continuous Assessment: Min (Mid Term Exam: Written + Final Exam: Written + Lecture attendance and oral examination in classroom) = 50 %

Week by Week Schedule

  1. Basic phases of translation process: analysis and synthesis; Source program analysis: lexical, syntax, and semantic analysis; ([1], pp. 1-12) Target program synthesis: intermediate code generation, optimization, and target code generation; ([1], pp. 13-19)
  2. Error handling during translation; Performance evaluation of translation process; Classification of language translators; ([1], pp. 19-31) Lexical analysis; Role and data structure of lexical analyzer; Interaction with syntax analyzer; Ambiguity in lexical analysis; Transliteration, tokens, lexical errors, and error-recovery methods; ([1], pp. 44-55)
  3. Lexical analyzer generators; Program Lex; ([1], pp. 56-70) Syntax analysis; Role and data structure of syntax analyzer; Languages for syntax rules definition; Simple parsing techniques: CO-NO table-based parsing; ([1], pp. 71-84) Exercises: lexical analysis;
  4. Top-down parsing; S, Q, and LL(1) grammar; SELECTION sets finding; ([1], pp. 84-103) SELECTION sets finding (continuation); Adjustment of productions to LL(1)-grammar; Error handling; Bottom-up parsing; ([1], pp. 103-121)
  5. Bottom-up parsing techniques: Shift-Identify parsing, Shift-Reduce parsing, and operator-precedence parsing; ([1], pp. 121-137) LR parsing; ([1], pp. 138-147)
  6. LR parsing (continuation); Parser generators; Program Yacc; Semantic analysis; Role and formal models of semantic analyzer; Operations of semantic analyzer; ([1], pp. 147-166) Exercises: syntax analysis;
  7. Operations of semantic analyzer (continuation); Syntax-directed semantic analysis: attribute translation grammar; ([1], pp. 167-180) L-attribute translation grammar; Pushdown automata for L-attribute translation grammar; ([1], pp. 180-190)
  8. First mid term exam: lexical, syntax, and semantic analysis;
  9. Pushdown automata for L-attribute translation grammar (continuation); Recursive descent method for L-attribute translation grammar; Type system; ([1], pp. 190-200) Type checking; Type equivalence; Run-time support for target program execution; ([1], pp. 200-223)
  10. Abstract data structures of source program and internal storage structures of target program; Program flow execution based on procedures; Memory management; ([1], pp. 223-233) Non-local names access; ([1], pp. 233-242)
  11. Input/output parameter passing; Intermediate code generation; Levels and forms of intermediate code; ([1], pp. 243-256) Levels and forms of intermediate code (continuation); Syntax-directed intermediate code generation; Target program generation; Target program generator structure; ([1], pp. 256-265)
  12. Target program generator structure (continuation); ([1], pp. 265-276) Target program generator algorithms; Target program generator generators; ([1], pp. 276-285) Second mid term exam: lexical analysis, syntax analysis;
  13. Preparation of target program for execution; Load-and-go language translators; Absolute and relocatable code generators; Generators of separate files of relocatable machine code; Linkers and loaders; Optimization; Program-execution analysis; ([1], pp. 286-297) Program-execution analysis (continuation); ([1], pp. 297-305)
  14. Machine-dependent and machine-independent optimization; Peephole optimization; Brief survey of other optimization methods; ([1], pp. 305-317) Exercises: semantic analysis, target program generation, optimization;
  15. Final exam: whole course matter;

Study Programmes

University undergraduate
Computer Science (module)
Specialization courses (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

S. Srbljić (2007.), Prevođenje programskih jezika, Element Zagreb
D. Grune, H. E. Bal, C. J. H. Jacobs, K. G. Langendoen (2000.), Modern Compiler Design, Wiley
A. V. Aho, R. Sethi, J. D. Ullman (1986.), Compilers: Principles, Techniques, and Tools, Addison-Wesley
K. Cooper, L. Torczon (2003.), Engineering a Compiler, Morgan Kaufmann
S. S. Muchnick (1997.), Advanced Compiler Design and Implementation, Morgan Kaufmann
(.), Algorithms for Compiler Design O. G. Kakde Charles River Media 2002,

Lecturers

Exercises

Laboratory exercises