Start of CONSTRUCTOR for the Grammar G11.grm Sat Apr 03 15:43:03 2004
Terminal alphabet
# 1 = #
# 2 = a
# 3 = c
# 4 = b
Nonterminal alphabet
# 5 = `T'
# 6 = `S'
# 7 = `B'
# 8 = `C'
# 9 = `A'
#10 = `D'
Productions
P 1: `T' -> # `S' #
P 2: `S' -> `B' `C'
P 3: `A' -> `B' `D'
P 4: `A' -> `A' a
P 5: `A' -> a c
P 6: `B' -> a
P 7: `C' -> `A' b
P 8: `D' -> a
Leftmost-set
| Symbol | # | a | c | b | T | S | B | C | A | D |
| 5.T | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6.S | 0 | * | 0 | 0 | 0 | 0 | * | 0 | 0 | 0 |
| 7.B | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8.C | 0 | * | 0 | 0 | 0 | 0 | * | 0 | * | 0 |
| 9.A | 0 | * | 0 | 0 | 0 | 0 | * | 0 | * | 0 |
| 10.D | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Rightmost-set
| Symbol | # | a | c | b | T | S | B | C | A | D |
| 5.T | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6.S | 0 | 0 | 0 | * | 0 | 0 | 0 | * | 0 | 0 |
| 7.B | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8.C | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 |
| 9.A | 0 | * | * | 0 | 0 | 0 | 0 | 0 | 0 | * |
| 10.D | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Leftmost & rightmost sets
`T' leftmost set: `#'
`T' rightmost set: #
`S' leftmost set: `a' , `B'
`S' rightmost set: b , C
`B' leftmost set: `a'
`B' rightmost set: a
`C' leftmost set: `a' , `B' , `A'
`C' rightmost set: b
`A' leftmost set: `a' , `B' , `A'
`A' rightmost set: a , c , D
`D' leftmost set: `a'
`D' rightmost set: a
Precedence matrix
| Symbol | # | a | c | b | T | S | B | C | A | D |
| 1.# | 0 | < | 0 | 0 | 0 | = | < | 0 | 0 | 0 |
| 2.a | 0 | > | = | > | 0 | 0 | > | > | > | > |
| 3.c | 0 | > | 0 | > | 0 | 0 | 0 | 0 | 0 | 0 |
| 4.b | > | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5.T | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6.S | = | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7.B | 0 | < | 0 | 0 | 0 | 0 | < | = | < | = |
| 8.C | > | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 9.A | 0 | = | 0 | = | 0 | 0 | 0 | 0 | 0 | 0 |
| 10.D | 0 | > | 0 | > | 0 | 0 | 0 | 0 | 0 | 0 |
The relationships of symbol #1 #:
The relationships of symbol #2 a:
| •> a | =• c | •> b | •> `B' | •> `C' | •> `A' | •> `D' |
The relationships of symbol #3 c:
The relationships of symbol #4 b:
The relationships of symbol #5 `T':
The relationships of symbol #6 `S':
The relationships of symbol #7 `B':
| <• a | <• `B' | =• `C' | <• `A' | =• `D' |
The relationships of symbol #8 `C':
The relationships of symbol #9 `A':
The relationships of symbol #10 `D':
Grammar G11.grm is a precedence grammar
Grammar G11.grm is not invertible
Left Context
| Symbol | # | a | c | b | T | S | B | C | A | D |
| 5.T | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6.S | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7.B | * | 0 | 0 | 0 | 0 | 0 | * | 0 | 0 | 0 |
| 8.C | 0 | 0 | 0 | 0 | 0 | 0 | * | 0 | 0 | 0 |
| 9.A | 0 | 0 | 0 | 0 | 0 | 0 | * | 0 | 0 | 0 |
| 10.D | 0 | 0 | 0 | 0 | 0 | 0 | * | 0 | 0 | 0 |
Right Context
| Symbol | # | a | c | b |
| 5.T | 0 | 0 | 0 | 0 |
| 6.S | * | 0 | 0 | 0 |
| 7.B | 0 | * | 0 | 0 |
| 8.C | * | 0 | 0 | 0 |
| 9.A | 0 | * | 0 | * |
| 10.D | 0 | * | 0 | * |
Independent context
`T' left context:
`T' right context:
`S' left context: #
`S' right context: #
`B' left context: # , `B'
`B' right context: a
`C' left context: `B'
`C' right context: #
`A' left context: `B'
`A' right context: a , b
`D' left context: `B'
`D' right context: a , b
Equivalent definitions:
`B' —> a & `D' —> a
`B' left context: # , `B'
`B' right context: a
`D' left context: `B'
`D' right context: a , b
The independent context of `B' 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 `B'
gamma3: the source is the production
P=3 `A' -> `B' `D'
{`B' , a}
gamma3: the source is the production
P=2 `S' -> `B' `C'
{# , a}
The set of dependent context of `B':
{# , a} {`B' , a}
I'll find the subsets of dependent context of `D'
gamma2: the source is the production
P=3 `A' -> `B' `D'
{`B' , a} {`B' , b}
The set of dependent context of `D':
{`B' , a} {`B' , b}
test_dep_con B and D
common: {`B' , a}
dependent context is not different: B and D
Grammar G11.grm is not BRC-reducible
The following pairs of nonterminals are having nondifferent context:
`B'and `D'
Finish of CONSTRUCTOR Sat Apr 03 15:43:03 2004