編譯原理教學課件：總復習

1、總復習Target codeSource codeScannerParserSemantic analyzerSource code optimizer/Intermediate code generatorCode generatorTarget code optimizerTokensSyntax TreeAnnotated TreeIntermediate codeTarget codeIdentify logical pieces of the description.Identify how those pieces relate to each other.Identify the

2、 meaning of the overall structure.Design one possible structure and Simplify the intended structureFabricate the structureImprove the resulting structureLiteral tableSymbol tableError handlerAuxiliary components that interact with some phases2Lexical AnalysisLexical Analysis1.Define the tokens with

3、a Regular Expression2.Create the equivalent NFA3.Construct the equivalent DFA4.Minimizing the equivalent DFA4Example1.Please write a regular expression for all strings of as and bs which contain two consecutive as or bs.(a|b)*(aa|bb) (a|b)*5nConvert the regular express into NFA4f35621iaaaabbbb62.Con

4、vert the NFA into DFA by subset construction. The Transition table is required.i，1，2IaIb1，2，31，2，31，2，41，2，41, 2, 3, 5, 6, f1, 2, 3, 5, 6, f1, 2, 3, 5, 6, f1, 2, 3, 6, f1, 2, 3, 6, f1, 2, 4, 5, 6, f1, 2, 4, 6, f1, 2, 4, 5, 6, f1, 2, 4, 5, 6, f1, 2, 4, 6, fS1，2，3A1，2，4B1, 2, 3, 5, 6, fC1, 2, 4, 5, 6,

5、 fD1, 2, 4, 6, fE1, 2, 3, 6, fFACACFFCBBDEDDE4f35621iaaaabbbb7SbAaaCaaBbbDbEbbabFaFa83.Minimizing the Number of States in a DFAaCDBAEFSbaaaaabbbbbabF1. Split into accepting states sets and Nonaccepting states setsS,A,B C,D,E,F2. Continue to split a: S,A,B=S,B AC,D,E,F = C,D,E,F b: S,B A=S A BC,D,E,F

6、 = C,D,E,F 3. Let D represents C,D,E,F Minimized DFA P=S,A,B,DDBASaaabbbba9Context-Free Grammars and ParsingProf. CHEN JSouth China University of TechnologyContext-Free Grammars and ParsingnThe Parsing ProcessnContext-Free GrammarsnParse Trees and Abstract Syntax TreenAmbiguity1112Context-Free Gramm

7、arsnFunctionqA context-free grammar is a specification for the syntactic structure of a programming languageqIt is similar to regular expressions except that a context-free grammar involves recursive rules.nExamplecontext-free grammar for integer arithmetic expressionexpexp op exp | (exp) | numberop

8、+ | - | *Example of Parsing Processexp exp op exp | (exp) | numop + | - | *na derivation for (34-3)*42 is:(1) exp=exp op exp(expexp op exp)(2) =exp op num(expnum)(3) =exp * num(op*)(4) =(exp) * num(exp(exp)(5) =(exp op exp) * num(expexp op exp)(6) =(exp op num) * num (expnum)(7) =(exp-num) * num (op

9、-)(8) =(num-num) * num (expnum)13Example (leftmost)expexp op exp | (exp) | numop + | - | *vThe leftmost derivation of “num+num” is:exp=exp op exp=num op exp =num + exp=num+num1exp2exp4exp3opnumnum+1415Example (rightmost)expexp op exp | (exp) | numop + | - | *vThe rightmost derivation of “num+num” is

10、:exp=exp op exp= exp op num = exp + num =num+num1exp2exp4exp3opnumnum+1. Leftmost and rightmost derivation are unique for the string they construct2. They are uniquely associated with the parse treeAbstract Syntax TreesnThe need of abstract syntax treeqA parse tree contains much more information tha

11、n is absolutely necessary for a compiler to produce executable codenExample:expexpexpopnum(3)+num(4)+34Abstract syntax tree16ExamplenThe parse tree and abstract syntax tree for expression (34-3)*4217AmbiguitynIn general ,a string of tokens has one parse tree, which corresponds to more than one deriv

12、ations of the stringnthe derivation of “” and the parse treeEET+TFTiiiE=E+TE=E+T =E+TF =T+TF=T+T=T+TF=i+ii=i+ii18It is possible for some grammars to permit a string to have more than one parse tree (or leftmost/rightmost derivation). For Example:nInteger arithmetic grammar: nString “” has two differ

13、ent parse trees:Corresponding to two leftmost derivations:1：E E+E EE+E iE+E ii+E ii+i2：E EE iE iE+E ii+E ii+iiEE+EEEiiEEEiEE+ii1920AmbiguitynA grammar G is ambiguous if there exists a string w L(G) such that w has two distinct parse trees (or leftmost /rightmost derivations)Top-Down ParsingProf. CHE

14、N JSouth China University of TechnologyTop-Down Parsing1.Non LL(1) grammar to LL(1) grammarqleft factor qleft recursion 2.Recognition of LL(1) GrammarqFirst SetsqFollow Sets3.LL(1) Parsing22Step 1: Determine whether the grammar is LL(1)G:EE+TTTT*FFF(E)iExample: LL(1) Parsing qThe grammar has left re

15、cursion, so it is not LL(1) grammar. Consider left recursion removal.qAfter left recursion removal getting G: ETE E+TE TFT T*FTF(E)i23Computer First and Follow Sets for each nonterminal nullableFirstFollowEno(,i),$Eyes+| ),$Tno(,i+,),$Tyes*| +,),$Fno(|i*,+,),$G: ETE E+TE TFT T*FTF(E)iG is a LL(1) gr

16、ammarStep 2: Determine whether G is LL(1)24Step 3: Construct the parsing tablenullableFirstFollowEno(,i ), $ Eyes+| ), $ Tno(,i +, ), $ Tyes*| +, ), $Fno(|i *, + , ), $G: ETE E+TE TFT T*FT F(E)i i+*()$E E T T F TETE+TEFTFTi*FT(E)25stepstacktopinputremainerMX,b12345678910111213Parsing process of stri

17、ng $i+i$ i+*()$ETE TE E +TE TFT FT T *FT Fi (E) $E$ET$ETF$ETi$ET $E $ET+$ET $ETF$ETi$ET $E $ETFiT E +T FiT E $iiii+ +i ii$ $ $+i$+i$+i$+i$i$ i$i$ $ETETFTF iT E +TET FTF iE T Step 4: LL(1) parsing26Bottom-Up ParsingProf. CHEN JSouth China University of TechnologyExampleG: (0) SS(1) SrD(2) DD,i(3) Di1

18、. Construct the DFA of LR(0) items for this grammar2. Is this grammar the LR(0) or SLR(1) grammar ? Give your reason. If so, Construct the parsing table.3. Show the parsing stack and the action of the parser for the input string “r i,i”.28I0:S SS rDI1: S S SI2: S rDD D,iD irI4: D i iI3: S rD D D ,iD

19、I5: D D,i,I6: D D,i i1.292. 1.In state I3, SrD is a complete item, DD,i is a shift item, there is shift-reduce conflict, so G is not LR(0) grammar. 2.Eliminating Conflicts I0:S SS rDI1: S S SI2: S rDD D,iD irI4: D i iI3: S rD D D ,iDI5: D D,i,I6: D D,i iFOLLOWS$S$D$ ,For state I3nIf the next token i

20、s $, then reducenIf the next token is , , then shiftConflict can be solvedG: (0) SS(1) SrD(2) DD,i(3) Di303. Construction of SLR(1) Parse TableACTION GOTO r,i$SD0123456S21accS43S5r1r3r3S6r2r2FOLLOW$ ,G: (0) SS(1) SrD(2) DD,i(3) Di31Parsing “r i,i”ACTION GOTO r,i$SD0S2 1 1 acc2 S4 33S5 r14r3 r35 S6 6

21、 r2 r2StackInputACTIONGOTO12345678$0ri,i$S2$0r2i,i$S4$0r2i4,i$r3$0r2D3,i$S5$0r2D3,5i$S6$0r2D3,5i6r23$0r2D3r11$0S1$acc$3G: (0) SS(1) SrD(2) DD,i(3) Di321.Right Sentential Form2.Viable Prefix3.HandleParsing “abbcde”reduce AAbcde$aAb5shiftcde$aA6shiftbcde$aA4reduce Abbcde$ab3shiftbbcde$a2shiftabbcde$1A

22、ctionInputStackS aAcBe A b A Ab B d331.Right Sentential Form2.Viable Prefix3.HandleParsing “abbcde”reduce AAbcde$aAb5shiftcde$aA6shiftbcde$aA4reduce Abbcde$ab3shiftbbcde$a2shiftabbcde$1ActionInputStackS aAcBe A b A Ab B dare all viable prefix of aAcde341.Right Sentential Form2.Viable Prefix3.HandleP

23、arsing “abbcde”reduce AAbcde$aAb5shiftcde$aA6shiftbcde$aA4reduce Abbcde$ab3shiftbbcde$a2shiftabbcde$1ActionInputStackS aAcBe A b A Ab B dn“b” is the handle of “abbcde”n“Ab” is the handle of “aAbcde”35Semantic AnalysisProf. CHEN JSouth China University of Technology37Consider the following grammar fo

24、r simple integer arithmetic expressions:exp exp + term | exp-term | termterm term*factor | factorfactor (exp)| number The principal attribute of an exp (or term or factor) is its numeric value (write as val) and the attribute equations for the val attribute are given as followsGrammar RuleSemantic R

25、ulesexp1exp2+termexp1.val=exp2.val+term.valexp1exp2-termexp1.val=exp2.val-erm.valexp1 termexp1.val= term.valterm1term2*factorterm1.val=term2.val*factor.val termfactorterm.val=factor.val factor(exp)factor.val=exp.val factornumberfactor.val=number.valTable 6.2Given the expression (34-3)*42 , the compu

26、tations implied by this attribute grammar by attaching equations to nodes in a parse tree is as followsexp(val = 1302)term(val = 31*42=1302)term(val = 31)factor(val = 42)( exp ) (val = 34-3=31)exp(val = 34)term(val = 3)factor(val = 31)number(val = 42)term(val = 34)factor(val =3)factor(val = 34)number(val = 3)number(val = 34)-*Dependency graphs and evaluation order38Code GenerationProf. CHEN JSouth China University of Technology40Instructions of three-address codenThree-address code for each construction of a standard programming la