Start of CONSTRUCTOR for the Grammar G28.grm Sat Apr 03 15:51:33 2004

Terminal alphabet

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

Nonterminal alphabet

# 5 = `A'
# 6 = `B'
# 7 = `C'
# 8 = `D'
# 9 = `E'

Productions

P 1: `A' -> # a `B' #
P 2: `B' -> a `B' `C'
P 3: `B' -> b
P 4: `C' -> b
P 5: `A' -> # a `D' #
P 6: `D' -> # `D' a `E'
P 7: `D' -> c
P 8: `E' -> c

Leftmost-set

Symbol#abcABCDE
5.A*00000000
6.B0**000000
7.C00*000000
8.D*00*00000
9.E000*00000

Rightmost-set

Symbol#abcABCDE
5.A*00000000
6.B00*000*00
7.C00*000000
8.D000*0000*
9.E000*00000

Leftmost & rightmost sets

`A' leftmost set: `#'
`A' rightmost set: #

`B' leftmost set: `a' , `b'
`B' rightmost set: b , C

`C' leftmost set: `b'
`C' rightmost set: b

`D' leftmost set: `#' , `c'
`D' rightmost set: c , E

`E' leftmost set: `c'
`E' rightmost set: c

Precedence matrix

Symbol#abcABCDE
1.#<=0<000=0
2.a<<<<0=0==
3.b>0>000>00
4.c>>0000000
5.A000000000
6.B=0<000=00
7.C>0>000>00
8.D==0000000
9.E>>0000000
The relationships of symbol #1 #:
<• #=• a<• c=• `D'

The relationships of symbol #2 a:
<• #<• a<• b<• c=• `B'=• `D'=• `E'

The relationships of symbol #3 b:
•> #•> b•> `C'

The relationships of symbol #4 c:
•> #•> a

The relationships of symbol #5 `A':

The relationships of symbol #6 `B':
=• #<• b=• `C'

The relationships of symbol #7 `C':
•> #•> b•> `C'

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

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

Grammar G28.grm is a precedence grammar

Grammar G28.grm is not invertible

Left Context


Symbol#abcABCDE
5.A000000000
6.B0*0000000
7.C00000*000
8.D**0000000
9.E0*0000000

Right Context


Symbol#abc
5.A0000
6.B*0*0
7.C*0*0
8.D**00
9.E**00


Independent context

`A' left context:
`A' right context:

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

`C' left context: `B'
`C' right context: # , b

`D' left context: # , a
`D' right context: # , a

`E' left context: a
`E' right context: # , a

Equivalent definitions:
`B' —> b & `C' —> b
`B' left context: a
`B' right context: # , b

`C' left context: `B'
`C' right context: # , b


The left context of `B' and `C' is different

Equivalent definitions:
`D' —> c & `E' —> c
`D' left context: # , a
`D' right context: # , a

`E' left context: a
`E' right context: # , a


The independent context of `D' and `E' 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 `D'
gamma1: the source is the production
P=6 `D' -> # `D' a `E'
{# , a}
gamma1: the source is the production
P=5 `A' -> # a `D' #
{a , #}

The set of dependent context of `D':
{# , a} {a , #}


I'll find the subsets of dependent context of `E'
gamma2: the source is the production
P=6 `D' -> # `D' a `E'
{a , #} {a , a}

The set of dependent context of `E':
{a , #} {a , a}

test_dep_con D and E

common: {a , #}

dependent context is not different: D and E

Grammar G28.grm is not BRC-reducible


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

Finish of CONSTRUCTOR Sat Apr 03 15:51:33 2004