15 SLR Parser – SLR Parsing table

Rajeswari Sridhar

In the previous module, we discussed the construction of the set of items. These items which are referred to canonical items are used to construct the SLR parsing table. In this module we will discuss the construction of the SLR parsing table. We also brief on the SLR parsing procedure in this module.

 

15.1 SLR Parsing Table construction

 

This algorithm does not produce a uniquely defined parsing action tables for all grammar. However, it produces fairly good results on many grammars used for programming languages. The input to this table is the canonical set of items which is given as the Deterministic finite automata as already discussed in the previous module. The DFA is designed to recognize viable prefixes. The SLR parsing table is constructed between the set of canonical items against the grammar symbols. The non-terminals section of the parsing table corresponds to the goto() function and the terminals section of the table corresponds to shift, reduce, accept and error action. The steps involved in the SLR parsing table construction is detailed in Algorithm 15.1

 

Algorithm 15.1 SLR Parsing table

 

•      Input: Augmented Grammar G’

•      Output: SLR parsing table with functions, shift, reduce and accept SLR_Parsing_Table(Augmened grammar G’)

{

 

1.      Construct the set C={I0,I1,…,In} of LR(0) items

2.      State ‘i’ is constructed from Ii. The parsing action for state ‘i’ are determined as follows:

a.       If [A®a•ab] Î Ii and goto(Ii,a)=Ij then set action[i,a]=shift j, where a is a terminal

b.      If [A®a•] Î Ii then set action[i,a]=reduce A®a for all a Î FOLLOW(A) where A¹S’)

c.       If [S’®S•] is in Ii then set action[i,$]=accept

3.      If goto(Ii,A)=Ij then set goto[i,A]=j

4.      All other entries other than 2, 3 is declared as error

a.       Repeat for all the items until no more entries added

  1. The initial state i is the Ii holding item [S’®•S]

}

 

The rows of the parsing table correspond to the items number. These are referred to as states. The columns correspond to the non-terminals and terminals. The non-terminals correspond to the goto() function. The table entry between the state and the termina ls will reflect one of the four actions: shift, reduce, accept, and error. On the other hand, the table entry between the state entry and the non-terminals correspond to the goto section.

 

From algorithm 15.1, step 2 of the algorithm handles the actions. In 2a, it considers the canonical collection of items and we perform a goto(I,X) computation where X is a terminal. It considers the target item number from which the goto() is initiated and the destination item number which is being formed. Sets it as a shift action at the table entry [i,a] if goto(Ii,a)=Ij. The step 2b of the algorithm is for reduce action, where we consider the kernel canonical items that have a dot at the end and the table entry [ i,a] is set as reduce by the production A®a, where ‘a’ corresponds to the FOLLOW(A). Step 2c of the algorithm is very simple, where it considers the item that has the augmented grammar’s kernel item and marks the table entry [kernel item number, $] as accept. The remaining entries of the action section of the parsing table are set to error.

 

Step 3 of the algorithm generates table entries between states and the non-terminals. The table entry [i,X] = j, if goto(Ii,X)=Ij where X is a non-terminal. The remaining entries of the parsing table are considered as error.

 

Example 15.1 Let us construct the parsing table for the expression grammar. The grammar is given here for reference. The canonical collection of items is also given for quick reference in Table 15.1.

  • E’ àE
  • E à E +T
  • E à T
  • T à T * F
  • T à F
  • F à (E)
  • F à id

Since, E is the start symbol of the original grammar, E gets $ in the FOLLOW() set. Using the production F à (E), E gets the ‘)’ symbol. Using the production, E à E+T, E gets “+”. Using the production E à T, FOLLOW(T) = FOLLOW(E). In addition, to the FOLLOW(E), FOLLOW(T) gets, “*” from the production T à T*F. Tà F yields, FOLLOW(F) = FOLLOW(T) and thus the FOLLOW(T) and FOLLOW(F) results in the same set. The computation of FOLLOW() is given below in equations 15.1 to 15.3

Goto(I3, ( ) = Goto(I6, ( ) = Goto(I10, ( ) =I3 => [3, ( ] = [6, (] = [10, ( ] = s3 Goto(I7, ) ) = I9 => [7, ) ] = s9

 

Similarly for the goto () section of the parsing table, consider Goto(I0, E ) = 1 and so at the table entry [0, E] we set it to 1. The other entries are given below

 

Goto(I0, T) = Goto(I3, T ) = 2 => [0,T] = [3, T] = 2

 

Goto(I0, F ) = Goto(I3, F ) = Goto(I6, F ) = 4, => [0,F] = [3, F] = [6, F] = 4

 

Goto(I3, E ) = 7 => [3, E] = 7

 

Goto(I6, T ) = 8 => [6,T] = 8

 

Goto(I10, F) = 11 => [10, F] =11

 

After looking at the shift and goto action, it is now convenient to set the accept action. Accept action is set based on the augmented grammar’s first production. So at the item number where [S’à S.] is available, we set this item number against $ as accept.

 

In the expression grammar [E’ à E.] is available in Item 1. So at the entry [1, $], we mark “acc”, to indicate accept.

 

Now onto the reduce actions. The item numbers that has the kernel item qualifies for this action. Table 15.3 summarizes the item numbers that has this kernel item as one of its component. These items may or may not have other items in it and is not considered. As can be seen from table 15.3, there are 6 productions in the grammar and thus there are 6 kernel items. The reduce action procedure is explained in Table 15.3

 

Table 15.3 Reduce action computation

Using table 15.3 we construct Table 15.2 which has the reduce action incorporated. This parser however is not a very powerful parser.

 

After constructing the parsing table, the SLR parsing algorithm uses this table, along with a stack to validate a string. The steps involved in the parsing algorithm are given below:

  • If action[sm ,ai] = shift s, then push ai, push s, and advance input:

(s0 X1 s1 X2 s2 … Xm sm ai s,               ai+1 … an $)

  • If action[sm ,ai] = reduce A ® b and goto[sm -r,A] = s with r=|b| then pop 2r symbols, push A, and push s:

(s0 X1 s1 X2 s2 … Xm -r sm-r A s,        ai ai+1 … an $)

 

The configuration of the stack contains alternately state number corresponding to item number and grammar symbol, with the top of the stack being a state number. The input contains a terminal. The top of the stack state is compared with the input and we go for a push action if the action is shift, and would pop if the action is reduce. The algorithm is detailed in the next module with more explanation and example.

 

Summary: In this module, we learnt to construct the follow() for the input grammar as it is necessary for the parsing table’s reduce action. We also studied the manner in which the canonical collection of items is used to construct the parsing table’s shift, reduce, accept and error actions. Based on this parsing table, the next module will discuss the parsing action and how to handle the various errors and conflicts of the SLR parser.