YSC1212 Lecture Notes, Week 02

• Bootstrapping
  • Goal
  • Bootstrapping an ML compiler
  • Exercise 1
  • Version
• On interpretive overheads
  • Goal
  • Exercise 2
  • Version
• Computational paradigms
  • Goal
  • Imperative programming
  • Functional programming
  • Logic programming
  • Rewriting
  • Other computational paradigms
  • Version
• Finite description of arbitrarily large data
  • Goal
  • Grammars for finite languages
  • Grammars as a logical system
  • Grammars as a rewriting system
  • Abstract-syntax trees
  • Concrete and abstract syntax
  • Parsing and unparsing
  • Using a grammar to generate grammatically correct sentences
  • Grammars for infinite languages
  • Using a grammar to generate grammatically correct sentences, continued
  • Exercise 3
  • Exercise 4
  • Exercise 5
  • Soundness and completeness
  • Example of a sound representation
  • Example of an unsound representation
  • Example of a complete representation
  • Example of an incomplete representation
  • A sound and complete representation of natural numbers
  • Computer data
  • The onion, revisited
  • More agricultural vagaries: the case of shallots
  • Version
• Syntax of regular expressions
  • Goal
  • A BNF for regular expressions
  • Exercise 6
  • Exercise 7
  • A BNF for regular expressions, logically
  • Exercise 8
  • Exercise 9
  • Syntax errors
  • Version
• Semantics of regular expressions
  • Goal
  • Resources
  • Reminder: abstract syntax of regular expressions
  • Semantics of regular expressions
  • Exercise 10
  • Exercise 11
  • Exercise 12
  • Exercise 13
  • Exercise 14
  • Resources
  • Version
• Exercises
  • Mandatory exercises
  • Recommended exercises
  • Exercise 15
  • Exercise 16
  • Version