编译原理复习

1、复习Target codeSource codeScannerParserSemantic analyzerSource code optimizerCode generatorTarget code optimizerTokensSyntax TreeAnnotated TreeIntermediate codeTarget codeLiteral tableSymbol tableError handlerAuxiliary components that interact with some phasesCompiling processScanner Regular expressio

2、n + automaton NFA,DFAs Convert NFAs to DFAs.RegularexpressionsNFADFALexicalSpecificationTable-driven Implementation of DFAMinimizParser CFG: production Derivation, leftmost and rightmost parse tree, abstract syntax tree Top-down and bottom-up Predictive lookaheadParser Top-down: LL(1) grammar FirstS

3、et and FollowSet nullable nontermianls Left Factor and Left RecursionLL(1) GrammarA 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 First(A) contains , First(A) Follow(

4、A) = .Parser Top-down: Recursive-Descent parser and LL(1) parser LL(1) parser LL(1) Parsing TablesInputParsing 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 stringsThe Construction of Parsing TablesRepeat the

5、following two steps for each nonterminal A and production choice A 1. For each token a in First(), add A to the entry MA,a2. if is in First(), for each element a of Follow(A) (token or $), add A to MA,aLL(1) Parse TablesParser Bottom-up Rightmost derivation traced in reverse(reduction) Right sentent

6、ial form Handle: a string is a substring in right sentenial form that matches the right hand side of a production viable prefixParser LR parser Shift and reduce Parsing table: action and goto State Item LR(0) DFA: Closure Operation and Goto Operation SLR(1) parser Only reduce A if the next token t i

7、s in FOLLOW(A).Schematic Form of LR parserLR Parsing Program$S0Xm-1Sm-1XmSm$anaia1gotoactionStackInputOutputParsing TableS EE T;ET+ET intT (E)T (E)E T;ET+ET intT (E)T int E T ;ET+EET+ESE ETET+EE T;ET+ET intT (E)intT (E)T (E)EE+intTintT(;E T ;)S EE T;E T + ET intT (E)A LR(0) DFAstartSemantic analysis Attribute Grammar SDD Dependency Graphs- Evaluation Order Synthesized and Inherited AttributesAttribute computations for the number 345oval=229val=28*8+5=229base=8base=8val=3*8+4=28base=8val=5base=8val=3base=8val=4base=8val=3base=8based-numnumbasecharnumdigitnumdigitdigit345oCode generationIn