ÍÃ×ÓÏÈÉú

Catalog description: 

Examination of the nature of programming languages and programs which implement them. Compiler and interpreter design and implementation techniques. Review of grammars and languages (context free, context sensitive, regular). Design of interactive interfaces. Parsing of context free languages. Lexical analysis. Semantic analysis and code optimization.

Prerequisite:

CSE 274

Required topics (approximate weeks allocated):

• Overview of the translation process (.5)
• Formal notations (1)
  • review of regular expressions
  • review of formal grammars
• Compiler tools (1.5)
  • currently available tools (e.g., lex and yacc)
• Lexical analysis (2)
  • regular expression
  • automata
  • tokens
• Syntax analysis (3)
  • parsers
  • context-free grammars
  • top-down parsing
  • bottom-up parsing
  • LL(1) grammars and parsing
  • LR grammars and parsing
  • parser generators
• Semantic processing (3)
  • syntax-directed translation
  • symbol tables
  • type checking
  • type systems
  • type equivalence
  • type conversions
  • run-time environments
  • attribute grammars
• Code optimization (1)
• Code generation (1)
• Compiler project (1)
• Exams/Review (1)

Learning Outcomes:

1. Create lexers/scanners for moderately complex computer languages
   • Explain and demonstrate the use of regular expressions for lexing/scanning
   • Explain and demonstrate the use of common compiler tools for creating lexers/scanners (e.g. Lex, Flex)
2. Create parsers for moderately complex computer languages
   • Explain and demonstrate the use of recursive descent to parse a program
   • Explain and demonstrate the use of common compiler tools for creating parsers (e.g. Yacc, Bison)
   • Explain the difference between parse trees and abstract syntax trees, and create them by hand
3. Generate executable code from an abstract syntax tree, both programmatically and by hand
4. Create a complete compiler for a moderately complex computer language
5. Explain some elementary compiler code optimization techniques
6. (Graduate students only) Demonstrate higher analytic application through independent implementation of a non-trivial programming language feature in a compiler that they have created