A. I. Cuza University of Iaşi

Formal Languages, Automata and Compilers

Course nameFormal Languages, Automata and Compilers CodeCS2103
Class Undergraduate, 2008 - 2011
Level Licenţă Year 2 Semester 1 Status Compulsory
Hours per weekTotal hours per semesterTotal hours of individual workCreditsEvaluation typeTeaching language
CSLPr
2 1 1 0 56 94 5 M ro
Taught byAcademic and scientific title, name
Professor, PhD, Gheorghe Grigoraş
Required courses Algorithms and Programming ; Object Oriented Programming
ObjectivesTeaching fundamental concepts and results on the formal languages (especially those of type 2 and 3), finite automata and pushdown automata.
Building a lexical analyser using regular expressions and a scanner generator e.g. Lex
Building a sintactic analyser for an context free grammar using a parser generator e.g. Yacc
Using Lex - Yacc for designing a interpreter / compiler for a programming language
General thematicsLanguages and grammars, grammars classification (Chomsky hierarchy), Regular grammars and languages, Finite automata and accepted languages, Equivalence of deterministic models with the nondeterministic ones and witth regular grammars, Context free grammars and languages, Derivations in context free grammars, Ambiguity, Recognition of context free languages, Removing epsilon rules, Removing rules of the form A->B, Chomsky normal form, Pushdown automata, Programming languages: design, implementation, Lexical analysis, Syntax analysis, Semantic analysis, Top down (predictive) syntax analysis, Bottom up (shift reduce) syntax analysis, Recursive descent syntax analysis, LL Syntax Analysis, LR Syntax Analysis, Translation to intermediate code.
Seminary / Laboratory thematicsExamples of languages and grammars, Deterministic finite automata, Nondeterministic automata, Epsilon-transition automata; example, Regular expressions, examples with reference to lexical units of programming languages, Context free grammars independent of, the derivation of trees, eliminating unnecessary symbols, eliminating rules of erasing , Redenumirilor, Chomsky normal form, with word recognition algorithm CYK, Automatic Pushdown; examples, lexical analyzer's manual, obtained with an analyzer tool-LEX, analyze using tools YACC type, Interpreter built with Lex and YACC.
Teaching methodsSlides with course items; seminar themes; projects’ issues; electronic version of the course; main readings will be found on the web page
Bibliography
  1. Grigoras, Gh. Constructia compilatoarelor - Algoritmi fundamentali, Ed. Universitatii Al. I. "Cuza Iasi", 274 pg., 2005.
  2. Jucan Toader - Limbaje formale şi automate, Editura Matrix Rom, Bucureşti, 1999, 162 p.
  3. Jucan Toader, Ştefan Andrei – Limbaje formale şi teoria automatelor. Teorie şi practică, Editura Universităţii “Al. I. Cuza”, Iaşi, 2002, 327p.
  4. Stoughton Alley, Formal Language Theory, Kansas State University, Draft of Fall 2007.
  5. Yehezkael R.B., Course notes on Formal Languages and Compilers, Jerusalem College of Technology, December 2004.
  6. Manual LEX,  Manual FLEX,  Manual YACC,  Manual Bison,  Compiler Construction using Flex and Bison
EvaluationconditionsSeminars’ activity (SA), participation to tutorial hours for clarifying the issues regarding project elaboration, participation to laborator hours (LA), participation to final exam (FE)
criteriasSA >= 5, LA >= 5
modesSA: questions, participation at discussions, original solutions to problems(a mark between 1 - 10)
LA: each topic is evaluated with a mark between 1 and 10.
T1, T2: 2 written tests (weeks 8, 16), FE = (T1+T2)/2.
formulaFormula of the final score: 30% SA + 30% LA + 40% FE and ECTS criteria
© 2006-2010 FII | about | intranet