Talk:Simple LR parser
From Wikipedia, the free encyclopedia
The parser uses a stack as work history memory, and 2 tables as methodology. The SLR is a bottom up parser , that can recognize unambiguous grammars that can be parsed with one symbol of lookahead. The algorithm and the stack usage in the example isn't strictly correct, as it suggests that the stack can just hold the state as history, when in Aho the stack holds both the state and previous symbols. The Aho et al book is a much more understandable explanation, and the example they are using is also better, as it is the grammar for a cutdown infix calculator, so it shows applicability as well as recursion. The Aho explanation begins with an unambiguous but fairly standard, readable grammar (earlier in the chapter, there is a discussion about topdown grammars, but the problem with predictive top down parsers was that the human readable grammar had to be converted so there was no (left) recursion in the grammar , and other disambiguation steps , as preparation ). The grammar was then converted , similiar to the wiki I think, by the steps of : creating a "pre" first step , so that there could be a transition to the top most symbol ; finding the initial closure set, which is basically stating explicitly and exhaustively what possibilities the particular initial grammar rule could be, given the current position of reading of input, which is represented by a dot, and the dot being at the left, given that no input has been read. Then from this , the goto rule generates the next possible set of rules, given one symbol of input , the symbol being possibly a nonterminal . The example in the wiki doesn't adequately account for the fact that the symbol could be a nonterminal, as it is not using a recursive grammar as an example. These other sets of items can then have the goto rule applied again, which is akin to reading the second next symbol, and so on with each sets of items generated. Of course, some of those sets of items will be repeated, so this is like an arrow in the state machine going back to a previously stepped over state. The idea was that a state machine was generated , where each state was a unique set of items, and the transition arrows are labelled with the possible symbols that can be seen from each state.
The final algorithm part, was to convert the state machine to the
SLR parsing machine , where the row labels of SLR parsing machine are the labels of the different states , and the columns of the central table are the possible terminal input symbols, and the columns of the rightmost table the nonterminal parsed symbols. The cells of the central table would hold either shift or reduce action, the shift actions coming directly from the state machine generated during the set of items construction, where a transition from one state to another on a symbol would correspond to the row corresponding the beginning state, the column corresponding the symbol, and the shift N , being the N corresponding to the state being transitioned to. This would not fill out all cells of the central table. The cells with reduction steps would be filled out by the FOLLOW(a) function, where a would be a particular grammar rule, and FOLLOW expressed all the possible terminal symbols that could follow that rule, and if that rule was A -> alpha dot , where the dot was rightmost, and that dotted item was in a particular set of items, then this would correspond to the row of the SLR table . This makes sense, because the dot at rightmost would mean there was a complete match to a grammar rule at that state, if the next symbol encountered was one of the possible symbols that can follow that grammar rule e.g. if F is factor, and E is expression and F -> (E . ) was in the state of items, Follow E would contain ).
... more on this.. Spamducky 00:04, 21 August 2007 (UTC)
