Start of CONSTRUCTOR for the Grammar G27.grm Sat Apr 03 15:49:30 2004

Terminal alphabet

# 1 = #
# 2 = a
# 3 = b
# 4 = 1
# 5 = c
# 6 = d

Nonterminal alphabet

# 7 = `T'
# 8 = `S'
# 9 = `A'
#10 = `B'

Productions

P 1: `T' -> # `S' #
P 2: `S' -> a `A' a
P 3: `S' -> b `A' b
P 4: `S' -> a `B' b
P 5: `S' -> b `B' a
P 6: `A' -> 1
P 7: `B' -> 1
P 8: `A' -> `B' c
P 9: `B' -> `A' d

Leftmost-set

Symbol#ab1cdTSAB
7.T*000000000
8.S0**0000000
9.A000*0000**
10.B000*0000**

Rightmost-set

Symbol#ab1cdTSAB
7.T*000000000
8.S0**0000000
9.A000**00000
10.B000*0*0000

Leftmost & rightmost sets

`T' leftmost set: `#'
`T' rightmost set: #

`S' leftmost set: `a' , `b'
`S' rightmost set: a , b

`A' leftmost set: `1' , `A' , `B'
`A' rightmost set: 1 , c

`B' leftmost set: `1' , `A' , `B'
`B' rightmost set: 1 , d

Precedence matrix

Symbol#ab1cdTSAB
1.#0<<0000=00
2.a>00<0000 3 3
3.b>00<0000 3 3
4.10>>0>>0000
5.c0>>00>0000
6.d0>>0>00000
7.T0000000000
8.S=000000000
9.A0==00=0000
10.B0==0=00000
The relationships of symbol #1 #:
<• a<• b=• `S'

The relationships of symbol #2 a:
•> #<• 1<•=• `A'<•=• `B'

The relationships of symbol #3 b:
•> #<• 1<•=• `A'<•=• `B'

The relationships of symbol #4 1:
•> a•> b•> c•> d

The relationships of symbol #5 c:
•> a•> b•> d

The relationships of symbol #6 d:
•> a•> b•> c

The relationships of symbol #7 `T':

The relationships of symbol #8 `S':
=• #

The relationships of symbol #9 `A':
=• a=• b=• d

The relationships of symbol #10 `B':
=• a=• b=• c

Precedence varies


P2-conflict: a <•=• `A'
The source is the production P 2: `S' -> a `A' a
I'll add a new NT P10: `S1' -> `A' a
I'll change the production P 2: `S' -> a `S1'

P2-conflict: a <•=• `B'
The source is the production P 4: `S' -> a `B' b
I'll add a new NT P11: `S2' -> `B' b
I'll change the production P 4: `S' -> a `S2'

P2-conflict: b <•=• `A'
The source is the production P 3: `S' -> b `A' b
I'll add a new NT P12: `S3' -> `A' b
I'll change the production P 3: `S' -> b `S3'

P2-conflict: b <•=• `B'
The source is the production P 5: `S' -> b `B' a
I'll add a new NT P13: `S4' -> `B' a
I'll change the production P 5: `S' -> b `S4'

Leftmost-set

Symbol#ab1cdTSABS1S2S3S4
7.T*0000000000000
8.S0**00000000000
9.A000*0000**0000
10.B000*0000**0000
11.S1000*0000**0000
12.S2000*0000**0000
13.S3000*0000**0000
14.S4000*0000**0000

New grammar

P 1: `T' -> # `S' #
P 2: `S' -> a `S1'
P 3: `S' -> b `S3'
P 4: `S' -> a `S2'
P 5: `S' -> b `S4'
P 6: `A' -> 1
P 7: `B' -> 1
P 8: `A' -> `B' c
P 9: `B' -> `A' d
P10: `S1' -> `A' a
P11: `S2' -> `B' b
P12: `S3' -> `A' b
P13: `S4' -> `B' a

Leftmost-set

Symbol#ab1cdTSABS1S2S3S4
7.T*0000000000000
8.S0**00000000000
9.A000*0000**0000
10.B000*0000**0000
11.S1000*0000**0000
12.S2000*0000**0000
13.S3000*0000**0000
14.S4000*0000**0000

Rightmost-set

Symbol#ab1cdTSABS1S2S3S4
7.T*0000000000000
8.S0**0000000****
9.A000**000000000
10.B000*0*00000000
11.S10*000000000000
12.S200*00000000000
13.S300*00000000000
14.S40*000000000000

Leftmost & rightmost sets

`T' leftmost set: `#'
`T' rightmost set: #

`S' leftmost set: `a' , `b'
`S' rightmost set: a , b , S1 , S2 , S3 , S4

`A' leftmost set: `1' , `A' , `B'
`A' rightmost set: 1 , c

`B' leftmost set: `1' , `A' , `B'
`B' rightmost set: 1 , d

`S1' leftmost set: `1' , `A' , `B'
`S1' rightmost set: a

`S2' leftmost set: `1' , `A' , `B'
`S2' rightmost set: b

`S3' leftmost set: `1' , `A' , `B'
`S3' rightmost set: b

`S4' leftmost set: `1' , `A' , `B'
`S4' rightmost set: a

Precedence matrix

Symbol#ab1cdTSABS1S2S3S4
1.#0<<0000=000000
2.a>00<0000<<==00
3.b>00<0000<<00==
4.10>>0>>00000000
5.c0>>00>00000000
6.d0>>0>000000000
7.T00000000000000
8.S=0000000000000
9.A0==00=00000000
10.B0==0=000000000
11.S1>0000000000000
12.S2>0000000000000
13.S3>0000000000000
14.S4>0000000000000
The relationships of symbol #1 #:
<• a<• b=• `S'

The relationships of symbol #2 a:
•> #<• 1<• `A'<• `B'=• `S1'=• `S2'

The relationships of symbol #3 b:
•> #<• 1<• `A'<• `B'=• `S3'=• `S4'

The relationships of symbol #4 1:
•> a•> b•> c•> d

The relationships of symbol #5 c:
•> a•> b•> d

The relationships of symbol #6 d:
•> a•> b•> c

The relationships of symbol #7 `T':

The relationships of symbol #8 `S':
=• #

The relationships of symbol #9 `A':
=• a=• b=• d

The relationships of symbol #10 `B':
=• a=• b=• c

The relationships of symbol #11 `S1':
•> #

The relationships of symbol #12 `S2':
•> #

The relationships of symbol #13 `S3':
•> #

The relationships of symbol #14 `S4':
•> #

Grammar G27.grm is a precedence grammar

Grammar G27.grm is not invertible

Left Context


Symbol#ab1cdTSABS1S2S3S4
7.T00000000000000
8.S*0000000000000
9.A0**00000000000
10.B0**00000000000
11.S10*000000000000
12.S20*000000000000
13.S300*00000000000
14.S400*00000000000

Right Context


Symbol#ab1cd
7.T000000
8.S*00000
9.A0**00*
10.B0**0*0
11.S1*00000
12.S2*00000
13.S3*00000
14.S4*00000


Independent context

`T' left context:
`T' right context:

`S' left context: #
`S' right context: #

`A' left context: a , b
`A' right context: a , b , d

`B' left context: a , b
`B' right context: a , b , c

`S1' left context: a
`S1' right context: #

`S2' left context: a
`S2' right context: #

`S3' left context: b
`S3' right context: #

`S4' left context: b
`S4' right context: #

Equivalent definitions:
`A' —> 1 & `B' —> 1
`A' left context: a , b
`A' right context: a , b , d

`B' left context: a , b
`B' right context: a , b , c


The independent context of `A' and `B' is not different
independent context didn't help us. I'll try to use the dependent one.


I'll find the subsets of dependent context of `A'
gamma3: the source is the production
P=12 `S3' -> `A' b
{b , b}
gamma3: the source is the production
P=10 `S1' -> `A' a
{a , a}
gamma3: the source is the production
P=9 `B' -> `A' d
{a , d} {b , d}

The set of dependent context of `A':
{a , a} {a , d} {b , b} {b , d}


I'll find the subsets of dependent context of `B'
gamma3: the source is the production
P=13 `S4' -> `B' a
{b , a}
gamma3: the source is the production
P=11 `S2' -> `B' b
{a , b}
gamma3: the source is the production
P=8 `A' -> `B' c
{a , c} {b , c}

The set of dependent context of `B':
{a , b} {a , c} {b , a} {b , c}

test_dep_con A and B

dependent context of `A' and `B' is different

Grammar G27.grm is BRC(1,1)-reducible

Dependent context


dependent context of `A':
{a , a} {a , d} {b , b} {b , d}

dependent context of `B':
{a , b} {a , c} {b , a} {b , c}

Semantics

Semantics file is G27.sem
#=1
a=2
b=3
1=4
c=5
d=6
P1=7 $P 1: `T' -> # `S' #
P2=8 $P 2: `S' -> a `S1'
P3=9 $P 3: `S' -> b `S3'
P4=10 $P 4: `S' -> a `S2'
P5=11 $P 5: `S' -> b `S4'
P6=12 $P 6: `A' -> 1
P7=13 $P 7: `B' -> 1
P8=14 $P 8: `A' -> `B' c
P9=15 $P 9: `B' -> `A' d
P10=16 $P10: `S1' -> `A' a
P11=17 $P11: `S2' -> `B' b
P12=18 $P12: `S3' -> `A' b
P13=19 $P13: `S4' -> `B' a

Result tables


FileSize
G27.prm28
G27.pm225
G27.t300
G27.tt140
G27.ht1540
G27.sm84
G27.v808
G27.lc225
G27.rc225
G27.dc208
Look at result tables

Finish of CONSTRUCTOR Sat Apr 03 15:49:30 2004