Languages and Translations

The course cannot be taken simultaneously with:

Languages and Translations (36JPR)

The course is a substitute for:

Languages and Translations (36JPR)

Lecturer:

Jan Holub

Tutor:

Jan Holub

Supervisor:

Department of Computer Science and Engineering

Synopsis:

Theory of formal languages, definition and classification of grammars, regular languages, regular grammars and regular expressions, deterministic and non-deterministic finite automata, context-free grammars, parsing, pushdown automata, LL and LR grammars (parsing, transformations), formal translation, translation grammars, finite transducers and regular translation grammars, pushdown transducer and context-free translation grammars, LL and LR translations, attribute grammars, evaluation of attributes.

Requirements:

http://service.felk.cvut.cz/courses/X36JPR/

Syllabus of lectures:

1. Basic notions of the theory of languages, definitions and grammar classification

2. Regular languages, regular grammars, and regular expressions

3. Nondeterministic and deterministic finite automata

4. Context-free grammars, parsing of context-free languages

5. Pushdown automata, relation between context-free grammars and pushdown automata

6. LL grammars, parsing tables, parsing

7. Transformations of context-free grammars to LL grammars

8. LR grammars, basic notions

9. LR grammars, parsing

10. LR grammars, parsing table construction

11. Formal translations, basic notions, translation grammar

12. Translation automata and grammars

13. Formal translation directed by LL parser

14. Formal translation directed by LR parser

Syllabus of tutorials:

1. Construction of grammars for simple languages

2. Finite automata for simple languages

3. Relation between regular grammars and finite automata

4. Relation between regular expressions and finite automata

5. Relation between regular expressions and regular grammars

6. Context-free grammars, basic transformations

7. Pushdown automata

8. LL grammars, parsing table construction, parsing

9. Transformations of context-free grammars to LL grammars

10. LR grammars - table construction

11. LR grammars - parsing

12. Translation grammars and automata

13. Formal translation in LL parsing

14. Formal translation in LR parsing

Study Objective:

Study materials:

1. Melichar, B., Holub, J., Mužátko, P.: Languages and Translations. Publishing House of CTU, Praha 1997.

Note:

Time-table for winter semester 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Fri	roomKN:E-308 Holub J. 12:45–14:15 (lecture parallel1 parallel nr.101) Karlovo nám. Lab K308 roomKN:E-308 Holub J. 12:45–14:15 (lecture parallel1) Karlovo nám. Lab K308
Thu
Fri

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Computer Technology - Software Engineering- structured studies (compulsory elective course, compulsory elective course, S3 recommendation)
• Computer Technology - System Programming- structured studies (compulsory course of the branch)
• Computer Technology - Computer Graphics- structured studies (compulsory elective course)
• Computer Technology - Computer Network and Internet- structured studies (compulsory elective course)
• Computer Technology - Designing Digital Systems- structured studies (compulsory elective course)