Start of CONSTRUCTOR for the Grammar G6.grm Sat Apr 03 15:54:55 2004

Terminal alphabet

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

Nonterminal alphabet

# 6 = `T'
# 7 = `S'
# 8 = `A'
# 9 = `B'
#10 = `C'
#11 = `D'

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' -> `C' 1
P 7: `B' -> `D' 1
P 8: `C' -> 0 `B' 1
P 9: `D' -> 0 1

Leftmost-set

Symbol#ab01TSABCD
6.T*0000000000
7.S0**00000000
8.A000*0000000
9.B000*00000**
10.C000*0000000
11.D000*0000000

Rightmost-set

Symbol#ab01TSABCD
6.T*0000000000
7.S0000*00**00
8.A0000*000000
9.B0000*000000
10.C0000*000000
11.D0000*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' , `C' , `D'
`B' rightmost set: 1

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

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

Precedence matrix

Symbol#ab01TSABCD
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.C0000=000000
11.D0000=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'<• `C'<• `D'

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

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 `C':
=• 1

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

Grammar G6.grm is a precedence grammar

Grammar G6.grm is not invertible

Left Context


Symbol#ab01TSABCD
6.T00000000000
7.S*0000000000
8.A0*0*0000000
9.B00**0000000
10.C00**0000000
11.D00**0000000

Right Context


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


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

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

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

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

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


The independent context of `A' and `D' 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 `D'
gamma3: the source is the production
P=7 `B' -> `D' 1
{b , 1} {0 , 1}

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

test_dep_con A and D

common: {0 , 1}

dependent context is not different: A and D

Grammar G6.grm is not BRC-reducible


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

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