Grammar: s  as




Yüklə 78.08 Kb.
tarix27.02.2016
ölçüsü78.08 Kb.
ASSIGNMENT

Virendra Singh Shekhawat

03CS 1019
GRAMMAR:

S  AS | b

A  SA | a


  1. To show that the grammar is ambiguous:

Def: A language is said to be ambiguous if it produces more than one parse tree for some sentence i.e. more than one leftmost derivations are possible.

Now, consider an instance of sentence , abab and we will show its two possible leftmost derivation to prove that the grammar is ambiguous .

1st leftmost derivation:

S  AS  aS  aAS  aSAS abAS abaS abab
2nd leftmost derivation:

S  AS  SAS  ASAS aSAS abAS abaS abab

Hence the given grammar is ambiguous.



  1. To construct the SLR parsing table:

First we will construct the items of the table of the modified grammar.


I0 :

S’  .S


S  .AS

S  .b


A  .SA

A  .a
I1 :

S’  S.

A  S.A


A  .SA

A  .a


S  .AS

S  .b


I2 :

S  A.S


S  .AS

S  .b


A  .SA

A  .a
I3 :

S  b.
I4 :

A  a.
I5 :

A  SA.

S  A.S


S  .AS

S  .b


A  .SA

A  .a
I6 :

A  S.A

A .SA


A  .a

S  .AS


S  .b

I7 :


S  AS.

A  S.A


A  .SA

A  .a


S  .AS

S  .b


RULES:

  1. S AS

  2. S b

  3. A  SA

  4. A  a

FOLLOW(A)={a,b}

FOLLOW(S)={a,b,$}

SLR PARSING TABLE:


Items

Action

Goto

A

b

$

S

A

I0

s4

s3




1

2

I1

s4

s3

Accept

6

5

I2

s4

s3




7

2

I3

r2

r2

r2







I4

r4

r4










I5

s4/ r3

s3/ r3



7

2

I6

S4

s3




6

5

I7

s4/ r1

s3/ r1

r1

6

5

3. To Construct LR(1) parsing table of the grammar.


Now, first we will construct the items of the grammar
I0 :

S’  .S ,$

S  .AS ,$

S  .b ,$

A  .SA ,a/b

A  .a ,a/b

I1 :

S’  S. ,$



A  S.A ,a/b

A  .SA ,a/b

A  .a ,a/b

S  .AS ,a/b

S  .b ,a/b

I2 :


S  A.S ,$

S  .AS ,$

S  .b ,$

A  .SA ,a/b

A  .a ,a/b
I3 :

S  b. ,$


I4 :

A  a. ,a/b


I5 :

A  SA. ,a/b

S  A.S ,a/b

S  .AS ,a/b

S  .b ,a/b

A  .SA ,a/b

A  .a ,a/b
I6 :

A  S.A ,a/b

A .SA ,a/b

A  .a ,a/b

S  .AS ,a/b

S  .b ,a/b


I7 :

S  b. ,a/b


I8 :


S  AS. ,$

A  S.A ,a/b

A  .SA ,a/b

A  .a ,a/b

S  .AS ,a/b

S  .b ,a/b


I9 :

S  AS. ,a/b

A  S.A ,a/b

A  .SA ,a/b

A  .a ,a/b

S  .AS ,a/b

S  .b ,a/b

I10 :


S  A.S ,a/b

S  .AS ,a/b

S  .b ,a/b

A  .SA ,a/b

A  .a ,a/b

RULES:


1)S AS

2)S b


3)A  SA

4)A  a




ITEMS

ACTION

GOTO

A

b

$

S

A

I0

s4

s3




1

2

I1

s4

s7

Accept

6

5

I2

s4

s3




8

2

I3







r2







I4

r4

r4









I5

s4/r3

s7/r3




9

10

I6

s4

s7




6

5

I7

r2

r2










I8

s4

s7

r1

6

5

I9

s4/r1

s7/r1



6

5

I10

s4

s7




9

10

LR(1) PARSING TABLE:

4)LALR PARSING TABLE:




ITEMS

ACTION

GOTO

A

b

$

S

A

I0

s4

s3-7




1

2-10

I1

s4

S3-7

Accept

6

5

I2-10

s4

s3-7




8-9

2-10

I3-7

r2

r2

r2







I4

r4

r4









I5

s4/r3

s3-7/r3




8-9

2-10

I6

s4

s3-7




6

5



















I8-9

s4/r1

s3-7/r1

r1

6

5




























-By merging the Items with identical core


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə