Start of CONSTRUCTOR for the Grammar G10.grm Sat Apr 03 15:40:18 2004

Terminal alphabet

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

Nonterminal alphabet

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

Productions

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

Leftmost-set

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

Rightmost-set

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

Leftmost & rightmost sets

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

`S' leftmost set: `a' , `b'
`S' rightmost set: a , b

`A' leftmost set: `1' , `B'
`A' rightmost set: 1 , c

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

Precedence matrix

Symbol#ab1cTSAB
1.#0<<000=00
2.a>00<000= 3
3.b>00<000= 3
4.10>>0>0000
5.c0>>000000
6.T000000000
7.S=00000000
8.A0==000000
9.B0==0=0000
The relationships of symbol #1 #:
<• a<• b=• `S'

The relationships of symbol #2 a:
•> #<• 1=• `A'<•=• `B'

The relationships of symbol #3 b:
•> #<• 1=• `A'<•=• `B'

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

The relationships of symbol #5 c:
•> a•> b

The relationships of symbol #6 `T':

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

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

The relationships of symbol #9 `B':
=• a=• b=• c

Precedence varies


P2-conflict: a <•=• `B'
The source is the production P 4: `S' -> a `B' b
I'll add a new NT P 9: `S1' -> `B' b
I'll change the production P 4: `S' -> a `S1'

P2-conflict: b <•=• `B'
The source is the production P 5: `S' -> b `B' a
I'll add a new NT P10: `S2' -> `B' a
I'll change the production P 5: `S' -> b `S2'

Leftmost-set

Symbol#ab1cTSABS1S2
6.T*0000000000
7.S0**00000000
8.A000*0000*00
9.B000*0000000
10.S1000*0000*00
11.S2000*0000*00

New grammar

P 1: `T' -> # `S' #
P 2: `S' -> a `A' a
P 3: `S' -> b `A' b
P 4: `S' -> a `S1'
P 5: `S' -> b `S2'
P 6: `A' -> 1
P 7: `B' -> 1
P 8: `A' -> `B' c
P 9: `S1' -> `B' b
P10: `S2' -> `B' a

Leftmost-set

Symbol#ab1cTSABS1S2
6.T*0000000000
7.S0**00000000
8.A000*0000*00
9.B000*0000000
10.S1000*0000*00
11.S2000*0000*00

Rightmost-set

Symbol#ab1cTSABS1S2
6.T*0000000000
7.S0**000000**
8.A000**000000
9.B000*0000000
10.S100*00000000
11.S20*000000000

Leftmost & rightmost sets

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

`S' leftmost set: `a' , `b'
`S' rightmost set: a , b , S1 , S2

`A' leftmost set: `1' , `B'
`A' rightmost set: 1 , c

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

`S1' leftmost set: `1' , `B'
`S1' rightmost set: b

`S2' leftmost set: `1' , `B'
`S2' rightmost set: a

Precedence matrix

Symbol#ab1cTSABS1S2
1.#0<<000=0000
2.a>00<000=<=0
3.b>00<000=<0=
4.10>>0>000000
5.c0>>00000000
6.T00000000000
7.S=0000000000
8.A0==00000000
9.B0==0=000000
10.S1>0000000000
11.S2>0000000000
The relationships of symbol #1 #:
<• a<• b=• `S'

The relationships of symbol #2 a:
•> #<• 1=• `A'<• `B'=• `S1'

The relationships of symbol #3 b:
•> #<• 1=• `A'<• `B'=• `S2'

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

The relationships of symbol #5 c:
•> a•> b

The relationships of symbol #6 `T':

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

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

The relationships of symbol #9 `B':
=• a=• b=• c

The relationships of symbol #10 `S1':
•> #

The relationships of symbol #11 `S2':
•> #

Grammar G10.grm is a precedence grammar

Grammar G10.grm is not invertible

Left Context


Symbol#ab1cTSABS1S2
6.T00000000000
7.S*0000000000
8.A0**00000000
9.B0**00000000
10.S10*000000000
11.S200*00000000

Right Context


Symbol#ab1c
6.T00000
7.S*0000
8.A0**00
9.B0**0*
10.S1*0000
11.S2*0000


Independent context

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

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

`A' left context: a , b
`A' right context: a , b

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

`S1' left context: a
`S1' right context: #

`S2' left context: b
`S2' right context: #

Equivalent definitions:
`A' —> 1 & `B' —> 1
`A' left context: a , b
`A' right context: a , b

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


The independent context of `A' and `B' 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=2 `S' -> a `A' a
{a , a}
gamma1: the source is the production
P=3 `S' -> b `A' b
{b , b}

The set of dependent context of `A':
{a , a} {b , b}


I'll find the subsets of dependent context of `B'
gamma3: the source is the production
P=9 `S1' -> `B' b
{a , b}
gamma3: the source is the production
P=10 `S2' -> `B' a
{b , a}
gamma3: the source is the production
P=8 `A' -> `B' c
{a , c} {b , c}

The set of dependent context of `B':
{a , b} {a , c} {b , a} {b , c}

test_dep_con A and B

dependent context of `A' and `B' is different

Grammar G10.grm is BRC(1,1)-reducible

Dependent context


dependent context of `A':
{a , a} {b , b}

dependent context of `B':
{a , b} {a , c} {b , a} {b , c}

Semantics

Semantics file is G10.sem
#=1
a=2
b=3
1=4
c=5
P1=6 $P 1: `T' -> # `S' #
P2=7 $P 2: `S' -> a `A' a
P3=8 $P 3: `S' -> b `A' b
P4=9 $P 4: `S' -> a `S1'
P5=10 $P 5: `S' -> b `S2'
P6=11 $P 6: `A' -> 1
P7=12 $P 7: `B' -> 1
P8=13 $P 8: `A' -> `B' c
P9=14 $P 9: `S1' -> `B' b
P10=15 $P10: `S2' -> `B' a

Result tables


FileSize
G10.prm28
G10.pm144
G10.t240
G10.tt120
G10.ht1428
G10.sm68
G10.v636
G10.lc144
G10.rc144
G10.dc168
Look at result tables

Finish of CONSTRUCTOR Sat Apr 03 15:40:18 2004