KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > persistence > antlr > Lookahead


1 package persistence.antlr;
2
3 /* ANTLR Translator Generator
4  * Project led by Terence Parr at http://www.jGuru.com
5  * Software rights: http://www.antlr.org/license.html
6  *
7  */
8
9 import persistence.antlr.collections.impl.BitSet;
10 import persistence.antlr.collections.impl.Vector;
11
12 /**This object holds all information needed to represent
13  * the lookahead for any particular lookahead computation
14  * for a <b>single</b> lookahead depth. Final lookahead
15  * information is a simple bit set, but intermediate
16  * stages need computation cycle and FOLLOW information.
17  *
18  * <p>
19  * Concerning the <tt>cycle</tt> variable.
20  * If lookahead is computed for a RuleEnd node, then
21  * computation is part of a FOLLOW cycle for this rule.
22  * If lookahead is computed for a RuleBlock node, the
23  * computation is part of a FIRST cycle to this rule.
24  *
25  * <p>
26  * Concerning the <tt>epsilonDepth</tt> variable.
27  * This is not the depth relative to the rule reference
28  * that epsilon was encountered. That value is
29  * <pre>
30  * initial_k - epsilonDepth + 1
31  * </pre>
32  * Also, lookahead depths past rule ref for local follow are:
33  * <pre>
34  * initial_k - (initial_k - epsilonDepth)
35  * </pre>
36  * Used for rule references. If we try
37  * to compute look(k, ruleref) and there are fewer
38  * than k lookahead terminals before the end of the
39  * the rule, epsilon will be returned (don't want to
40  * pass the end of the rule). We must track when the
41  * the lookahead got stuck. For example,
42  * <pre>
43  * a : b A B E F G;
44  * b : C ;
45  * </pre>
46  * LOOK(5, ref-to(b)) is {<EPSILON>} with depth = 4, which
47  * indicates that at 2 (5-4+1) tokens ahead, end of rule was reached.
48  * Therefore, the token at 4=5-(5-4) past rule ref b must be
49  * included in the set == F.
50  * The situation is complicated by the fact that a computation
51  * may hit the end of a rule at many different depths. For example,
52  * <pre>
53  * a : b A B C ;
54  * b : E F // epsilon depth of 1 relative to initial k=3
55  * | G // epsilon depth of 2
56  * ;
57  * </pre>
58  * Here, LOOK(3,ref-to(b)) returns epsilon, but the depths are
59  * {1, 2}; i.e., 3-(3-1) and 3-(3-2). Those are the lookahead depths
60  * past the rule ref needed for the local follow.
61  *
62  * <p>
63  * This is null unless an epsilon is created.
64  *
65  * @see persistence.antlr.Lookahead#combineWith(Lookahead)
66  */
67 public class Lookahead implements Cloneable JavaDoc {
68     /** actual bitset of the lookahead */
69     BitSet fset;
70     /** is this computation part of a computation cycle? */
71     String JavaDoc cycle;
72     /** What k values were being computed when end of rule hit? */
73     BitSet epsilonDepth;
74     /** Does this lookahead depth include Epsilon token type? This
75      * is used to avoid having a bit in the set for Epsilon as it
76      * conflicts with parsing binary files.
77      */
78     boolean hasEpsilon = false;
79
80     public Lookahead() {
81         fset = new BitSet();
82     }
83
84     /** create a new lookahead set with the LL(1) set to the parameter */
85     public Lookahead(BitSet p) {
86         fset = p;
87     }
88
89     /** create an empty lookahead set, but with cycle */
90     public Lookahead(String JavaDoc c) {
91         this();
92         cycle = c;
93     }
94
95     /** Make a deep copy of everything in this object */
96     public Object JavaDoc clone() {
97         Lookahead p = null;
98         try {
99             p = (Lookahead)super.clone();
100             p.fset = (BitSet)fset.clone();
101             p.cycle = cycle; // strings are immutable
102 if (epsilonDepth != null) {
103                 p.epsilonDepth = (BitSet)epsilonDepth.clone();
104             }
105         }
106         catch (CloneNotSupportedException JavaDoc e) {
107             throw new InternalError JavaDoc();
108         }
109         return p;
110     }
111
112     public void combineWith(Lookahead q) {
113         if (cycle == null) { // track at least one cycle
114 cycle = q.cycle;
115         }
116
117         if (q.containsEpsilon()) {
118             hasEpsilon = true;
119         }
120
121         // combine epsilon depths
122 if (epsilonDepth != null) {
123             if (q.epsilonDepth != null) {
124                 epsilonDepth.orInPlace(q.epsilonDepth);
125             }
126         }
127         else if (q.epsilonDepth != null) {
128             epsilonDepth = (BitSet)q.epsilonDepth.clone();
129         }
130         fset.orInPlace(q.fset);
131     }
132
133     public boolean containsEpsilon() {
134         return hasEpsilon;
135     }
136
137     /** What is the intersection of two lookahead depths?
138      * Only the Epsilon "bit" and bitset are considered.
139      */
140     public Lookahead intersection(Lookahead q) {
141         Lookahead p = new Lookahead(fset.and(q.fset));
142         if (this.hasEpsilon && q.hasEpsilon) {
143             p.setEpsilon();
144         }
145         return p;
146     }
147
148     public boolean nil() {
149         return fset.nil() && !hasEpsilon;
150     }
151
152     public static Lookahead of(int el) {
153         Lookahead look = new Lookahead();
154         look.fset.add(el);
155         return look;
156     }
157
158     public void resetEpsilon() {
159         hasEpsilon = false;
160     }
161
162     public void setEpsilon() {
163         hasEpsilon = true;
164     }
165
166     public String JavaDoc toString() {
167         String JavaDoc e = "",b,f = "",d = "";
168         b = fset.toString(",");
169         if (containsEpsilon()) {
170             e = "+<epsilon>";
171         }
172         if (cycle != null) {
173             f = "; FOLLOW(" + cycle + ")";
174         }
175         if (epsilonDepth != null) {
176             d = "; depths=" + epsilonDepth.toString(",");
177         }
178         return b + e + f + d;
179
180     }
181
182     public String JavaDoc toString(String JavaDoc separator, CharFormatter formatter) {
183         String JavaDoc e = "",b,f = "",d = "";
184         b = fset.toString(separator, formatter);
185         if (containsEpsilon()) {
186             e = "+<epsilon>";
187         }
188         if (cycle != null) {
189             f = "; FOLLOW(" + cycle + ")";
190         }
191         if (epsilonDepth != null) {
192             d = "; depths=" + epsilonDepth.toString(",");
193         }
194         return b + e + f + d;
195     }
196
197     public String JavaDoc toString(String JavaDoc separator, CharFormatter formatter, Grammar g) {
198         if (g instanceof LexerGrammar) {
199             return toString(separator, formatter);
200         }
201         else {
202             return toString(separator, g.tokenManager.getVocabulary());
203         }
204     }
205
206     public String JavaDoc toString(String JavaDoc separator, Vector vocab) {
207         String JavaDoc b,f = "",d = "";
208         b = fset.toString(separator, vocab);
209         if (cycle != null) {
210             f = "; FOLLOW(" + cycle + ")";
211         }
212         if (epsilonDepth != null) {
213             d = "; depths=" + epsilonDepth.toString(",");
214         }
215         return b + f + d;
216     }
217 }
218
Popular Tags