编译原理教学课件：Chapter 5 - Bottom-Up Parsing

资源描述

《编译原理教学课件：Chapter 5 - Bottom-Up Parsing》由会员分享，可在线阅读，更多相关《编译原理教学课件：Chapter 5 - Bottom-Up Parsing（124页珍藏版）》请在金锄头文库上搜索。

2、” is not a right sentential formnEach right sentential form is split between the parsing stack and the inputreduceAAbcde$aAb5shiftcde$aA6shiftbcde$aA4reduceAbbcde$ab3shiftbbcde$a2shiftabbcde$1ActionInputStack2024/7/3018nRight sentential form and shift-reduce parsingqA shift-reduce parser will shift

3、terminals from the input to the stack until it is possible to perform a reduction to obtain the next right sentential form2024/7/30192) Viable PrefixnDefinitionThe sequence of symbols on the parsing stack is called a viableprefixviableprefix of the right sentential formreduceBde$aAcd8shiftde$aAc7shi

4、ftcde$aA6ActionInputStack“aAcde”isarightsententialform,itissplitbetweentheparsingstackandtheinputinstep6,7and8aA,aAc,aAcdaA,aAc,aAcdareallviable prefixofaAcdeAs long as the content of the parsing stack is a viable prefix of a right sentential form, the shift-reduce parsing is correct2024/7/30203) Ha

5、ndlenHandle of the right sentential formqThe string matches the right-hand side of the production that is used in the next reductionqTogether with the position in the right sentential form where it occursqAnd the production used to reduce it nFor exampleIn the right sentential form “abbcde”, the han

6、dle is the string consisting of the leftmost “b”, together with the production A b 2024/7/3021Handle and shift-reduce parsing1.Determining the next handle in a parse is the main task of a shift-reduce parser2.When the next handle is on the top of the stack, action “reduce ” is taken3.When the next h

7、andle has not formed on the top of the stack, action “shift” is takenreduceSaAcBe$aAcBe10accept$S11shifte$aAcB9reduceBde$aAcd8shiftde$aAc7reduceAAbcde$aAb5shiftcde$aA6shiftbcde$aA4reduceAbbcde$ab3shiftbbcde$a2shiftabbcde$1ActionInputStackn“b” is the handle of “abbcde”n“Ab” is the handle of “aAbcde”n

8、“d” is the handle of “aAcde”n“aAcBe” is the handle of “aAcBe”2024/7/3023nIn many cases the leftmost substring that matches the right side of some production A is not a handle, because a reduction by the production A yields a string that is not a right sentential formnFor exampleScAdAabAa(1)cabd|-cAd

9、|-S “ab” is the handle of “cabd”(2)cabd|-cAbd “a” is not the handle of “cabd”2024/7/3024Formal Definition of HandlenA handle of a right-sentential form is a production A and a position of where the string may be found and replaced by A to produce the previous right-sentential form in a rightmost der

10、ivation of 2024/7/3025nThat is, if S=* A= , then in the position following and A is a handle of , to the right of the handle contains only terminal symbolsnThere are three conditions for a handle:q is a right-sentential formqS =* AqA is a productionnUsually we say “the substring is a handle of ” for

11、 shortRRR2024/7/3026ExampleGE:EE + T | TTT * F | FF(E) | idThe rightmost derivation of “T*F+id” isE=E+T=E+F=E+id=T+id=T*F+idso “T*F” is the handle of “T*F+id”2024/7/3027nHandle in the parse tree of a right-sentential form SAHandle is the leaves of the leftmost subtree which consisting of a node and

12、its children2024/7/3028Examplen“T*F”istheleavesoftheleftmostcompletesubtreeconsistingofanodeanditschildrennso“T*F”isthehandleofT*F+idGE: EE+T|TTT*F|FF(E)|idEET+TTF*FidThe parse tree of “T*F+id”2024/7/3029Viable Prefix and HandlenA viable prefix is that it is a prefix of a right-sentential form that

13、does not continue past the right end of the handle of that sentential formnExampleRight sentential form aAcde (where d is handle)Viable prefixes are: a, aA, aAc, aAcd2024/7/3030Characters of Bottom-Up Parse taking a view of implementationnParser keeps putting viable prefixes in the stacknUntil handl

14、e is on the top of the stack, reduction is to take placenAs long as the content of the stack is a viable prefix, paring is correctreduceSaAcBe$aAcBe10accept$S11shifte$aAcB9reduceBde$aAcd8shiftde$aAc7reduceAAbcde$aAb5shiftcde$aA6shiftbcde$aA4reduceAbbcde$ab3shiftbbcde$a2shiftabbcde$1ActionInputStackn

15、Parser keeps putting viable prefixes in the stacknUntil handle is on the top of the stack, reduction is to take place2024/7/3032Characters of Bottom-Up Parse in generalnBottom-up parse is in general more powerful than top-down parse, it can be used to parse virtually all programming languagenThe con

16、structions involved in this parse are also more complex. Indeed, all of the important bottom-up methods are really too complex for hand coding2024/7/30335.2 Overview of LR Parsing MethodnThere are many Bottom-Up parsing methods, we will only talk about LR parsing methodnIn LR Parsing we will talk ab

17、outqLR(0) parsingqSLR(1) parsingqLALR(1) parsingqLR(1) parsing2024/7/30341. LR(K) ParsingnBasing on the string on top of the parsing stack (represent as state) and using the next K (K0) tokens in the input as lookahead to determine handle for reductionnThe Meaning of “LR(K)”qqL L indicates that the

18、input is processed from left to rightqqR R indicates that a rightmost derivation is producedqqK K for the number of input symbols of lookahead that are used in making parsing decision2024/7/3035A consequence of the power of LR(k) parsingnLR(0) parsing, where no lookahead is consulted in making parsi

19、ng decisionsnSLR(1) parsing (simple LR(1) is an improvement on LR(0)nLALR(1) parsing (lookahead LR(1) is slightly more powerful than SLR(1) but less complex than general LR(1)nLR(1) parsing is the most powerful and most complex2024/7/30362. Schematic Form of LR parser2024/7/30371)Input:The parsing p

20、rogram reads Tokens from the input buffer one at a time2)StackStore “$S0X1S1XmSm”, where Xi is a grammar symbol and Si is a state it summarizes the information contained in the stack below it. New state number is pushed onto the parsing stack after each push of a symbol3)Parsingtable that has two pa

21、rts (action and goto)It changes from one parser to another4)LRParsingProgramIt is the same for all LR parsers. The combination of the state on top of the stack and the current input token are used to index the parsing table and determine the shift-reduce parsing decision2024/7/30383. Parsing TablenE

22、ach line represents a state, each column is a grammar symboln nGOTOGOTO: take a state and a grammar symbol, determine the next staten nACTIONACTION: take a state and a grammar symbol, determine the next action to take placeACTIONGOTOacebd$acebd$ S A B0S211acc2SS133r2r2r2r2r2r22024/7/3039To save spac

23、e, compress ACTION and GOTO on columns of terminalsACTIONGOTOacebd$SAB0S211acc2S1S33r2r2r2r2r2r22024/7/3040ACTION TablenThe table entry (actionSm,ai) for state Sm and input ai has four values:1.Shift(Sk)Put symbol ai and state K into the stack2.Reduction(rk)Reduce by number k production (A),the acti

24、on includes:a)Pop the string and all of its corresponding states from the stack. Suppose currently the top of stack is state Sib)Push A onto stackc)Push the state Sj =GOTOSi,A onto stack3.Accept Indicate that parsing is complete successfully4.ErrorIndicate that parsing has discovered an errorACTIONG

25、OTOacebd$SAB0S211acc2S1S33r2r2r2r2r2r22024/7/3041Example of LR Parsing (SLR(1)GS：(1)S aAcBe (2)A b(3)A Ab(4)B dACTIONGOTOacebd$SAB0S211acc2S433S5S64r2r25S876r3r37S98r49r1ParsingPlease take a photo of this slide for further use.LR parsing process of “abbcde$”1733Gotoacc$011R1$0a2A3c5B7e910S9e$0a2A3c5

26、9R4e$0a2A3c5d88S8de$0a2A3c57S5cde$0a26R3cde$0a2A3b65S6bcde$0a24R2bcde$0a2b43S4bbcde$0a22S2abbcde$01ActionInputStackA33A7B1S2024/7/3043Summarization of LR parsing method nParsing Program is the same for all LR parsers, only parsing table changes from one parser to another nHow can we construct a pars

27、ing table for different grammars and different parsers? This is the key of LR parser2024/7/30445.3 Finite Automata of LR(0) Items and LR(0) ParsingnLR(0) ParsingqThe LR parser using LR(0) parsing table is LR(0) parser; The grammar for which an LR(0) parser can be constructed is said to be LR(0) gram

28、marqLR(0) parser uses only the content of stack to determine handle, it doesnt need input token as lookaheadqAlmost all “real” grammars are not LR(0), but LR(0) method is a good starting point for studying LR parsing2024/7/3045n5.3.1 LR(0) Itemsn5.3.2 Finite Automata of Itemsn5.3.3 Constructing LR(0

29、) Parsing Tablen5.3.4 The LR(0) Parsing Algorithm2024/7/30465.3.1 LR(0) ItemsnLR(0) ItemqAn LR(0) item of a grammar G is a production of G with a distinguished position in its right-hand sideqFor example,production UXYZ has four items 0 U XYZ1 UX YZ 2 UXY Z3 UXYZ production Ahas only one item AqThes

30、e are called LR(0) items because they contain no explicit reference to lookahead2024/7/3047nWhy do we need to construct items?qHandle is the right hand side of a productionqThe rightmost position of the handle string is on the top of the stack when reduction takes placeqThus ,it seems plausible that

31、 parser determines its actions based on positions in right hand sides of productionsqWhen these positions reach the right-hand end of a production, then this production is a candidate for a reduction, and it is possible that the handle is at the top of the stack2024/7/3048The Meaning of ItemsAn item

32、 records an intermediate step in the recognition of the right-hand side of a productionnA means that we may be about to recognize an A by using production A nA means that has already been seen ( must appear at the top of stack) and that it may be possible to derive the next input token from nA means

33、 that now resides on the top of the stack and may be the handle, if A is to be used for the next reduction2024/7/3049Categories of ItemsnInitial ItemItem of the form A , means the initial of recognizing nComplete ItemItem of the form A , means the completeness of recognizing 2024/7/30505.3.2 Finite

34、Automata of ItemsnThe LR(0) items can be used as the states of a finite automaton that maintains information about the parsing stack and the progress of a shift-reduce parse1.Construct NFA of Items2.Construct DFA of Sets of Items Directly3.LR(0) Parsing with DFA2024/7/30511. Construct NFA of ItemsTr

35、ansitions of NFAConsider item i: A Xand item j：A X, there is a transition on symbol X from i to jA X A X X2024/7/3052nIf X is a tokenqThis transition corresponds to a shift of X from the input to the top of the stack during a parsenIf XVNqThis transition corresponds to the pushing of X onto the stac

36、kqBut X will never appear as an input symbol, this can only occur during a reduction by a production XqSo for each production choice X of X, we must add an -transition to XA X X 2024/7/3053Start State of NFAqAugment the grammar by a single production SS, where S is a new nonterminal, it becomes the

37、start symbol of the Augmented grammarSince start symbol S may appear in the right hand side of productions,t he purpose of augmenting is to indicate when the parser should stop parsing and announce acceptance of the inputqS S becomes the start state of the NFA2024/7/3054Accepting State of NFAqNFA is

38、 used to keep track of the state of a parse, not to recognize strings outrightqThus, the parser itself will decide when to accept, and the NFA has no accepting states at all2024/7/3055GS ：SEEaA|bBAcA|dBcB|dAll items of G: 1 S E 10. Ad 2 SE 11. E bB3 EaA 12. Eb B4 EaA13. EbB 5 EaA 14. B cB6 A cA15. B

39、c B7 Ac A16. BcB 8 AcA 17. B d9 A d 18. Bd 2024/7/3056 3 11a 4 1 6c 7 9TheNFAofitems该文法的项目有：1 S E10. Ad2 SE 11. E bB3 E aA12. Eb B4 Ea A13. EbB 5 EaA 14. B cB6 A cA15. Bc B7 Ac A16. BcB 8 AcA 17. B d9 A d18. Bd A 5 d10A8b 12 dB B 14 15 17c 18 1613E 2*2024/7/3057TheDFAofsetsofitems2024/7/3058nThis me

40、thod starts out as a NFA of items, from this NFA construct the DFA of sets of items using the subset construction nIt is complex, not utilitynIt is much easier to construct the DFA of sets of items directly2024/7/30592. Construct DFA of Sets of Items DirectlynThe Construction of DFAqEach state of DF

41、A is a set of itemsqHow to construct a state?-closure operationqHow to construct transition form one state to another?-goto operation2024/7/30601) The Closure OperationnIf I is a set of items for grammar G, then closure(I) is the set of items constructed from I by the two rules:a)Initially, each ite

42、m of I is added to closure(I)b)If A Bis in closure(I) and BVN , then for each production B , add the item B to closure(I), if it is not there.c)Repeat b) until no more new items are addednFor each item where is at the right end or followed by a terminal, closure of this item is the item itself2024/7

43、/3061if I= SE thenclosure(I)= SE, EaA, EbB GS ：SEEaA|bBAcA|dBcB|dMake ClearItem A Bin closure(I) indicates that ,at some point in the parsing process, the next seeing substring is derivable from B. If B , the next seeing substring is derivable from at this point. For this reason B is in closure(I)20

44、24/7/3062nDistinction of Items in the state of DFAqKernel itemsWhich include the S S and all items whose dots are not at the left end qClosure itemsWhich have their dots at the left end, they are added to the state during the closure operation2024/7/30632) The Goto OperationnI is a set of items,XVNV

45、T, goto(I,X)= closure(J) where J is the set of all items A X such that A X is in IExampleSE EaA | bBAcA|dBcB | d I = SE，EaA，EbB goto(I, E)=closure( SE)= SEgoto(I,a)= closure(EaA) =EaA,AaA,Ad goto(I, b)= closure( EbB ) = EbB,BcB,Bd 2024/7/30643) The Construction of DFAa)IS0=closure(SS) is the start s

46、tate of DFA,and it is unlabeledb)Get an unlabeled state ISi from DFAvLabel ISivFor each item U xRy(R VNVT,x and y are strings) of ISi, compute goto(ISi,R)=ISjvAdd ISj to DFA as unlabeled if it is not therevAdd a transition form ISi to ISj on Rc)Repeat b) until there is no unlabeled state in DFA2024/

47、7/3065GS ：SEEaA|bBAcA|dBcB|dAll items of G: 1 S E 10. Ad 2 SE 11. E bB3 EaA 12. Eb B4 EaA13. EbB 5 EaA 14. B cB6 A cA15. Bc B7 Ac A16. BcB 8 AcA 17. B d9 A d 18. Bd 2024/7/3066BcBcAcAcSEEaAEbBAcAAdBcBBdBcBBdAcAAdEaAaSEEEbBbccAcAAdAddEaAAdBddEbBBBcBBTheconstructionofDFAGS ：SEEaA|bBAcA|dBcB|d2024/7/30

48、673. LR(0) Parsing with DFAnLR(0) parsing algorithm depends on keeping track of the current state in the DFA of sets of itemsnWe do this by pushing the new state number onto the parsing stack after each push of a symbolnLet s be the current state (at the top of the parsing stack). Then actions are d

49、efined as follows:2024/7/30681.If state s contains any item of the form AX, where X VTqThen the action is to shift the current input token onto the stack.qIf this token is X, then the new state to be pushed on the stack is the state containing the item A XqIf this token is not X, an error is declare

50、d2.If state s contains S S, where S is the start symbolqThen the action is to accept, provide the input token is $qAnd error if the input is not $2024/7/30693.If state s contains any complete items (A )qThen the action is to reduce by the rule AqThe new state is computed as follows.nRemove the strin

51、g and all of its corresponding states from the stack.nCorrespondingly, back up in the DFA to the state from which the construction of began, this state must contain an item of the form B A nPush A onto the stack, and push the state containing the item B A 2024/7/3070StepStackInputAction 1） $ abbcde$

52、 shift 0 S2 2） $a bbcde$ shift 02 S4 4） $aA bcde$ shift 023 S6 6） $aA cde$ shift 023 S5 7） $aAc de$ shift 0235 S8 9） $aAcB e$ shift 02357 S911） $S $ accept 01 accLR parsing for “abbcde$” 3） $ab bcde$ reduce(Ab) 024 r2 3 5） $aAb cde$ reduce(AAb) 0236 r3 3 8） $ aAcd e$ reduce(Bd) 02358 r4 710） $aAcBe

53、$ reduce(SaAcBe) 023579 r1 1StateACTIONGOTO014235769SabAbcBed8*识别文法活识别文法活前缀前缀DFA的的工作方式工作方式2024/7/3071StepStackInputAction 1） $ abbcde$ shift 0 S2StateACTIONGOTO014235769SabAbcBed8*LR parsing for “abbcde$”2024/7/3072StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 StateACTIONGOTO

54、014235769SabAbcBed8*LR parsing for “abbcde$”2024/7/3073StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 3） $ab bcde$ reduce(Ab) 024 r2 3StateACTIONGOTO014235769SabAbcBed8*LR parsing for “abbcde$”2024/7/3074StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 4）

55、$aA bcde$ shift 023 S6 3） $ab bcde$ reduce(Ab) 024 r2 3StateACTIONGOTO014235769SabAbcBed8*LR parsing for “abbcde$”2024/7/3075StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 4） $aA bcde$ shift 023 S6 3） $ab bcde$ reduce(Ab) 024 r2 3 5） $aAb cde$ reduce(AAb) 0236 r3 3StateACTIONG

56、OTO014235769SabAbcBed8*LR parsing for “abbcde$”2024/7/3076StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 4） $aA bcde$ shift 023 S6 6） $aA cde$ shift 023 S5 3） $ab bcde$ reduce(Ab) 024 r2 3 5） $aAb cde$ reduce(AAb) 0236 r3 3StateACTIONGOTO014235769SabAbcBed8*LR parsing for “abb

57、cde$”2024/7/3077StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 4） $aA bcde$ shift 023 S6 6） $aA cde$ shift 023 S5 7） $aAc de$ shift 0235 S8 3） $ab bcde$ reduce(Ab) 024 r2 3 5） $aAb cde$ reduce(AAb) 0236 r3 3StateACTIONGOTO014235769SabAbcBed8*LR parsing for “abbcde$”2024/7/3078

58、StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 4） $aA bcde$ shift 023 S6 6） $aA cde$ shift 023 S5 7） $aAc de$ shift 0235 S8 3） $ab bcde$ reduce(Ab) 024 r2 3 5） $aAb cde$ reduce(AAb) 0236 r3 3 8） $ aAcd e$ reduce(Bd) 02358 r4 7StateACTIONGOTO014235769SabAbcBed8*LR parsing for “

59、abbcde$”2024/7/3079StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 4） $aA bcde$ shift 023 S6 6） $aA cde$ shift 023 S5 7） $aAc de$ shift 0235 S8 9） $aAcB e$ shift 02357 S9 3） $ab bcde$ reduce(Ab) 024 r2 3 5） $aAb cde$ reduce(AAb) 0236 r3 3 8） $ aAcd e$ reduce(Bd) 02358 r4 7State

60、ACTIONGOTO014235769SabAbcBed8*LR parsing for “abbcde$”2024/7/3080StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 4） $aA bcde$ shift 023 S6 6） $aA cde$ shift 023 S5 7） $aAc de$ shift 0235 S8 9） $aAcB e$ shift 02357 S9 3） $ab bcde$ reduce(Ab) 024 r2 3 5） $aAb cde$ reduce(AAb) 023

61、6 r3 3 8） $ aAcd e$ reduce(Bd) 02358 r4 710） $aAcBe $ reduce(SaAcBe) 023579 r1 1StateACTIONGOTO014235769SabAbcBed8*LR parsing for “abbcde$”2024/7/3081StepStackInputAction 1） $ abbcde$ shift 0 S2 2） $a bbcde$ shift 02 S4 4） $aA bcde$ shift 023 S6 6） $aA cde$ shift 023 S5 7） $aAc de$ shift 0235 S8 9）

62、$aAcB e$ shift 02357 S911） $S $ accept 01 acc 3） $ab bcde$ reduce(Ab) 024 r2 3 5） $aAb cde$ reduce(AAb) 0236 r3 3 8） $ aAcd e$ reduce(Bd) 02358 r4 710） $aAcBe $ reduce(SaAcBe) 023579 r1 1StateACTIONGOTO014235769SabAbcBed8*Language(G): ab*cdeLR parsing for “abbcde$”2024/7/30825.3.3 Constructing LR(0)

63、 Parsing TablenLR(0) Parsing TableqACTION: LR(0) parsing does not consult input token, so LR(0) parsing states are either “shift” states or “reduce” statesqGOTO: There must be a column for every symbol(VN, VT and $ )ACTIONGOTOacebd$SAB0Shift211R12Shift133R22024/7/3083Construction of LR(0) Parsing Ta

64、bleGiven a grammar G, we augment G to produce G1.Construct DFA of sets of LR(0) items2.The ACTIONsection for state K is determined as follows:a)If A K, then ACTIONK=Shiftb)If A K, and the number of A is j, then set ACTIONK=Rj 3.The GOTOsection for state K is constructed for all symbols using the rul

65、e: If goto(K,X)=J, XVNVT$, then set GOTOK,X=J2024/7/3084G：(0) SE(1) EaA (2) EbB (3) AcA(4) Ad(5) BcB (6) Bd parsingtableLR(0)parsingtableDFAExampleACTIONGOTOabcd$EAB01234567891011S2.r1r2r3r5r4r6S3.r1r2r3r5r4r6. S4S5S4S5r1r2r3r5r4r6. S10S11S10S11r1r2r3r5r4r6.acc.r1r2r3r5r4r61.6.8.7 .9 SLR(1) parsing

66、table2024/7/30865.3.4 The LR(0) Parsing AlgorithmLet S be the current state (at the top of the parsing stack), actions are defined as follows:1)If ACTIONS=Shift, and a is the current input symbol then push symbol a and state j=GOTOS,a onto stack. If GOTOS,a is empty, an error occurs2024/7/30872)ACTI

67、ONS=RjnIf the rule numbered j is SS, where S is the start symbol, then the action is to acceptance, provided the input is “$”,and error if the input is not “$”nOtherwise the action is to reduce by the rule numbered j (A)qRemove the string and all of its corresponding states from the stack, suppose c

68、urrently the top of stack is state KqPush A onto stackqPush the state i= GOTOK,A onto stackG：(0) SE(1) EaA (2) EbB (3) AcA(4) Ad(5) BcB (6) Bd StackInputACTIONGOTO12345678910LR(0) parsing of string “bccd$”$0bccd$S3$0b3ccd$S5$0b3c5cd$S5$0b3c5c5d$S11$0b3c5c5d11$R69$0b3c5c5B9$R59$0b3c5B9$R57$0b3B7$R21$

69、0E1$acceptParsingTable2024/7/30895.4 SLR(1) Parsing1.Conflict in the set of itemsnShift-Reduce ConflictIf a set contains shift item A a and complete item B, an ambiguity arises as to whether shift a or reduce to BnReduce-Reduce ConflictIf a set contains complete item A and B , an ambiguity arises as

70、 to which production to use for the reductionA grammar is LR(0) if and only if non of the set of items has shift-reduce conflict or reduce-reduce conflict. A a B A B 2024/7/3090ExamplenGrammarofrealvariabledeclarationreal,identifieridentifiernRewritetheG：(0)SS(1)SrD(2)DD,i(3)Di2024/7/3091Example G:

71、(0) SS(1) SrD(2) DD,i (3) DinIn state I3, SrD is a complete item, DD,i is a shift item, there is shift-reduce conflict, so G is not LR(0) grammarI0: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 i2024/7/30922. Eliminating Conflicts in SLR(1)nThe Main Idea of SLR(1)(Sim

72、ple LR(1)qSLR(1) parsing is a simple, effective extension of LR(0)qIt uses the DFA of sets of LR(0) items.qIncreases the power of LR(0) parsing by using the next token in the input string to direct its actionsqThe simple use of lookahead is powerful enough to parse almost all practical language2024/

73、7/3093nTwo ways of using the lookahead token :qIt consults the input token before a shift to make sure that an appropriate DFA transition existsqIt uses the Follow set of a nonterminal to decide if a reduction should be preformed. For item A , reduction only takes place when the next token aFOLLOW(A

74、)2024/7/3094Example G: (0) SS(1) SrD(2) DD,i (3) DiI0: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$ ,ForstateI3nIfthenexttokenis$,thenreducenIfthenexttokenis,thenshiftConflictcanbesolved2024/7/3095Eliminating Conflicts in SLR(1)nExampleI=X b A B, where

75、bVT，if FOLLOW(A) FOLLOW(B)= and not includes b, the action of I is based on the next input token aqIf a=b, then shiftqIf a FOLLOW(A), then reduce with A qIf a FOLLOW(B), then reduce with B qOtherwise, an error occurs X b A B 2024/7/3096nIngeneralIf state I has m shift items:A1 1a11, A2 2a2 2, , Am m

76、amm and n reduction items:B11 , B2 2 , , Bn n ,we have:a1，a2，am FOLLOW(B1) FOLLOW(B2) FOLLOW(Bn)=then the action of I is based on the next token aqIf a a1，a2，am, then shiftqIf a FOLLOW(Bi), i=1,2,n, then reduce with Bi i;qOtherwise, an error occursA grammar is SLR(1) if the application of lookahead

77、as above results in no ambiguity2024/7/30973. Construction of SLR(1) Parse TablenLR(0) Parsing TableACTIONGOTOacebd$SAB0S211acc2S1S33r2r22024/7/3098nConstructionofSLR(1)ParsingTableGiven a grammar G, we augment G to produce G 1.Construct DFA of sets of LR(0) items2.The ACTIONsection for state K is d

78、etermined as follows:a)If A aK, aVT, and goto(K,a)=J, then set ACTIONK,a=SJb)If A K, and the number of A is j, then set ACTIONK,a=Rj for each aFollow(A)c)If SSK, then set ACTIONK,$=acc3.The GOTOsection for state K is constructed for all nonterminals using the rule: If A BK, BVN, and goto(K,B)=J, the

79、n set GOTOK,B=J4.Empty entries not defined by rule 2 and 3 represent errors2024/7/3099Example G: (0) SS(1) SrD(2) DD,i (3) DiI0: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$,ACTIONGOTOr,i$SD0123456S21accS43S5r1r3r3S6r2r22024/7/301004. The SLR(1) Parsing

80、 AlgorithmLet S be the current state(at the top of the parsing stack), a be the current input symbol. Then actions are defined as follows:1)If ACTIONS,a=Sj, aVT, thenpush symbol a and state j onto stack2)If ACTIONS,a=Rj,a VT or $, then the action is to reduce by the rule numbered j(A)vRemove the str

81、ing and all of its corresponding states from the stack, suppose currently the top of stack is state KvPush A onto stackvPush the state j = GOTOK,A onto stack3)If ACTIONS,a=acc, parsing is completed successfully 4)If ACTIONS,a is empty, an error occursParsing “r i,i”ACTIONGOTOr,i$SD0S211acc2S433S5r14

82、r3r35S66r2r2StackInputACTIONGOTO12345678$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) Di2024/7/301025.5 General LR(1) and LALR(1) ParsingnThere are a few situations in which SLR(1) parsing is not quite powerful enoughnThis will lead

83、us to study the more powerful general LR(1) and LALR(1) parsing2024/7/30103G：(0)SS(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)AeI5:FOLLOW(A)c=c,dcI7:FOLLOW(A)d=c,ddThen,theconflictsinI5and I7cannotbesolvedbySLR(1)method.FOLLOW(A) = ? c,d2024/7/30104ObservationnS=S=aAd=aednS=SaAcThen,aAdisarightsententialformaAci

84、sNOTarightsententialform*G：(0)SS(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)Ae2024/7/30105ObservationnS=S=bAc=becnS=SbAdThen,bAcisarightsententialformbAdisNOTarightsententialform*G：(0)SS(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)Ae2024/7/30106nSLR(1) parsing uses Follow sets of nonterminals as lookahead. This eliminate some

85、 invalidate reduction in LR(0), some conflicts in a state may be removednFollow set of A includes all terminals that may follow A in all sentential form, but it is not the case that A may be followed by any terminal in Follow(A) in any sentential form including A, so SLR(1) cant eliminate all confli

86、cts2024/7/301075.5.1 Main Idea of General LR(1)nMainIdeaofGeneralLR(1)qInLR(1)parsing,lookaheadsarebuiltfordistinctsententialformsqForexampleAllsententialformsthatincludeAare: Aa, Ab, Ac,soFOLLOW(A)=a,b,c,nFor“ A”,reductiontoAoccursonlywhenthelookaheadisa;nFor“ A”,reductiontoAoccursonlywhenthelookah

87、eadisb;nFor“ A”,reductiontoAoccursonlywhenthelookaheadisc;2024/7/30108LR(1) ParsingnA LR(1) item is a pair consisting of a LR(0) item and a lookahead tokenA ,a where A is a LR(0) item and a is a lookahead tokennThe power of general LR(1) lies in :if AB,a is in state I, then B,b is also in I for ever

88、y production B and for every token b in FIRST(a) (replacing Follow(B) as lookahead for B in SLR(1), FIRST( a) is a subset of Follow(B)2024/7/30109I0:S S, $S aAd, $S bAc, $S aec, $S bed, $I1:S S , $I2:S a Ad, $S a ec, $A e, dI3:S b Ac, $S b ed, $A e, cI4:S aA d, $I5:S ae c, $A e , dI6:S bA c, $I7:S b

89、e d, $A e , cI8:S aAd , $I9:S aec , $I10:S bAc , $I11:S bed , $Why LR(1) can solve the conflict in I5 and I7?SabAeecAdcdG：(0) S S(1) S aAd (2) S bAc(3) S aec(4) S bed(5) A e2024/7/30110状态状态ACTIONGOTOabcde#SA01234567891011S2S3.S9S10r5.S8r5.S11.S5S7.acc.r1r3r2r41. 46LR(1) parsing tableG：(0) S S(1) S a

90、Ad (2) S bAc(3) S aec(4) S bed(5) A eI5:S ae c, $A e , dI7:S be d, $A e , c2024/7/30111Characters of LR(1) parsingnLookaheads are precise in LR(1) parsing, it overcomes the problem with SLR(1) , eliminates all invalidate reductionsnBut at a cost of substantially increased complexity. General LR(1) p

91、arsing is usually considered too complex to use in the construction of parsers in most situations2024/7/301125.5.2 Main Idea of LALR(1)nLALR(1)(“lookahead” LR parsing)LALR(1) retains some of the benefit of general LR(1) parsing over SLR(1) parsing, while preserving the smaller size of the DFA of LR(

92、0) items2024/7/30113LALR(1) parsingnThe core of a state of the DFA of LR(1) items is the set of LR(0) itemsnLALR(1) parsing identifies all the states that have the same core and combines their lookaheadsnIn doing so, we end up with a DFA which size is identical to the DFA of LR(0) itemsnIf there is

93、no conflict in any state of DFA after combining, then it is the DFA of LALR(1)2024/7/30114G：(0) S S(1) B aB (2) S BB(3) B bI0:S S, $S BB, $B aB, a/bB b, a/bI1:S S , $I2:S B B, $B a B, $B b, $I5:S B B , $I6:B a B, $B aB, $B b, $I9:B a B , $I4:B b , a/bI3:B a B, a/bB aB, a/bB b, a/bI8:B a B , a/bI7:B

94、b , $SBbbBbbaaaaBBTheDFAofLR(1)items2024/7/30115I3andI6,I4andI7,I8andI9arestateswiththesamecoreI3:B a B, a/bB aB, a/bB b, a/bI6:B a B, $B aB, $B b, $I4:B b , a/bI7:B b , $I8:B a B , a/bI9:B a B , $I3,6:B a B, a/b/$B aB, a/b/$B b, a/b/$combiningI4,7:B b , a/b/$combiningI8,9:B a B , a/b/$combiningTher

95、eisnoconflictaftercombining,soitistheDFAofLALR(1)2024/7/301165.6 Error Recovery in Bottom-up ParsersnDetecting Errors in Bottom-up ParsingA bottom-up parser will detect an error when a blank entry is detected in the parsing tableqAn LR(1) parser can detect errors earlier than LALR(1) or SLR(1) parse

96、r.qAnd these latter can detect errors earlier than an LR(0) parser.2024/7/30117combiningLR(1) parsing table LALR(1) parsing table G：(0) S S(1) B aB (2) S BB(3) B b2024/7/30118STATEINPUTACTIONGOTO123$0$0a3$0a3b4ab$.b$.$.S3S4出错出错 LR(1) Parsing “ab$”LR(1) parsing table G：(0) S S(1) B aB (2) S BB(3) B b

97、2024/7/30119STATEINPUTACTIONGOTO12345$0$0a(3,6)$0a(3,6)b(4,7)$0a(3,6)B(8,9)$0B2ab$.b$.$.$.$.S3,6S4,7r3r2出错出错(8,9)2LALR(1) parsing table LALR(1) Parsing “ab$”G：(0) S S(1) B aB (2) S BB(3) B b总结：LR(0),SLR(1),LR(1),LR(k),LALR(1)LR(0)SLR(1): 生成的LR(0)项目集如有冲突，则根据非终结符的FOLLOW集决定LR(1)、LR(k): 项由心与向前搜索符组成，搜索符

98、长度为1或kLALR(1): 对LR(1)项目集规范族合并同心集1202024/7/301215.6 Error Recovery in Bottom-up ParsersnDetecting Errors in Bottom-up ParsingnPanic Mode Error RecoveryRemove symbols from either the parsing stack or the input or both. There are three possible alternative actions:1.Pop states from the parsing stack un

99、til a state is found with nonempty goto entries2024/7/301222.If there is a legal action on the current input token from one of the goto states, push that state onto the stack and restart the parse.nIf there are several such states, prefer a shift to a reduce.nAmong the reduce actions, prefer one who

100、se associated nonterminal is least general3.If there is no legal action on the current input token from one of the goto states, advance the input until there is a legal action or the end of the input reachedExample:LRparsingofstring“(2+*)”ACTIONGOTOnum(+-*)$ETF4r6r6r6r6r6r6r67S5S61149S5S61311r2r2r2r

101、2S9 r2r213r5r5r5r5r5r5r5reduceTT*F)$0(6E10+7T11*9F13error;pushF,goto13)$0(6E10+7T11*9S9*)$0(6E10+7T11error;pushT,goto11*)$0(6E10+7ActionInputParsingstack2024/7/30124AssignmentConsiderthefollowinggrammar:E-(L)|aL-L,E|E1.ConstructtheDFAofLR(0)itemsforthisgrammar2.ConstructtheSLR(1)parsingtable3.ShowtheparsingstackandtheactionsofanSLR(1)parserfortheinputstring(a),a,(a,a)4.IsthisgrammaranLR(0)grammar?Ifnot,describetheLR(0)conflict.Ifso,constructtheLR(0)parsingtable,anddescribehowaparsemightdifferfromanSLR(1)parse.

展开阅读全文

编译原理教学课件：Chapter 5 - Bottom-Up Parsing

最新文档