CSE 401 Compilers Class

Details / Midterm Review

Overall Compiler Organization what's in the front/back end what the job of each phase is Lexical Analysis Terminology lexeme, token, pattern Regular expressions the notation *how you build them, concrete examples advantages limitations naming them Scanners 4 steps: RE -> NFA -> DFA -> code/tables why use an NFA? a DFA? *constructing an NFA *constructing a DFA Syntactic Analysis Context-free grammar BNF: terminals, nonterminals, productions *how you build them, concrete examples advantages limitations Derivations abstract vs. concrete (parse) syntax trees

Parsing algorithms top-down vs. bottom-up predictive parsing table-driven & recursive descent implementations LL(1) grammars *ambiguity & fixes meta-rules (code/precedence tables) rewrite grammar change language *common prefixes (left factoring) *left recursion Building a table-driven predictive parser *PREDICT(nonterminal, input symbol) *FIRST(RHS) *FOLLOW(nonterminal) Semantic Analysis Type checking basics examples type checking algorithm: bottom up Symbol table attributes for each type of symbol *scopes: when created, how used, why have them *handling procedures *handling records Strong, weak, static, dynamic typing Type equivalence structural vs name