KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > antlr > Lookahead


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