Login

Language Theory Description

Key Elements

Code

INFO 306

Formation

BS Computer Sciences

Semester

6

Credits

5

Number of Teaching Hours

24

Number of Tutoring Sessions

18

Number of Laboratory Sessions

6

Content

Objective

This course is an introduction to the theory of automata and languages (regular expressions, finite automata, grammars) and compilation. It has the following objectives: • Present the concepts needed to translate one language into another • Understand the basic principles of compilation • Study the lexical and syntactic analysis of compilation.

Content

I. Formal languages A. basic concepts B. Fundamental problems C. Chomsky hierarchy II. Regular Languages and finite automata A. Construction of a regular language B. Regular expressions C. Finite automata D. Algorithms 1. Thompson construction 2. Construction of a DFA from a NFA 3. Construction of a DFA from a regular expression 4. Minimization of a DFA E. Exercises III. Application regular expression A. the flex tool IV. Context-free Languages, grammars and stack automata A. Context-free grammars B. grammar Transformations 1. Left factorization 2. Elimination of left recursion. V. Construction of analyzers for context-free grammars A. Analysis of context-free languages B. Top-down analysis 1. Principles of top-down analysis 2. Top-down recursion 3. Predictive and not recursive analyzer of type LL(l)