課件，編譯原理，編譯原理課件，屬性文法，語法制導，2005課件說明，lrreview(參考版)
2025-05-06 23:12本頁面
【正文】 – ?S. A grammar is LR(1) if the following two conditions are satisfied for each configurating set: 1. For any item in the set [A – u?xv , a] with x a terminal, there is no item in the set of the form [B – u?, x] In the action table, this translates no shiftreduce conflict for any state.. 4. The lookaheads for all plete items within the set must be disjoint, . set cannot have both [A – u?, a] and [B – v ?, a] This translates to no reducereduce conflict on any state.. The motivation for LALR Because a canonical LR(1) parser splits states based on differing lookahead sets, it typically has many more states that the corresponding SLR(1) or LR(0) parser. Potentially it could require the Cartesian product of all possible LR(0) configurations and the power set of the never actually gets that bad in practice, but a canonical LR(1) parser for an ordinary programming language might have an order of magnitude more states than an SLR(1) parser. Is there something in between? With LALR (lookahead LR) parsing, we attempt to reduce the number of states in an LR(1) parser by merging similar states. This reduces the number of states to the same as SLR(1), but still 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 gram
教學課件相關推薦
鄂ICP備17016276號-1