Start of CONSTRUCTOR for the Grammar G12.grm Sat Apr 03 15:43:20 2004

Terminal alphabet

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

Nonterminal alphabet

# 6 = `T'
# 7 = `S'
# 8 = `A'
# 9 = `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' -> c `B'

Leftmost-set

Symbol#ab1cTSAB
6.T*00000000
7.S0**000000
8.A000**0000
9.B000*00000

Rightmost-set

Symbol#ab1cTSAB
6.T*00000000
7.S0**000000
8.A000*0000*
9.B000*00000

Leftmost & rightmost sets

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

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

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

`B' leftmost set: `1'
`B' rightmost set: 1

Precedence matrix

Symbol#ab1cTSAB
1.#0<<000=00
2.a>00<<00==
3.b>00<<00==
4.10>>000000
5.c000<0000=
6.T000000000
7.S=00000000
8.A0==000000
9.B0 5 5000000
The relationships of symbol #1 #:
<• a<• b=• `S'

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

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

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

The relationships of symbol #5 c:
<• 1=• `B'

The relationships of symbol #6 `T':

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

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

The relationships of symbol #9 `B':
=••> a=••> b

Precedence varies


P1-conflict: `B' =••> a
The source is the production P 5: `S' -> b `B' a
I'll add a new NT P 9: `S1' -> b `B'
I'll change the production P 5: `S' -> `S1' a

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

New grammar

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

Leftmost-set

Symbol#ab1cTSABS1S2
6.T*0000000000
7.S0**000000**
8.A000**000000
9.B000*0000000
10.S100*00000000
11.S20*000000000

Rightmost-set

Symbol#ab1cTSABS1S2
6.T*0000000000
7.S0**00000000
8.A000*0000*00
9.B000*0000000
10.S1000*0000*00
11.S2000*0000*00

Leftmost & rightmost sets

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

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

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

`B' leftmost set: `1'
`B' rightmost set: 1

`S1' leftmost set: `b'
`S1' rightmost set: 1 , B

`S2' leftmost set: `a'
`S2' rightmost set: 1 , B

Precedence matrix

Symbol#ab1cTSABS1S2
1.#0<<000=00<<
2.a>00<<00==00
3.b>00<<00==00
4.10>>00000000
5.c000<0000=00
6.T00000000000
7.S=0000000000
8.A0==00000000
9.B0>>00000000
10.S10=000000000
11.S200=00000000
The relationships of symbol #1 #:
<• a<• b=• `S'<• `S1'<• `S2'

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

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

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

The relationships of symbol #5 c:
<• 1=• `B'

The relationships of symbol #6 `T':

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

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

The relationships of symbol #9 `B':
•> a•> b

The relationships of symbol #10 `S1':
=• a

The relationships of symbol #11 `S2':
=• b

Grammar G12.grm is a precedence grammar

Grammar G12.grm is not invertible

Left Context


Symbol#ab1cTSABS1S2
6.T00000000000
7.S*0000000000
8.A0**00000000
9.B0**0*000000
10.S1*0000000000
11.S2*0000000000

Right Context


Symbol#ab1c
6.T00000
7.S*0000
8.A0**00
9.B0**00
10.S10*000
11.S200*00


Independent context

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

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

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

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

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

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

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

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


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'
gamma1: the source is the production
P=2 `S' -> a `A' a
{a , a}
gamma1: the source is the production
P=3 `S' -> b `A' b
{b , b}

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


I'll find the subsets of dependent context of `B'
gamma2: the source is the production
P=9 `S1' -> b `B'
{b , a}
gamma2: the source is the production
P=10 `S2' -> a `B'
{a , b}
gamma2: the source is the production
P=8 `A' -> c `B'
{c , a} {c , b}

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

test_dep_con A and B

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

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

Dependent context


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

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

Semantics

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

Result tables


FileSize
G12.prm28
G12.pm144
G12.t240
G12.tt120
G12.ht1428
G12.sm68
G12.v636
G12.lc144
G12.rc144
G12.dc174
Look at result tables

Finish of CONSTRUCTOR Sat Apr 03 15:43:20 2004