Left Factoring

  An LL(K) parser can recognize a grammar unambiguously only if the grammar is left factored. To understand left factoring consider the grammar given below. The grammar is not left factored.

S→ abX | abY
X→m
Y→n  

The above grammar can not be parsed by an LL(1) parser. An LL(1) parser looks ahead only a single character (Token) to make a parsing decision. But here the the parser should read two characters in advance to make a parsing decision. Thus in general we can say that there exists a non left factored grammar which can not be parsed by an LL(K) parser for any value of K. To parse the grammar it should be left factored. The grammar given below is a left factored grammar equivalent to the grammar given above. 

S→abC
C→X | Y 
X→m
Y→n

This grammar can be parsed by an LL(1) parser. 
 

C/C++ Program illustrating Spatial Locality

  Spatial locality is the expectation of a Computer System that a particular program will use data from neighboring locations of already used data. C programming language uses a row major ordering to allocate array data. That means the data is stored row wise in contiguous memory locations. So spatial locality tells us to access data in a row wise order.  

Consider the two loops given below.

// LOOP 1
   for(i =0; i < 700; i++)
   {
      for(j=0; j< 700; j++)
      {
            a[ i ][ j ]=1;     // Here elements are accessed row wise.
       }
    }

// LOOP 2
   for(i =0; i < 700; i++)
  {
      for(j=0; j< 700; j++)
      {
            a[ j ][ i ]=1;     // Here elements are accessed row wise.
       }
    }

 Which loop will take more time to execute? Even though both the loops sets exactly 490000 locations to 1, the first loop is much more faster than the second loop. Reason is spatial locality and row major ordering of C programs. If you were executing the same algorithm in MATLAB the second loop will execute faster since MATLAB follows a column major ordering for storing array data.

The Figure Given Below Shows the Output of the C Program

Click here to download the C Program illustrating the principle of Spatial Locality. 

Click here to download the C++ Program illustrating the principle of Spatial Locality.