001: package antlr;
002:
003: /* ANTLR Translator Generator
004: * Project led by Terence Parr at http://www.cs.usfca.edu
005: * Software rights: http://www.antlr.org/license.html
006: */
007:
008: import antlr.collections.impl.BitSet;
009: import antlr.collections.impl.Vector;
010:
011: /**This object holds all information needed to represent
012: * the lookahead for any particular lookahead computation
013: * for a <b>single</b> lookahead depth. Final lookahead
014: * information is a simple bit set, but intermediate
015: * stages need computation cycle and FOLLOW information.
016: *
017: * <p>
018: * Concerning the <tt>cycle</tt> variable.
019: * If lookahead is computed for a RuleEnd node, then
020: * computation is part of a FOLLOW cycle for this rule.
021: * If lookahead is computed for a RuleBlock node, the
022: * computation is part of a FIRST cycle to this rule.
023: *
024: * <p>
025: * Concerning the <tt>epsilonDepth</tt> variable.
026: * This is not the depth relative to the rule reference
027: * that epsilon was encountered. That value is
028: * <pre>
029: * initial_k - epsilonDepth + 1
030: * </pre>
031: * Also, lookahead depths past rule ref for local follow are:
032: * <pre>
033: * initial_k - (initial_k - epsilonDepth)
034: * </pre>
035: * Used for rule references. If we try
036: * to compute look(k, ruleref) and there are fewer
037: * than k lookahead terminals before the end of the
038: * the rule, epsilon will be returned (don't want to
039: * pass the end of the rule). We must track when the
040: * the lookahead got stuck. For example,
041: * <pre>
042: * a : b A B E F G;
043: * b : C ;
044: * </pre>
045: * LOOK(5, ref-to(b)) is {<EPSILON>} with depth = 4, which
046: * indicates that at 2 (5-4+1) tokens ahead, end of rule was reached.
047: * Therefore, the token at 4=5-(5-4) past rule ref b must be
048: * included in the set == F.
049: * The situation is complicated by the fact that a computation
050: * may hit the end of a rule at many different depths. For example,
051: * <pre>
052: * a : b A B C ;
053: * b : E F // epsilon depth of 1 relative to initial k=3
054: * | G // epsilon depth of 2
055: * ;
056: * </pre>
057: * Here, LOOK(3,ref-to(b)) returns epsilon, but the depths are
058: * {1, 2}; i.e., 3-(3-1) and 3-(3-2). Those are the lookahead depths
059: * past the rule ref needed for the local follow.
060: *
061: * <p>
062: * This is null unless an epsilon is created.
063: *
064: * @see antlr.Lookahead#combineWith(Lookahead)
065: */
066: public class Lookahead implements Cloneable {
067: /** actual bitset of the lookahead */
068: BitSet fset;
069: /** is this computation part of a computation cycle? */
070: String cycle;
071: /** What k values were being computed when end of rule hit? */
072: BitSet epsilonDepth;
073: /** Does this lookahead depth include Epsilon token type? This
074: * is used to avoid having a bit in the set for Epsilon as it
075: * conflicts with parsing binary files.
076: */
077: boolean hasEpsilon = false;
078:
079: public Lookahead() {
080: fset = new BitSet();
081: }
082:
083: /** create a new lookahead set with the LL(1) set to the parameter */
084: public Lookahead(BitSet p) {
085: fset = p;
086: }
087:
088: /** create an empty lookahead set, but with cycle */
089: public Lookahead(String c) {
090: this ();
091: cycle = c;
092: }
093:
094: /** Make a deep copy of everything in this object */
095: public Object clone() {
096: Lookahead p = null;
097: try {
098: p = (Lookahead) super .clone();
099: p.fset = (BitSet) fset.clone();
100: p.cycle = cycle; // strings are immutable
101: if (epsilonDepth != null) {
102: p.epsilonDepth = (BitSet) epsilonDepth.clone();
103: }
104: } catch (CloneNotSupportedException e) {
105: throw new InternalError();
106: }
107: return p;
108: }
109:
110: public void combineWith(Lookahead q) {
111: if (cycle == null) { // track at least one cycle
112: cycle = q.cycle;
113: }
114:
115: if (q.containsEpsilon()) {
116: hasEpsilon = true;
117: }
118:
119: // combine epsilon depths
120: if (epsilonDepth != null) {
121: if (q.epsilonDepth != null) {
122: epsilonDepth.orInPlace(q.epsilonDepth);
123: }
124: } else if (q.epsilonDepth != null) {
125: epsilonDepth = (BitSet) q.epsilonDepth.clone();
126: }
127: fset.orInPlace(q.fset);
128: }
129:
130: public boolean containsEpsilon() {
131: return hasEpsilon;
132: }
133:
134: /** What is the intersection of two lookahead depths?
135: * Only the Epsilon "bit" and bitset are considered.
136: */
137: public Lookahead intersection(Lookahead q) {
138: Lookahead p = new Lookahead(fset.and(q.fset));
139: if (this .hasEpsilon && q.hasEpsilon) {
140: p.setEpsilon();
141: }
142: return p;
143: }
144:
145: public boolean nil() {
146: return fset.nil() && !hasEpsilon;
147: }
148:
149: public static Lookahead of(int el) {
150: Lookahead look = new Lookahead();
151: look.fset.add(el);
152: return look;
153: }
154:
155: public void resetEpsilon() {
156: hasEpsilon = false;
157: }
158:
159: public void setEpsilon() {
160: hasEpsilon = true;
161: }
162:
163: public String toString() {
164: String e = "", b, f = "", d = "";
165: b = fset.toString(",");
166: if (containsEpsilon()) {
167: e = "+<epsilon>";
168: }
169: if (cycle != null) {
170: f = "; FOLLOW(" + cycle + ")";
171: }
172: if (epsilonDepth != null) {
173: d = "; depths=" + epsilonDepth.toString(",");
174: }
175: return b + e + f + d;
176:
177: }
178:
179: public String toString(String separator, CharFormatter formatter) {
180: String e = "", b, f = "", d = "";
181: b = fset.toString(separator, formatter);
182: if (containsEpsilon()) {
183: e = "+<epsilon>";
184: }
185: if (cycle != null) {
186: f = "; FOLLOW(" + cycle + ")";
187: }
188: if (epsilonDepth != null) {
189: d = "; depths=" + epsilonDepth.toString(",");
190: }
191: return b + e + f + d;
192: }
193:
194: public String toString(String separator, CharFormatter formatter,
195: Grammar g) {
196: if (g instanceof LexerGrammar) {
197: return toString(separator, formatter);
198: } else {
199: return toString(separator, g.tokenManager.getVocabulary());
200: }
201: }
202:
203: public String toString(String separator, Vector vocab) {
204: String b, f = "", d = "";
205: b = fset.toString(separator, vocab);
206: if (cycle != null) {
207: f = "; FOLLOW(" + cycle + ")";
208: }
209: if (epsilonDepth != null) {
210: d = "; depths=" + epsilonDepth.toString(",");
211: }
212: return b + f + d;
213: }
214: }
|