编译原理复习

1、复习 Target code Source code Scanner Parser Semantic analyzer Source code optimizer Code generator Target code optimizer Tokens Syntax Tree Annotated Tree Intermediate code Target code Literal table Symbol table Error handler Auxiliary components that interact with some phases Compiling process Scanne

2、r Regular expression + automaton NFA,DFAs Convert NFAs to DFAs. Regular expressions NFA DFA Lexical Specification Table-driven Implementation of DFA Minimiz Parser CFG: production Derivation, leftmost and rightmost parse tree, abstract syntax tree Top-down and bottom-up Predictive lookahead Parser T

3、op-down: LL(1) grammar FirstSet and FollowSet nullable nontermianls Left Factor and Left Recursion LL(1) Grammar A grammar is LL(1) grammar if the following conditions are satisfied: For each production A 1|2|n, for all i and j, 1i, j n, ij , First(i) First(j) = For each nonterminal A such that Firs

4、t(A) contains , First(A) Follow(A) = . Parser Top-down: Recursive-Descent parser and LL(1) parser LL(1) parser LL(1) Parsing Tables Input Parsing stack stores the symbols waiting to be matched in parsing $ is used to mark the bottom of the stack $ is used to mark the end of the input strings The Con

5、struction of Parsing Tables Repeat the following two steps for each nonterminal A and production choice A 1. For each token a in First(), add A to the entry MA,a 2. if is in First(), for each element a of Follow(A) (token or $), add A to MA,a LL(1) Parse Tables Parser Bottom-up Rightmost derivation

6、traced in reverse(reduction) Right sentential form Handle: a string is a substring in right sentenial form that matches the right hand side of a production viable prefix Parser LR parser Shift and reduce Parsing table: action and goto State Item LR(0) DFA: Closure Operation and Goto Operation SLR(1)

7、 parser Only reduce A if the next token t is in FOLLOW(A). Schematic Form of LR parser LR Parsing Program $ S0 Xm-1 Sm-1 Xm Sm $anaia1 gotoaction Stack Input Output Parsing Table S E E T; ET+E T int T (E) T (E) E T; ET+E T int T (E) T int E T ; ET+E ET+E SE E T ET+E E T; ET+E T int T (E) int T (E) )

8、 T (E) E E + int T int T ( ( ; E T ; ) S E E T; E T + E T int T (E) A LR(0) DFA start Semantic analysis Attribute Grammar SDD Dependency Graphs- Evaluation Order Synthesized and Inherited Attributes Attribute computations for the number 345o val=229 val=28*8+5=229 base=8 base=8 val=3*8+4=28 base=8 val=5 base=8 val=3base=8val=4 base=8 val=3base=8 based-num numbasechar numdigit numdigit digit 3 4 5 o Code generatio