460-2018/04 – Programming Languages and Compilers (PJP)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantorIng. Marek Běhálek, Ph.D.Subject version guarantorIng. Marek Běhálek, Ph.D.
Study levelundergraduate or graduateRequirementCompulsory
Year3Semestersummer
Study languageEnglish
Year of introduction2019/2020Year of cancellation
Intended for the facultiesFEIIntended for study typesBachelor
Instruction secured by
LoginNameTuitorTeacher giving lectures
BEH01 Ing. Marek Běhálek, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Graded credit 2+2

Subject aims expressed by acquired skills and competences

Students get an overview of the area of programming, main programming paradigms (imperative, functional, logic) and their typical representatives. They also get some theoretical body of knowledge and practical experience of compiling methods, especially concentrated to the source code analysis and intermediate code synthesis phases. Students develop practical abilities to use compiler generators like JavaCC. After this lectures student should be able to effectively implement analyzers of a structured text data or of simple languages. Also they should understand concepts and constructions common for today's programming languages.

Teaching methods

Lectures
Tutorials
Project work

Summary

Students get an overview of the area of programming, main programming paradigms (imperative, functional, logic) and their typical representatives. They also get some theoretical body of knowledge and practical experience of compiling methods, especially concentrated to the source code analysis and intermediate code synthesis phases. Students develop practical abilities to use compiler generators like JavaCC.

Compulsory literature:

Torben Mogensen: Basics of Compiler Design - freely available at http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/

Recommended literature:

Aho, A. V., Lam M.S., Sethi, R., Ullman, J. D.: Compilers. Principles, Techniques, and Tools. Addison Wesley; 2nd edition (September 10, 2006). ISBN 0321486811.7 Pierce B.C.: Types and Programming Languages, MIT Press, 2002, ISBN: 9780262162098.

Way of continuous check of knowledge in the course of semester

Evaluation compose from two parts. During the exercise, students will be programing assigned tasks. The results of these tasks will be roughly the half of the final evaluation. Remaining points can be obtained for a project – a compiler that will be continuously implemented during the semester.

E-learning

Other requirements

There are no additional requirements for students. It is expected, that students will be able to write programs in Java, C# or in C++. Moreover, students should understand topics covered by course: Introduction to theoretical computer science.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

List of presentations: 1. Course introduction, introduction to compilers, compiler structure. Specification of programming languages. 2. Lexical analysis - finite automatons, regular expressions. Implementation of a lexical analyzer. 3. Syntactic analysis, top-down analysis. LL(1) grammars, computation of sets FIRST and FOLLOW. 4. Parser implementation - pushdown automaton for LL(1) languages. Recursive descent analysis. Compiler Compilers - javacc. 5. Syntax bottom – up analysis. LR(1) languages, tools: flex and Bison. 6. Internal representation of a program - intermediate program representation. Target code generating. 7. Semantic analysis, type checking 8. Run-time program structure - memory management. 9. Code optimization. 10. Advanced topics: operational semantics, syntax directed translation - attributed grammars. List of laboratories (it is expected, that all laboratories will be in a computer laboratories) 1. Implementation of a simple interpreter of mathematical expressions (to compare it with more advanced approaches presented later). 2. Implementation of a lexical analyzer. 3. Implementation of the algorithms computing sets First and Follow. 4. Implementation of a parser using recursive descent. 5. Introduction to Compiler Compilers - javacc. Project's first phase - parser in javacc will be implemented. 6. Tool ANTLR - usage visitor design pattern. 7. Second phase in the project - implementation of a type checker in the project. 8. Introduction to target code generation for JVM 9. Implementation of a target code generator. 10. Project evaluation.

Conditions for subject completion

Full-time form (validity from: 2019/2020 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Graded credit Graded credit 100  51
Mandatory attendence parzicipation: At least 80%

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2020/2021 (B0613A140010) Computer Science TZI P English Ostrava 3 Compulsory study plan
2019/2020 (B0613A140010) Computer Science TZI P English Ostrava 3 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner