Start of CONSTRUCTOR for the Grammar G5A.grm Sat Apr 03 15:55:30 2004

Terminal alphabet

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

Nonterminal alphabet

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

Productions

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

Leftmost-set

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

Rightmost-set

Symbol#ab01TSAB
6.T*00000000
7.S0000*00**
8.A0000*0000
9.B0000*0000

Leftmost & rightmost sets

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

`S' leftmost set: `a' , `b'
`S' rightmost set: 1 , A , B

`A' leftmost set: `0'
`A' rightmost set: 1

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

Precedence matrix

Symbol#ab01TSAB
1.#0<<000=00
2.a000<000=0
3.b000<0000=
4.0000<=00==
5.1>000 50000
6.T000000000
7.S=00000000
8.A>000=0000
9.B>000=0000
The relationships of symbol #1 #:
<• a<• b=• `S'

The relationships of symbol #2 a:
<• 0=• `A'

The relationships of symbol #3 b:
<• 0=• `B'

The relationships of symbol #4 0:
<• 0=• 1=• `A'=• `B'

The relationships of symbol #5 1:
•> #=••> 1

The relationships of symbol #6 `T':

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

The relationships of symbol #8 `A':
•> #=• 1

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

Precedence varies


P1-conflict: 1 =••> 1
The source is the production P 7: `B' -> 0 1 1
I'll add a new NT P 8: `B1' -> 0 1
I'll change the production P 7: `B' -> `B1' 1
The source is the production P 6: `B' -> 0 `B' 1 1
I'll add a new NT P 9: `B2' -> 0 `B' 1
I'll change the production P 6: `B' -> `B2' 1

New grammar

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

Leftmost-set

Symbol#ab01TSABB1B2
6.T*0000000000
7.S0**00000000
8.A000*0000000
9.B000*00000**
10.B1000*0000000
11.B2000*0000000

Rightmost-set

Symbol#ab01TSABB1B2
6.T*0000000000
7.S0000*00**00
8.A0000*000000
9.B0000*000000
10.B10000*000000
11.B20000*000000

Leftmost & rightmost sets

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

`S' leftmost set: `a' , `b'
`S' rightmost set: 1 , A , B

`A' leftmost set: `0'
`A' rightmost set: 1

`B' leftmost set: `0' , `B1' , `B2'
`B' rightmost set: 1

`B1' leftmost set: `0'
`B1' rightmost set: 1

`B2' leftmost set: `0'
`B2' rightmost set: 1

Precedence matrix

Symbol#ab01TSABB1B2
1.#0<<000=0000
2.a000<000=000
3.b000<0000=<<
4.0000<=00==<<
5.1>000>000000
6.T00000000000
7.S=0000000000
8.A>000=000000
9.B>000=000000
10.B10000=000000
11.B20000=000000
The relationships of symbol #1 #:
<• a<• b=• `S'

The relationships of symbol #2 a:
<• 0=• `A'

The relationships of symbol #3 b:
<• 0=• `B'<• `B1'<• `B2'

The relationships of symbol #4 0:
<• 0=• 1=• `A'=• `B'<• `B1'<• `B2'

The relationships of symbol #5 1:
•> #•> 1

The relationships of symbol #6 `T':

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

The relationships of symbol #8 `A':
•> #=• 1

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

The relationships of symbol #10 `B1':
=• 1

The relationships of symbol #11 `B2':
=• 1

Grammar G5A.grm is a precedence grammar

Grammar G5A.grm is not invertible

Left Context


Symbol#ab01TSABB1B2
6.T00000000000
7.S*0000000000
8.A0*0*0000000
9.B00**0000000
10.B100**0000000
11.B200**0000000

Right Context


Symbol#ab01
6.T00000
7.S*0000
8.A*000*
9.B*000*
10.B10000*
11.B20000*


Independent context

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

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

`A' left context: a , 0
`A' right context: # , 1

`B' left context: b , 0
`B' right context: # , 1

`B1' left context: b , 0
`B1' right context: 1

`B2' left context: b , 0
`B2' right context: 1

Equivalent definitions:
`A' —> 0 1 & `B1' —> 0 1
`A' left context: a , 0
`A' right context: # , 1

`B1' left context: b , 0
`B1' right context: 1


The independent context of `A' and `B1' 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=4 `A' -> 0 `A' 1
{0 , 1}
gamma2: the source is the production
P=2 `S' -> a `A'
{a , #}

The set of dependent context of `A':
{a , #} {0 , 1}


I'll find the subsets of dependent context of `B1'
gamma3: the source is the production
P=7 `B' -> `B1' 1
{b , 1} {0 , 1}

The set of dependent context of `B1':
{b , 1} {0 , 1}

test_dep_con A and B1

common: {0 , 1}

dependent context is not different: A and B1

Grammar G5A.grm is not BRC-reducible


The following pairs of nonterminals are having nondifferent context:
`A'and `B1'

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