Formal Languages, Automata and Compilers
Course information
Evaluation system
  • Structure: 7 seminars, 6 laboratories.
  • Final score: P = 2.5 *SA + 2.5 * LA + 5 * T
    • SA = seminar activity (max 10 points) = A + ST
      • A: 2 points for the activity during the seminar
      • ST: 8 points for written test
    • LA = laboratory activity (max 10 points)
      • homework (10 points)
      • Aditional points can be obtained by solving proposed problems during the laboratory
    • T written test during the examination session
    • Minimal conditions for passing the exam:

      SA >=4, LA >=4, SA + LA >=10, T >=5, final score P >=50

  • The final grade is obtained using the Gauss distribution
Laboratory and seminar general rules
  • Every student must attend the laboratories and seminars with the group he/she is registered in.
  • Any extrordinary situation that might require attending the seminar/laboratory with other group must be announced (the laboratory teacher will establish the way in which te activity must be re-scheduled).
  • The seminary written test (ST) cannot be re-taken during the re-examnination session!

  • Special information for students who failed the exam in the past 2 years: any of the grades over 5 obtained in the previous years for LA, SA can be taken into account this year.
Laboratory

Resources:

Laboratory attendance is mandatory. Any absence will lead to penalties in the final grade for the homework.

Lex Laboratory

Yacc/Bison laboratory

Homework

  • The homework must be solved in teams consisting of 2 students (from the same group).
Lectures
  • Lecture 1: Formal languages; Grammars; Chomsky Hierarchy; Type 3 grammars; Closure properties for regular languages
  • Lecture 2: Deterministic and Nondeterministic Finite Automata; Automata with epsilon-transitions
  • Lecture 3: Minimization of Deterministic Finite Automata; Type 3 Grammars and Finite Automata
  • Lecture 4: Regular expressions; The automaton equivalent to a regular expression;
  • Lecture 5: Context-free grammars and languages; The reduced form for type 2 grammars; Chomsky normal form; The recognition problem: CYK algorithm
  • Lecture 6: Pushdown automata; Pushdown automata and context-free languages
  • Lecture 7: Stages of compilation, Lexical analysis, General Bottom-up parsing
  • Lecture 8: Bottom-up parsing. LR(0) parsing. SLR(1) parsing. FIRST and FOLLOW
  • Lecture 9: LR(1) parsing. LALR(1) parsing.
  • Lecture 10: Semantic analysis. Semantic attributes. High-level intermediate code.
News