SLR Grammar - Parsing Algorithm

Parsing Algorithm

A grammar is said to be SLR(1) if the following Simple LR parser algorithm results in no ambiguity.

1. If state s contains any item of the form A -> a.Xb, where X is a terminal, and X is the next token in the input string, then the action is to shift the current input token onto the stack, and the new state to be pushed on the stack is the state containing the item A -> aX.b.

2. If state s contains the complete item A -> y., and the next token in the input string is in Follow(A), then the action is to reduce by the rule A -> y. A reduction by the rule S' -> S, where S is the start state, is equivalent to acceptance; this will happen only if the next input token is $. In all other cases, the new state in computed as follows. Remove the string y and all of its corresponding states from the parsing stack. Correspondingly, back up in the DFA to the state from which the construction of y began. By construction, this state must contain an item of the form B -> a.Ab. Push A on to the stack, and push the state containing the item B -> aA.b.

3. If the next input token is such that neither of the above two cases apply, an error is declared.

Read more about this topic:  SLR Grammar