【文章內(nèi)容簡介】
ined by rules 2 and 3 are errors. 5. The initial state is the one constructed from the configurating set containing S39。 – ?S. SLR(1) grammars A grammar is SLR(1) if the following two conditions hold for each configurating set: 1. For any item A – u?xv in the set, with terminal x, there is no plete item B – w ? in that set with x in Follow(B). In the tables, this translates no shiftreduce conflict on any state. This means the successor function for x from that set either shifts to a new state or reduces, but not both. 2. For any two plete items A – u? and B – v ? in the same configurating set, the follow sets must be disjoint, . Follow(A) ??Follow(B) is empty. This translates to no reduce reduce conflict on any state. If more than one nonterminal could be reduced from this set, it must be possible to uniquely determine which using only one token of lookahead. The limitations of SLR(1) The SLR(1) technique still leaves something to be desired, because we are not using all the information that we have at our disposal. When we have a pleted configuration (. dot at the end) such as X – u?, we know this corresponds to a situation in which we have u as a handle on top of the stack which we then can reduce, ., replacing u by X. We allow such a reduction whenever the next symbol is in Follow(X). However, it may be that we should not reduce for every symbol in Follow(X), because the symbols below u on the stack preclude u being a handle for reduction in this case. In other words, SLR(1) states only tell us about the sequence on top of the stack, not what is below it on the stack. We may need to divide an SLR(1) state into separate states to differentiate the possible means by which that sequence has appeared on the stack. By carrying more information in the state, it will allow us to rule out these invalid reductions. LR or canonical LR parsing LR or canonical LR parsing incorporates the required extra information into the state by redefining configurations to include a terminal symbol as an added ponent. LR(1) configurations have the general form: A – X1...Xi ? Xi+1...Xj , a This means we have states corresponding to X1...Xi on the stack and we are looking to put states corresponding to Xi+1...Xj on th