LR(1) items and LALR(1) Parsing table how to do this?

280 Views Asked by At

From the grammar given below create LR(1) items and merge the sets of items having give the set of LALR(1) items. I am not sure how to construct from this grammar

B -> id | id ( B ) | B . id | B [ B ] | B . id ( B )

Answer so far: i0- B' -> .B, $ | .id, $ | .id ( B )

1

There are 1 best solutions below

0
On

Here are the LALR(1) sets of items, as given by LRSTAR 8.0:

STATE MACHINE LISTING:

      +=>  Shift and goto next state.
      +<=  Shift and reduce.
       <=  Reduce.

///////////////////////////// STATE 0 /////////////////////////////
//
// *    0  G -> . B <eof> 

        2  <id>        +=>    2

        1  B           +=>    1

///////////////////////////// STATE 1 /////////////////////////////
//
// *    0  G -> B . <eof> 
// *    3  B -> B . '.' <id> 
// *    4  B -> B . '[' B ']' 
// *    5  B -> B . '.' <id> '(' B ')' 

        1  <eof>       +=>   11
        5  '.'         +=>    3
        6  '['         +=>    4

Came from: 0

///////////////////////////// STATE 2 /////////////////////////////
//
// *    1  B -> <id> . 
// *    2  B -> <id> . '(' B ')' 

        3  '('         +=>    5
           (default)    <=    1

Came from: 0 4 5 9

///////////////////////////// STATE 3 /////////////////////////////
//
// *    3  B -> B '.' . <id> 
// *    5  B -> B '.' . <id> '(' B ')' 

        2  <id>        +=>    6

Came from: 1 7 8 10

///////////////////////////// STATE 4 /////////////////////////////
//
// *    4  B -> B '[' . B ']' 

        2  <id>        +=>    2

        1  B           +=>    7

Came from: 1 7 8 10

///////////////////////////// STATE 5 /////////////////////////////
//
// *    2  B -> <id> '(' . B ')' 

        2  <id>        +=>    2

        1  B           +=>    8

Came from: 2

///////////////////////////// STATE 6 /////////////////////////////
//
// *    3  B -> B '.' <id> . 
// *    5  B -> B '.' <id> . '(' B ')' 

        3  '('         +=>    9
           (default)    <=    3

Came from: 3

///////////////////////////// STATE 7 /////////////////////////////
//
// *    3  B -> B . '.' <id> 
// *    4  B -> B . '[' B ']' 
// *    4  B -> B '[' B . ']' 
// *    5  B -> B . '.' <id> '(' B ')' 

        5  '.'         +=>    3
        6  '['         +=>    4
        7  ']'         +<=    4

Came from: 4

///////////////////////////// STATE 8 /////////////////////////////
//
// *    2  B -> <id> '(' B . ')' 
// *    3  B -> B . '.' <id> 
// *    4  B -> B . '[' B ']' 
// *    5  B -> B . '.' <id> '(' B ')' 

        4  ')'         +<=    2
        5  '.'         +=>    3
        6  '['         +=>    4

Came from: 5

///////////////////////////// STATE 9 /////////////////////////////
//
// *    5  B -> B '.' <id> '(' . B ')' 

        2  <id>        +=>    2

        1  B           +=>   10

Came from: 6

///////////////////////////// STATE 10 /////////////////////////////
//
// *    3  B -> B . '.' <id> 
// *    4  B -> B . '[' B ']' 
// *    5  B -> B . '.' <id> '(' B ')' 
// *    5  B -> B '.' <id> '(' B . ')' 

        5  '.'         +=>    3
        6  '['         +=>    4
        4  ')'         +<=    5

Came from: 9

///////////////////////////// STATE 11 /////////////////////////////
//
// *    0  G -> B <eof> . 

           (default)    <=    0

Came from: 1

//
////////////////////////////////////////////////////////////////////

The sets of items for minimal LR(1) is the same. I'm not sure about the sets of canonical LR(1) items. Canonical LR(1) parser tables are not practical for use, unless the grammar is small.