Syllabus: CS 401 - Introduction to Compilers

Course Description:

This course introduces fundamental concepts and techniques in designing and implementing compilers. It covers finite automata, regular expressions, context-free grammars, lexical analysis, parsing, and the construction of compiler components. Students will gain practical experience by working on a term project in C/C++ programming, which involves creating the various components of a compiler.

Prerequisites:

At least C in CS/EET 122, CS 301

Textbook:

Compilers: Principles, Techniques, and Tools (2nd Edition), Aho, Lam, Sethi, Ullman. ISBN-10 : 0321486811, ISBN-13 : 9780321486813, Addison Wesley

Course Learning Objectives:

• Understand the theoretical concepts of regular languages, context-free languages, regular expressions, context-free grammars, and formal language hierarchy.
• Use Thompson's construction to convert from regular expressions to NFA and apply subset construction to convert from NFA to DFA.
• Implement recursive descent parsing for a small grammar.
• Understand LL and LR parsing techniques for context-free languages.
• Use table-driven top-down (LL(1)) and bottom-up (SLR) parsing methods to parse context-free languages.
• Apply the concepts of scanning, parsing, symbol table management, abstract syntax tree representation, and code generation in the construction of a compiler.
• Apply relevant tools (e.g., lex, yacc, flex, bison, and make) to develop a medium-sized C/C++ project.

Course Topics:

• Introduction to Compilers: The Structure of a Compiler
• Lexical analysis:
  • Regular expressions
  • Finite-state automata (deterministic and non- deterministic)
  • Regular expressions from/to finite-state automata conversion
  • String matching
• Syntax Analysis:
  • Context-free grammars (CFG)
  • Parsing algorithms
  • Abstract syntax trees (ASTs)
  • CFGs classes

Course Grading

Project	60%
Labs/Quizzes/Homeworks	15%
Exams	25%