Start of CONSTRUCTOR for the Grammar G4.grm Sat Apr 03 15:53:56 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 | # | a | b | 0 | 1 | T | S | A | B |
6.T | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7.S | 0 | * | * | 0 | 0 | 0 | 0 | 0 | 0 |
8.A | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 |
9.B | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 |
Rightmost-set
Symbol | # | a | b | 0 | 1 | T | S | A | B |
6.T | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7.S | 0 | 0 | 0 | 0 | * | 0 | 0 | * | * |
8.A | 0 | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 |
9.B | 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: 1 , A , B
`A' leftmost set: `0'
`A' rightmost set: 1
`B' leftmost set: `0'
`B' rightmost set: 1
Precedence matrix
Symbol | # | a | b | 0 | 1 | T | S | A | B |
1.# | 0 | < | < | 0 | 0 | 0 | = | 0 | 0 |
2.a | 0 | 0 | 0 | < | 0 | 0 | 0 | = | 0 |
3.b | 0 | 0 | 0 | < | 0 | 0 | 0 | 0 | = |
4.0 | 0 | 0 | 0 | < | = | 0 | 0 | = | = |
5.1 | > | 0 | 0 | 0 | 5 | 0 | 0 | 0 | 0 |
6.T | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7.S | = | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8.A | > | 0 | 0 | 0 | = | 0 | 0 | 0 | 0 |
9.B | > | 0 | 0 | 0 | = | 0 | 0 | 0 | 0 |
The relationships of symbol #1 #:
The relationships of symbol #2 a:
The relationships of symbol #3 b:
The relationships of symbol #4 0:
The relationships of symbol #5 1:
The relationships of symbol #6 `T':
The relationships of symbol #7 `S':
The relationships of symbol #8 `A':
The relationships of symbol #9 `B':
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 | # | a | b | 0 | 1 | T | S | A | B | B1 | B2 |
6.T | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7.S | 0 | * | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8.A | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
9.B | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 | * | * |
10.B1 | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
11.B2 | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Rightmost-set
Symbol | # | a | b | 0 | 1 | T | S | A | B | B1 | B2 |
6.T | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7.S | 0 | 0 | 0 | 0 | * | 0 | 0 | * | * | 0 | 0 |
8.A | 0 | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 |
9.B | 0 | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 |
10.B1 | 0 | 0 | 0 | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 |
11.B2 | 0 | 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: 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 | # | a | b | 0 | 1 | T | S | A | B | B1 | B2 |
1.# | 0 | < | < | 0 | 0 | 0 | = | 0 | 0 | 0 | 0 |
2.a | 0 | 0 | 0 | < | 0 | 0 | 0 | = | 0 | 0 | 0 |
3.b | 0 | 0 | 0 | < | 0 | 0 | 0 | 0 | = | < | < |
4.0 | 0 | 0 | 0 | < | = | 0 | 0 | = | = | < | < |
5.1 | > | 0 | 0 | 0 | > | 0 | 0 | 0 | 0 | 0 | 0 |
6.T | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7.S | = | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8.A | > | 0 | 0 | 0 | = | 0 | 0 | 0 | 0 | 0 | 0 |
9.B | > | 0 | 0 | 0 | = | 0 | 0 | 0 | 0 | 0 | 0 |
10.B1 | 0 | 0 | 0 | 0 | = | 0 | 0 | 0 | 0 | 0 | 0 |
11.B2 | 0 | 0 | 0 | 0 | = | 0 | 0 | 0 | 0 | 0 | 0 |
The relationships of symbol #1 #:
The relationships of symbol #2 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:
The relationships of symbol #6 `T':
The relationships of symbol #7 `S':
The relationships of symbol #8 `A':
The relationships of symbol #9 `B':
The relationships of symbol #10 `B1':
The relationships of symbol #11 `B2':
Grammar G4.grm is a precedence grammar
Grammar G4.grm is not invertible
Left Context
Symbol | # | a | b | 0 | 1 | T | S | A | B | B1 | B2 |
6.T | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7.S | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8.A | 0 | * | 0 | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
9.B | 0 | 0 | * | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
10.B1 | 0 | 0 | * | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
11.B2 | 0 | 0 | * | * | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Right Context
Symbol | # | a | b | 0 | 1 |
6.T | 0 | 0 | 0 | 0 | 0 |
7.S | * | 0 | 0 | 0 | 0 |
8.A | * | 0 | 0 | 0 | * |
9.B | * | 0 | 0 | 0 | * |
10.B1 | 0 | 0 | 0 | 0 | * |
11.B2 | 0 | 0 | 0 | 0 | * |
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 G4.grm is not BRC-reducible
The following pairs of nonterminals are having nondifferent context:
`A'and `B1'
Finish of CONSTRUCTOR Sat Apr 03 15:53:56 2004