16 SLR PARSING

Rajeswari Sridhar

In this module, we will discuss the parsing action of the SLR parser. The parser uses the SLR parsing table already discussed in the previous module and uses a stack and compares the contents of the stack with the input symbol and manipulates the stack by referring to the parsing table.

 

16.1 Parsing algorithm

 

As in the case of LL(1), Shift-reduce and Operator precedence parser discussed so far, the SLR(1) parser also uses a stack for manipulating the input string and decide on successful or unsuccessful parsing action. The stack is loaded with the initial state symbol 0. As we already discussed in the previous module, the set of items number correspond to the state of the parsing table. The input string is appended with $ symbol. The contents of the stack and the input is shown in figure 16.1

of the RHS of the production from the stack. We then observe the state number after popping and let the state be sm -r. The LHS of the production A is pushed onto the stack and the combination of sm-r, A is looked in the goto() section of the SLR parsing table and the corresponding state number is pushed onto the stack. The input pointer stays as it is in the previous iteration

  1. If action[sm ,ai] = accept, then stop

This is a terminating action of the parsing table where the action corresponds to accept and this would be typically reached only if ai corresponds to “$” as it is the only combination in the table that has the accept action.

  1. If action[sm ,ai] = error, then attempt recovery

If the table entry corresponds to an empty entry then we claim it as an error combination and the parser has to go through a error recovery process.

 

The algorithm is given is Algorithm 16.1

 

SLR_PARSING(SLR_Parsing_table T, Input w$)

 

{

  • Set input to point to the first symbol of w$
  • Repeat forever

Let s be the state on the top of the stack

  1. Let a be the symbol pointed to by ip
  2. If action [s, a] = shift s’ then
    1. Push a then s’ on top of the stack
  1. Move input to the next input symbol
  • Else if action [s, a] = reduce A à β then
    1. Pop 2 * | β | symbols off the stack
  1. Let s’ be the state now on the top of the stack
  2. Push A then goto [s’, A] on top of the stack
  3. Output the production A à β
  4. Else if action[s, a] = accept then return;
  5. Else error()

}

 

The steps from (ii) to (v) correspond to the steps (1) to (4) of the earlier procedure.

 

Example 16.1 Consider the string “id * id +id” to be parsed by the SLR parser. For convenience the SLR parsing table is given in Table 16.1. The input string is appended with $ to indicate end of input. The overall parsing action is given in Table 16.2 where the comments column indicates how parsing action is done.

 

If the input has the next symbol as “)” after the last but one step in Table 16.2, we need to compare [1, )]. As we know from the parsing table 16.1, the table entry is blank which means the input is not accepted and the parser cannot continue parsing. For these situations, error recovery mechanisms in terms of panic / phrase mode need to be applied. We can also cla im that “Every SLR grammar is unambiguous, but not every unambiguous grammar is SLR”. This means that the SLR parser can parse only a small class of grammar.