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