課件編譯原理編譯原理課件屬性文法語法制導(dǎo)2005課件說明lrreview(文件)
【正文】 al a is the next input token. The possible actions are to shift a state onto the stack, to reduce the handle on top of the stack, to accept the input, or to report an error. 2. The goto table Goto[s,X] indicates the new state to place on top of the stack after a reduce of the nonterminal X while state s is on top of the stack. The two tables are usually bined, with the action table specifying entries for terminals, and the goto table specifying entries for nonterminals. Types of LR parsers There are three types of LR parsers: LR(k), simple LR(k), and lookahead LR(k) (abbreviated to LR(k), SLR(k), LALR(k)). The k identifies the number of tokens of lookahead. We will usually only concern ourselves with 0 or 1 tokens of lookahead, but it does generalize to k 1. The different classes of parsers all operate the same way (as shown above, being driven by their action and goto tables), but they differ in how their action and goto tables are constructed, and the size of those tables. Constructing LR(0) parsing tables LR(0) configuration or item. A configuration is a production of the grammar with a dot at some position on its right side. 1. Construct F = {I0, I1, ... In}, the collection of configurating sets for G39。. 2. State i is determined from Ii. The parsing actions for the state are determined as follows: a) If A – u? is in Ii then set action[i,a] to reduce A – u for all input. (A not equal to S39。. 2. State i is determined from Ii. The parsing actions for the state are determined as follows: a) If A – u? is in Ii then set action[i,a] to reduce A – u for all a in Follow(A) (A may not be S39。 (augmented by adding the special production S39。 – ?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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1