課件，編譯原理，編譯原理課件，屬性文法，語法制導(dǎo)，2005課件說明，lrreview-資料下載頁
2025-05-01 23:12本頁面
【導(dǎo)讀】top-downmethods,butnotsurprisingly,theconstructions. specification.ofthebottom-uptechniques.derivation)areefficient,tabledrivenshift-reduceparsers.The. LRtechniques.ortoreportanerror.thosetables.forG'.a)IfA–>u?input.(AnotequaltoS').b)IfS'–>S?c)IfA–>u?avisinIiandGO(Ii,a)=Ij,thensetaction[i,a]toshift. j(aisaterminal).containingS'–>?S.u?inthatset.in
【正文】 l retains some of the power of the LR(1) lookaheads. LALR table construction The “bruteforce” method 1. Construct all canonical LR(1) states. 2. 2. Merge those states that are identical if the lookaheads are ignored, . two states being merged must have the same number of items and the items have the same core (. the same productions, differing only in lookahead). The lookahead on merged items is the union of the lookahead from the states being merged. 3. The GO function for the new LALR(1) state is the union of the GO function of the merged states. If the two configurations have the same core, then the original successors must have the same core as well, and thus the new state has the same successors. 4. The action and goto entries are constructed from the LALR(1) states as for the canonical LR(1) parser. Relationships between LL(1) and the various LR(1) grammars Note this diagram refers to grammars, not languages, . there may be an equivalent LR(1) grammar that accepts the same language as a given nonLR(1) grammar. No ambiguous grammar is LL(1) or LR(1), so we must either rewrite the grammar to remove the ambiguity or resolve conflicts in the parser table or implementation. The hierarchy of LR variants is clear: every LR(0) grammar is SLR(1) and thus LALR(1) which in turn is LR(1). There are grammars that don’t meet the requirements for the weaker forms that can be parsed by the more powerful variations. We’ve seen several examples of grammars that are not LL(1) that are LR(1). A not immediately obvious fact is that every LL(1) grammar is LR(1). Proving this rigorously is a little tricky, but your intuition should tell you that an LR(1) parser uses more information the LL(1) parser Parsing miscellany A different way of resolving ambiguity Ambiguity in a grammar means we have two or more leftmost derivations for the same input string, or equivalently, that we can build more than one parse trees for the same input string. Common examples: E – E + E | E * E | (E) | id S – iSeS | iS | a rewriting the grammar to introduce new intermediate nonterminals that force the precedence that we desired. to build an SLR(1) table for this grammar. 3. try to build an LL(1) table for this grammar
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1