1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
package scalac.transformer.matching ;
import scalac.Global ;
import scalac.ApplicationError ;
import scalac.ast.Tree ;
import scalac.util.Name ;
import scalac.util.Names ;
import Tree.* ;
import java.util.* ;
//import scala.compiler.printer.XMLTreePrinter ;
//import scala.compiler.printer.XMLAutomPrinter ;
/** a Berry-Sethi style construction for nfas.
* this class plays is the "Builder" for the "Director" class
* WordRecognizer.
*/
public class BindingBerrySethi extends BerrySethi {
HashMap deltaqRev[]; // delta of Rev
Vector defaultqRev[]; // default transitions of Rev
Vector qbinders[]; // transitions <-> variables
protected void makeTransition( Integer srcI, Integer destI, Label label ) {
int src = srcI.intValue() ;
int dest = destI.intValue() ;
Vector arrows, revArrows;
Label revLabel = new Label.Pair( srcI, label );
switch( label ) {
case DefaultLabel:
arrows = defaultq[ src ];
revArrows = defaultqRev[ dest ];
break;
default:
arrows = (Vector) deltaq[ src ].get( label );
if( arrows == null )
deltaq[ src ].put( label,
arrows = new Vector() );
revArrows = (Vector) deltaqRev[ dest ].get( revLabel );
if( revArrows == null )
deltaqRev[ dest ].put( revLabel,
revArrows = new Vector() );
}
arrows.add( destI );
revArrows.add( srcI );
}
NondetWordAutom revnfa ;
void seenLabel( Tree pat, Label label ) {
Integer i = new Integer( ++pos );
seenLabel( pat, i, label );
switch( pat ) {
case Apply(_, _):
case Literal( _ ):
case Select(_, _):
case Typed(_,_):
this.varAt.put( i, activeBinders.clone() ); // below @ ?
break;
case Ident( Name name ):
assert ( pat.symbol() == Global.instance.definitions.PATTERN_WILDCARD )||( name.toString().indexOf("$") > -1 ) : "found variable label "+name;
Vector binders = (Vector) activeBinders.clone();
/*
if( pat.symbol() != Global.instance.definitions.PATTERN_WILDCARD) {
binders.add( pat.symbol() );
}
*/
this.varAt.put( i, binders );
break;
default:
throw new ApplicationError("unexpected atom:"+pat.getClass());
}
}
HashMap varAt; // chi: Positions -> Vars (Symbol)
protected void initialize( Tree[] pats ) {
this.varAt = new HashMap(); // Xperiment
super.initialize( pats );
}
protected void initializeAutom() {
super.initializeAutom();
deltaqRev = new HashMap[ pos ]; // deltaRev
defaultqRev = new Vector[ pos ]; // default transitions
qbinders = new Vector[ pos ]; // transitions <-> variables
for( int j = 0; j < pos; j++ ) {
deltaqRev[ j ] = new HashMap();
defaultqRev[ j ] = new Vector();
qbinders[ j ] = (Vector) varAt.get( new Integer( j ) );
}
varAt.clear(); // clean up
}
public NondetWordAutom automatonFrom( Tree pat, Integer finalTag ) {
this.finalTag = finalTag ;
//System.out.println( "enter automatonFrom("+ pat +")");
switch( pat ) {
case Sequence( Tree[] subexpr ):
initialize( subexpr );
// (1) compute first + follow;
++pos;
globalFirst = compFollow( subexpr );
initializeAutom(); // explicit representation
collectTransitions();
NondetWordAutom result =
new NondetWordAutom(pos, // = nstates
labels,
initials,
finals,
deltaq,
defaultq,
(Object) qbinders);
result.leftTrans = true;
TreeSet revInitials = new TreeSet( finals.keySet() );
/*
pos++; // adding a state
HashSet deltaqRev2[] = new HashSet[ deltaqRev.length + 1];
HashSet defaultqRev2[] = new HashSet[ deltaqRev.length + 1];
HashSet qbinders[] = new HashSet[ deltaqRev.length + 1];
for(Iterator it = finals.keySet().iterator(); it.hasNext(); ) {
}
*/
TreeMap revFinals = new TreeMap();
for(Iterator it = initials.iterator(); it.hasNext(); ) {
revFinals.put( it.next(), finalTag);
}
revnfa = new NondetWordAutom(pos,
labels,
revInitials,
revFinals,
deltaqRev,
defaultqRev,
(Object) qbinders);
revnfa.rightTrans = true;
/*
System.out.println("inBerrySethi");
XMLAutomPrinter pr = new XMLAutomPrinter( System.out );
pr.begin();
pr.print( result );
pr.print( revnfa );
pr.end();
System.out.println("initialsRev = "+initialsRev);
System.out.println("outBerrySethi");
*/
//System.exit(0);
return result; //print();
}
throw new ApplicationError("expected a sequence pattern");
}
}
|