CONSTRUCTOR G23.grm

Start of CONSTRUCTOR for the Grammar G23.grm Sat Apr 03 15:46:59 2004

Terminal alphabet
# 1 = #
# 2 = a
# 3 = b
# 4 = 1
# 5 = c
# 6 = d

Nonterminal alphabet
# 7 = `T'
# 8 = `S'
# 9 = `A'
#10 = `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' -> c `A' c
P 9: `B' -> d `B'
Leftmost-set
Symbol # a b 1 c d T S A B
7.T * 0 0 0 0 0 0 0 0 0
8.S 0 * * 0 0 0 0 0 0 0
9.A 0 0 0 * * 0 0 0 0 0
10.B 0 0 0 * 0 * 0 0 0 0
Rightmost-set
Symbol # a b 1 c d T S A B
7.T * 0 0 0 0 0 0 0 0 0
8.S 0 * * 0 0 0 0 0 0 0
9.A 0 0 0 * * 0 0 0 0 0
10.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: a , b

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

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

Precedence matrix
Symbol # a b 1 c d T S A B
1.# 0 < < 0 0 0 0 = 0 0
2.a > 0 0 < < < 0 0 = =
3.b > 0 0 < < < 0 0 = =
4.1 0 > > 0 > 0 0 0 0 0
5.c 0 > > < 6 0 0 0 = 0
6.d 0 0 0 < 0 < 0 0 0 =
7.T 0 0 0 0 0 0 0 0 0 0
8.S = 0 0 0 0 0 0 0 0 0
9.A 0 = = 0 = 0 0 0 0 0
10.B 0 5 5 0 0 0 0 0 0 0
The relationships of symbol #1 #:
<• a <• b =• `S'

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

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

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

The relationships of symbol #5 c:
•> a •> b <• 1 <••> c =• `A'

The relationships of symbol #6 d:
<• 1 <• d =• `B'

The relationships of symbol #7 `T':

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

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

The relationships of symbol #10 `B':
=••> a =••> b

Precedence varies

P1-conflict: c <••> c
The source is the production P 8: `A' -> c `A' c
I'll add a new NT P10: `A1' -> c
I'll change the production P 8: `A' -> `A1' `A' c

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

P1-conflict: `B' =••> b
The source is the production P 4: `S' -> a `B' b
I'll add a new NT P12: `S3' -> a `B'
I'll change the production P 4: `S' -> `S3' b
New grammar
P 1: `T' -> # `S' #
P 2: `S' -> a `A' a
P 3: `S' -> b `A' b
P 4: `S' -> `S3' b
P 5: `S' -> `S2' a
P 6: `A' -> 1
P 7: `B' -> 1
P 8: `A' -> `A1' `A' c
P 9: `B' -> d `B'
P10: `A1' -> c
P11: `S2' -> b `B'
P12: `S3' -> a `B'
Leftmost-set
Symbol # a b 1 c d T S A B A1 S2 S3
7.T * 0 0 0 0 0 0 0 0 0 0 0 0
8.S 0 * * 0 0 0 0 0 0 0 0 * *
9.A 0 0 0 * * 0 0 0 0 0 * 0 0
10.B 0 0 0 * 0 * 0 0 0 0 0 0 0
11.A1 0 0 0 0 * 0 0 0 0 0 0 0 0
12.S2 0 0 * 0 0 0 0 0 0 0 0 0 0
13.S3 0 * 0 0 0 0 0 0 0 0 0 0 0
Rightmost-set
Symbol # a b 1 c d T S A B A1 S2 S3
7.T * 0 0 0 0 0 0 0 0 0 0 0 0
8.S 0 * * 0 0 0 0 0 0 0 0 0 0
9.A 0 0 0 * * 0 0 0 0 0 0 0 0
10.B 0 0 0 * 0 0 0 0 0 * 0 0 0
11.A1 0 0 0 0 * 0 0 0 0 0 0 0 0
12.S2 0 0 0 * 0 0 0 0 0 * 0 0 0
13.S3 0 0 0 * 0 0 0 0 0 * 0 0 0
Leftmost & rightmost sets
`T' leftmost set: `#'
`T' rightmost set: #

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

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

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

`A1' leftmost set: `c'
`A1' rightmost set: c

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

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

Precedence matrix
Symbol # a b 1 c d T S A B A1 S2 S3
1.# 0 < < 0 0 0 0 = 0 0 0 < <
2.a > 0 0 < < < 0 0 = = < 0 0
3.b > 0 0 < < < 0 0 = = < 0 0
4.1 0 > > 0 > 0 0 0 0 0 0 0 0
5.c 0 > > > > 0 0 0 > 0 > 0 0
6.d 0 0 0 < 0 < 0 0 0 = 0 0 0
7.T 0 0 0 0 0 0 0 0 0 0 0 0 0
8.S = 0 0 0 0 0 0 0 0 0 0 0 0
9.A 0 = = 0 = 0 0 0 0 0 0 0 0
10.B 0 > > 0 0 0 0 0 0 0 0 0 0
11.A1 0 0 0 < < 0 0 0 = 0 < 0 0
12.S2 0 = 0 0 0 0 0 0 0 0 0 0 0
13.S3 0 0 = 0 0 0 0 0 0 0 0 0 0
The relationships of symbol #1 #:
<• a <• b =• `S' <• `S2' <• `S3'

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

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

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

The relationships of symbol #5 c:
•> a •> b •> 1 •> c •> `A' •> `A1'

The relationships of symbol #6 d:
<• 1 <• d =• `B'

The relationships of symbol #7 `T':

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

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

The relationships of symbol #10 `B':
•> a •> b

The relationships of symbol #11 `A1':
<• 1 <• c =• `A' <• `A1'

The relationships of symbol #12 `S2':
=• a

The relationships of symbol #13 `S3':
=• b

Grammar G23.grm is a precedence grammar
Grammar G23.grm is not invertible
Left Context

Symbol # a b 1 c d T S A B A1 S2 S3
7.T 0 0 0 0 0 0 0 0 0 0 0 0 0
8.S * 0 0 0 0 0 0 0 0 0 0 0 0
9.A 0 * * 0 0 0 0 0 0 0 * 0 0
10.B 0 * * 0 0 * 0 0 0 0 0 0 0
11.A1 0 * * 0 0 0 0 0 0 0 * 0 0
12.S2 * 0 0 0 0 0 0 0 0 0 0 0 0
13.S3 * 0 0 0 0 0 0 0 0 0 0 0 0

Right Context

Symbol # a b 1 c d
7.T 0 0 0 0 0 0
8.S * 0 0 0 0 0
9.A 0 * * 0 * 0
10.B 0 * * 0 0 0
11.A1 0 0 0 * * 0
12.S2 0 * 0 0 0 0
13.S3 0 0 * 0 0 0

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

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

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

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

`A1' left context: a , b , `A1'
`A1' right context: 1 , c

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

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

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

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

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=8 `A' -> `A1' `A' c
{`A1' , c}
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} {`A1' , c}

I'll find the subsets of dependent context of `B'
gamma2: the source is the production
P=12 `S3' -> a `B'
{a , b}
gamma2: the source is the production
P=11 `S2' -> b `B'
{b , a}
gamma2: the source is the production
P=9 `B' -> d `B'
{d , a} {d , b}

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

test_dep_con A and B

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

Grammar G23.grm is BRC(1,1)-reducible
Dependent context

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

dependent context of `B':
{a , b} {b , a} {d , a} {d , b}
Semantics
Semantics file is G23.sem
#=1
a=2
b=3
1=4
c=5
d=6
P1=7 $P 1: `T' -> # `S' #
P2=8 $P 2: `S' -> a `A' a
P3=9 $P 3: `S' -> b `A' b
P4=10 $P 4: `S' -> `S3' b
P5=11 $P 5: `S' -> `S2' a
P6=12 $P 6: `A' -> 1
P7=13 $P 7: `B' -> 1
P8=14 $P 8: `A' -> `A1' `A' c
P9=15 $P 9: `B' -> d `B'
P10=16 $P10: `A1' -> c
P11=17 $P11: `S2' -> b `B'
P12=18 $P12: `S3' -> a `B'
Result tables

File Size
G23.prm 28
G23.pm 196
G23.t 280
G23.tt 140
G23.ht 1508
G23.sm 80
G23.v 756
G23.lc 196
G23.rc 196
G23.dc 210
Look at result tables
Finish of CONSTRUCTOR Sat Apr 03 15:46:59 2004

Symbol	#	a	b	1	c	d	T	S	A	B
7.T	*	0	0	0	0	0	0	0	0	0
8.S	0	*	*	0	0	0	0	0	0	0
9.A	0	0	0	*	*	0	0	0	0	0
10.B	0	0	0	*	0	*	0	0	0	0

Symbol	#	a	b	1	c	d	T	S	A	B	A1	S2	S3
7.T	*	0	0	0	0	0	0	0	0	0	0	0	0
8.S	0	*	*	0	0	0	0	0	0	0	0	*	*
9.A	0	0	0	*	*	0	0	0	0	0	*	0	0
10.B	0	0	0	*	0	*	0	0	0	0	0	0	0
11.A1	0	0	0	0	*	0	0	0	0	0	0	0	0
12.S2	0	0	*	0	0	0	0	0	0	0	0	0	0
13.S3	0	*	0	0	0	0	0	0	0	0	0	0	0

File	Size
G23.prm	28
G23.pm	196
G23.t	280
G23.tt	140
G23.ht	1508
G23.sm	80
G23.v	756
G23.lc	196
G23.rc	196
G23.dc	210

Start of CONSTRUCTOR for the Grammar G23.grm Sat Apr 03 15:46:59 2004

Terminal alphabet

Nonterminal alphabet

Productions

Leftmost-set

Rightmost-set

Leftmost & rightmost sets

Precedence matrix

Precedence varies

New grammar

Leftmost-set

Rightmost-set

Leftmost & rightmost sets

Precedence matrix

Grammar G23.grm is a precedence grammar

Grammar G23.grm is a precedence grammar

Grammar G23.grm is not invertibleLeft ContextSymbol#ab1cdTSABA1S2S37.T00000000000008.S*0000000000009.A0**0000000*0010.B0**00*000000011.A10**0000000*0012.S2*00000000000013.S3*000000000000Right ContextSymbol#ab1cd7.T0000008.S*000009.A0**0*010.B0**00011.A1000**012.S20*000013.S300*000

Grammar G23.grm is not invertible

Left Context

Right Context

Independent context

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

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

Dependent context

Semantics

Result tables

Finish of CONSTRUCTOR Sat Apr 03 15:46:59 2004