1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
3 package edu.berkeley.sbp;
4 import edu.berkeley.sbp.*;
5 import edu.berkeley.sbp.util.*;
6 import edu.berkeley.sbp.Sequence.Position;
9 import java.lang.reflect.*;
10 import java.lang.ref.*;
12 /** a traversal of the grammar performed by mapping from SequenceOrElements to a lattice and computing the resulting LUB */
13 abstract class Walk<T> {
14 protected HashSet<SequenceOrElement> acc = new HashSet<SequenceOrElement>();
15 protected abstract T bottom(SequenceOrElement e);
17 protected final Cache c;
18 public Walk() { this(null); }
19 public Walk(Cache c) { this.c = c; }
21 public T walkSequence(Sequence s) {
23 for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
24 ret = sequence(s, ret, walk(p.element()));
28 public T walkAtom(Atom r) { return walk(r); }
29 public T union(Union u, T a, T b) { return bottom(u); }
30 public T sequence(Sequence s, T a, T b) { return bottom(s); }
31 protected T walk(SequenceOrElement e) {
32 if (acc.contains(e)) return bottom(e);
37 protected T walk2(SequenceOrElement e) {
38 if (e instanceof Atom) return walkAtom((Atom)e);
39 else if (e instanceof Sequence) return walkSequence((Sequence)e);
40 else if (e instanceof Union) {
42 for(Sequence s : (Union)e) {
43 ret = union((Union)e, ret, walk(s));
46 for(Sequence ss : s.needs()) ret = union((Union)e, ret, walk(ss));
47 for(Sequence ss : s.hates()) ret = union((Union)e, ret, walk(ss));
51 throw new Error("unknown element of class " + e.getClass().getName() + ": " + e);
55 static class YieldSet extends Walk<HashSet<SequenceOrElement>> {
56 private final SequenceOrElement e;
57 public final HashSet<SequenceOrElement> walk() { return walk(e); }
58 public YieldSet(SequenceOrElement e, Cache c) { super(c); this.e = e; }
59 public HashSet<SequenceOrElement> bottom(SequenceOrElement e) { return acc; }
60 public HashSet<SequenceOrElement> walkSequence(Sequence seq) { return bottom(seq); }
61 public HashSet<SequenceOrElement> walkAtom(Atom r) {
62 c.atoms.put(e, c.atoms.get(e)==null ? r : c.atoms.get(e).union(r));
63 return super.walkAtom(r);
68 // Boolean //////////////////////////////////////////////////////////////////////////////
70 static class PossiblyEpsilon extends Walk<Boolean> {
71 public Boolean walkAtom(Atom r) { return false; }
72 public Boolean sequence(Sequence s, Boolean a, Boolean b) { return new Boolean(a && b); }
73 public Boolean union(Union u, Boolean a, Boolean b) { return new Boolean(a || b); }
74 public Boolean bottom(SequenceOrElement e) { return (e instanceof Union) ? false : true; }
75 private HashMap<SequenceOrElement,Boolean> hm = new HashMap<SequenceOrElement,Boolean>();
76 protected Boolean walk(SequenceOrElement e) {
77 if (hm.get(e) != null) return hm.get(e);
79 Boolean ret = walk2(e);
86 // Input-Set //////////////////////////////////////////////////////////////////////////////
88 static abstract class WalkTokenSet<Tok extends Input> extends Walk<Topology<Tok>> {
89 public Topology<Tok> cs;
90 public WalkTokenSet(Topology<Tok> cs) { this.cs = cs; }
91 public WalkTokenSet(Topology<Tok> cs, Cache c) { super(c); this.cs = cs; }
92 public Topology<Tok> bottom(SequenceOrElement e) { return cs; }
93 public Topology<Tok> walkAtom(Atom r) { cs = cs.union(r.getTokenTopology()); return cs; }
96 static class First<Tok extends Input> extends WalkTokenSet<Tok> {
97 public First(Topology<Tok> cs, Walk.Cache cache) { super(cs, cache); }
98 public Topology<Tok> walkSequence(Sequence seq) {
99 for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
101 if (!c.possiblyEpsilon(p.element())) break;
107 static class Follow<Tok extends Input> extends WalkTokenSet<Tok> {
108 private final SequenceOrElement me;
109 private final HashSet<SequenceOrElement> all;
110 private boolean eof = false;
111 public boolean includesEof() { return eof; }
112 public Follow(Topology<Tok> cs, SequenceOrElement me, HashSet<SequenceOrElement> all, Cache c) {
113 super(cs, c); this.me = me; this.all = all; }
114 public Topology<Tok> bottom(SequenceOrElement e) { return cs; }
115 public Topology<Tok> walkSequence(Sequence seq) { return cs; }
116 public Topology<Tok> walkAtom(Atom r) { return walk((SequenceOrElement)r); }
117 public Topology<Tok> walk(SequenceOrElement e) {
118 if (acc.contains(e)) return bottom(e);
122 Topology<Tok> cached = (Topology<Tok>)c.follow.get(e);
123 if (cached != null) {
124 cs = cs.union(cached);
130 Topology<Tok> cso = cs;
132 eof = c.eof.get(e) != null && c.eof.get(e).booleanValue();
135 for(SequenceOrElement x : all) {
136 boolean matched = false;
137 if (!(x instanceof Sequence)) continue;
138 Sequence a = (Sequence)x;
140 for(Position pos = a.firstp(); pos != null && !pos.isLast(); pos = pos.next()) {
141 if (matched) cs = cs.union(c.first(pos.element(), cs.empty()));
142 if (pos.isLast()) { matched = (matched && c.possiblyEpsilon(pos.element())); continue; }
143 boolean good = false;
144 if (e instanceof Atom) {
145 Topology top = c.atoms.get(pos.element());
146 if (top==null) continue;
147 if (!(top.containsAll(((Atom)e)))) continue;
149 if (c.ys.contains(pos.element(),e)) good = true;
156 if (matched) walk(a);
159 if (e instanceof Sequence) {
160 Sequence s = (Sequence)e;
161 if (s.follow != null) cs = cs.intersect(s.follow.getTokenTopology());
164 if (c != null && e==me) {
179 public final HashMap<SequenceOrElement,Boolean> possiblyEpsilon = new HashMap<SequenceOrElement,Boolean>();
180 public HashMap<SequenceOrElement,Boolean> eof = new HashMap<SequenceOrElement,Boolean>();
181 public HashMap<SequenceOrElement,Topology> follow = new HashMap<SequenceOrElement,Topology>();
182 public HashMapBag<SequenceOrElement,SequenceOrElement> ys = new HashMapBag<SequenceOrElement,SequenceOrElement>();
183 public HashMap<SequenceOrElement,Topology> atoms = new HashMap<SequenceOrElement,Topology>();
184 public <Tok extends Input> Topology<Tok> first(SequenceOrElement e, Topology<Tok> empty) {
185 return new Walk.First<Tok>(empty, this).walk(e);
187 final boolean possiblyEpsilon(SequenceOrElement e) {
188 Walk.Cache cache = this;
189 Boolean ret = possiblyEpsilon.get(e);
190 if (ret != null) return ret.booleanValue();
191 ret = new Walk.PossiblyEpsilon().walk(e) ? Boolean.TRUE : Boolean.FALSE;
192 possiblyEpsilon.put(e, ret);