Another review of the compiler Compiler Front End Lexer => Parser => Semantic Analysis; usually language specific. Compiler Mid End Optimizer; usually shared across many languages. Compiler Back End Codegen parser parser does parsing parser: takes sequence of tokens from the lexer and produce AST of the program. General goal is to distinguish between valid and invalid strings of tokens. Importantly, we don’t really emit errors from parsing; instead we just do it at the layer below and above. NOTE: FORM of the CFGs is very important. We use Context-Free Grammars example Consider: if x = y then 1 else 2 fi parser gets IF ID = ID THEN INT ELSE INT FI parser makes Chomsky Hierarchy Levels of languages, in increasing amounts of difficulty. regular languages CFGs (pushdown automatas)—they have a stack CSGs (context sensitive grammars) Recursively Enumerable languages (undecidable languages)