NAME:ARIJIT GHOSH 
ROLL NO:03CS3007

a)

Given Grammar:

S -> AS | b
S -> SA | a

             I)                 S                                               II)                 S     
                              /   \                                                                /   \
                           A      S                                                            A    S
                         /   \        \                                                         /      /  \
                      S      A       b                                                     a     A    S
                     /  \        \                                                                  /  \      \
                   A   S        a                                                              S    A     b
                  /       \                                                                      /         \
                a         b                                                                   b           a

            Two seperate parse tree for the same word (abab) that  belong to the language .
            Hence the language is ambiguous .(proved)

2)Contructing the SLR parsing table for the given grammer : 

Given Grammar:

S -> AS | b
A -> SA | a

Augmented Grammar:

S' -> S
S -> AS | b
A -> SA | a

States of the Augmented Grammar :{ 0,1,2,3,4,5,6,7}
Start State : 0

goto(0,a) = 1
goto(0,b) = 2
goto(0,S) = 3
goto(0,A) = 4

goto(3,a) = 1
goto(3,b) = 2
goto(3,S) = 6
goto(3,A) = 5

goto(4,a) = 1
goto(4,b) = 2
goto(4,S) = 7
goto(4,A) = 4

goto(5,a) = 1
goto(5,b) = 2
goto(5,S) = 6
goto(5,A) = 4

goto(6,a) = 1
goto(6,b) = 2
goto(6,S) = 6
goto(6,A) = 5

goto(7,a) = 1
goto(7,b) = 2
goto(7,S )= 6
goto(7,A) = 5

action[ 0,a ] = shift 1
action[ 0,b ] = shift 2

action[1 ,a ] = reduce A -> a
action[ 1,b ] = reduce A -> a

action[ 2,a ] = reduce S -> b
action[ 2,b ] = reduce S -> b

action[ 3,a ] = shift 1
action[ 3,b ] = shift 2 
action[ 3,a ] = reduce S' -> S
action[ 3,b ] = reduce S' -> S
action[ 3,$ ] = accept

action[ 4,a ] = shift 1
action[ 4,b ] = shift 2

action[5 ,a ] = shift 1
action[5 ,b ] = shift 2
action[5 , a] = reduce A -> SA
action[5 , b] = reduce A -> SA

action[6 ,a ] = shift 1
action[6 ,b ] = shift 2

action[7 ,a ] = shift 1
action[7 ,b ] = shift 2
action[7 ,a ] = reduce S -> AS
action[7 ,b ] = reduce S -> AS

The language is not SLR since the transition table has got conflicting action .

3)Constructing LR(!) parsing table for the given grammar.

The sates are :{0,1,2,3,4,5,6,7}
Where the start state is :0

goto(0,a) = 1
goto(0,b) = 2
goto(0,S) = 3
goto(0,A) = 4

goto(3,a) = 1
goto(3,b) = 2
goto(3,S) = 5
goto(3,A) = 4

goto(4,a) = 1
goto(4,b) = 2
goto(4,S) = 7
goto(4,A) = 6

goto(5,a) = 1
goto(5,b) = 2
goto(5,S) = 5
goto(5,A) = 4

goto(6,a) = 1
goto(6,b) = 2
goto(6,S) = 7
goto(6,A) = 6

goto(7,a) = 1
goto(7,b) = 2
goto(7,S) = 5
goto(7,A) = 4

action[0 ,a ] = shift 1
action[0 ,b ] = shift 2

action[1 ,a ] = reduce A -> a  
action[1 ,b ] = reduce A -> a 

action[2 ,a ] = reduce S -> b
action[2 ,b ] = reduce S -> b

action[3 ,a ] = shift 1
action[3 ,b ] = shift 2
action[3 ,$ ] = accept 

action[4 ,a ] = shift 1
action[4 ,b ] = shift 2
action[4 ,a ] = reduce A -> SA
action[4 ,b ] = reduce A -> SA 

action[5 ,a ] = shift 1
action[5 ,b ] = shift 2

action[6 ,a ] = shift 1
action[6 ,b ] = shift 2

action[7 ,a ] = shift 1
action[7 ,b ] = shift 2
action[7 ,a ] = reduce S -> AS
action[7 ,b ] = reduce S -> AS

Grammar is not a LR(1) because the transition table has got conflicting entries.

4) Constructing LALR parsing table for the given grammar ;

The states are :{ 0,1,2,3,4,5,6,7}
Where the start state is :0

All the states remain same after reduction. Hence the  goto table remain same for both the case . i.e same as the LR(1).