《(4.5.1)--3.5.1ReductionsandHandle-.pdf》由会员分享，可在线阅读，更多相关《(4.5.1)--3.5.1ReductionsandHandle-.pdf（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Compilers TechniquesSyntaxA n a l y s i sReviewContext-free grammarsTop-downBottom-upLL(1)grammarsTwo functionsRecursive-descent prediction parsingNonrecursive predictive parsingLeftmost derivationsRightmost derivations!Top-down Parsing corresponds to the process of constructing a syntax tree using
2、leftmost derivationE lmTE lmFT E lmid T E lm id*F T E lmid*id T E lmid*id E lmid*idETE E +TE|TFT T *FT|F(E)|idinput：id*idETE id*T Fid FT Leftmost Derivations and Top-down ParsingCan the rightmost derivation be used for top-down parsing?E lmTE lmFT E lmid T E lm id*F T E lmid*id T E lmid*id E lmid*id
3、ETE E +TE|TFT T *FT|F(E)|idinput：id*idETE id*T Fid FT Read the input string from left to right,but do the rightmost derivations.Its difficult to use the character on the left to decide the expansion ofnon-terminal on the right.Rightmost derivations:not suitable for top-down parsing tree construction
4、Leftmost Derivations and Top-down ParsingStarting from the given sentence,hope to turn sentences into start symbols Rightmost derivations,used for bottom-up parsingNext part Bottom-up parsing,corresponds to the inverse process of rightmost derivationsIntroducing the concept of reductions Reduction i
5、s an inverse process of derivation.Eid+id*idBottom-Up ParsingImportantConceptReductionsHandle PruningOverview of Bottom-Up ParsingReducting:an important action in bottom-up parsingS aABeA Abc|bB dReductions correspond to the inverse process of the rightmost derivationsabbcdeaAbcdeaAdeaABeSrmrmrmrmGr
6、ammar：a b b c d eAABSReductionsReductione.g.S aABeA Abc|bB dabbcdeaAbcdeeabbdcAabbcdeaAbcde rmBottom-Up ParsingReductione.g.S aABeA Abc|bB dabbcdeaAbcdeaAdeeabbdcAAabbcdeaAde rmaAbcde rmBottom-Up ParsingReductione.g.S aABeA Abc|bB dabbcdeaAbcdeaAdeaABeeabbdcAABabbcdeaABe rmaAde rmaAbcde rmBottom-Up
7、ParsingReductione.g.S aABeA Abc|bB dabbcdeaAbcdeaAdeaABeSeabbdcabbcdeAABSSrmaABe rmaAde rmaAbcde rmBottom-Up ParsingHandle:A substring that matches the right of a productionS aABeA Abc|bB dS rmaABe rmaAde rmaAbcde rmabbcde A handle is a substring of a right-sentential form.Reducing the handle to a n
8、on-terminal represents one step along the reverse of a rightmost derivation.Bottom-Up ParsingProperties of handlese.g.E E+E|E*E|(E)|idE rmE*EE rmE+ErmE*E+ErmE+id3rmE*E+id3rmE*E+id3rmE*id2+id3rmE*id2+id3rmid1*id2+id3rmid1*id2+id3In the pattern E*E+id3,the handle is not unique.S rmaABe rmaAde rmaAbcde
9、 rmabbcde The right side of the handle contains only the terminal If the grammar is ambiguous,the handle may not be uniqueBottom-Up ParsingInformal definition of handlesThe handle of a sentential form is the string that matches the right of a production in the sentential form.Grammar:S aABeA Abc|bB
10、dWhat are the possible handles in the rightmost derivation?aABeAbcbdHandlesHandlesPrecise definition of handle The handle of the right-sentential form is the right part of a production.After replacing handle in with a,the former sentential form in rightmost derivation is obtained Let =,can be reduce
11、d to sentential form A through production form A-abbcdeaAbcde rmaAAcde rmaAAcdeis not the grammars right patternIs ba handle?So bis not a handle of aAbcdeIf bis a handle,this step of derivation exists.Grammar:S aABe A Abc|bB dAll the sentential formsthat appear in the rightmost derivations are calle
12、d right-sententialformsS*X is the handle of X In the shift-reduce parsing,the handle always appears at the top of the stack.Bottom-up parsing is based on identifying handles.Handlese.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmr
13、mrmrmBottom-Up Parsingabbcdee.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmBottom-Up Parsingabbcdee.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmB
14、ottom-Up Parsingbabcdee.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmBottom-Up ParsingAabcdee.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmBottom-
15、Up ParsingbAacdee.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmBottom-Up ParsingAacdee.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmBottom-Up Pars
16、ingcAadee.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmBottom-Up ParsingdcAaee.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmBottom-Up ParsingBcAae
17、e.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmBottom-Up ParsingeBcAae.g.Grammar G(S)：(1)S aAcBe(2)A b(3)A Ab(4)B dTry to carry out shift-reduce parsing on abbcdeabbcdeaAbcdeaAcdeaAcBeSrmrmrmrmBottom-Up ParsingSCompilers TechniquesSyntaxA n a l y s i s