package antlr;
/* ANTLR Translator Generator
* Project led by Terence Parr at http://www.cs.usfca.edu
* Software rights: http://www.antlr.org/license.html
*
* $Id: //depot/code/org.antlr/release/antlr-2.7.7/antlr/Lookahead.java#2 $
*/
import antlr.collections.impl.
BitSet;
import antlr.collections.impl.
Vector;
/**This object holds all information needed to represent
* the lookahead for any particular lookahead computation
* for a <b>single</b> lookahead depth. Final lookahead
* information is a simple bit set, but intermediate
* stages need computation cycle and FOLLOW information.
*
* <p>
* Concerning the <tt>cycle</tt> variable.
* If lookahead is computed for a RuleEnd node, then
* computation is part of a FOLLOW cycle for this rule.
* If lookahead is computed for a RuleBlock node, the
* computation is part of a FIRST cycle to this rule.
*
* <p>
* Concerning the <tt>epsilonDepth</tt> variable.
* This is not the depth relative to the rule reference
* that epsilon was encountered. That value is
* <pre>
* initial_k - epsilonDepth + 1
* </pre>
* Also, lookahead depths past rule ref for local follow are:
* <pre>
* initial_k - (initial_k - epsilonDepth)
* </pre>
* Used for rule references. If we try
* to compute look(k, ruleref) and there are fewer
* than k lookahead terminals before the end of the
* the rule, epsilon will be returned (don't want to
* pass the end of the rule). We must track when the
* the lookahead got stuck. For example,
* <pre>
* a : b A B E F G;
* b : C ;
* </pre>
* LOOK(5, ref-to(b)) is {<EPSILON>} with depth = 4, which
* indicates that at 2 (5-4+1) tokens ahead, end of rule was reached.
* Therefore, the token at 4=5-(5-4) past rule ref b must be
* included in the set == F.
* The situation is complicated by the fact that a computation
* may hit the end of a rule at many different depths. For example,
* <pre>
* a : b A B C ;
* b : E F // epsilon depth of 1 relative to initial k=3
* | G // epsilon depth of 2
* ;
* </pre>
* Here, LOOK(3,ref-to(b)) returns epsilon, but the depths are
* {1, 2}; i.e., 3-(3-1) and 3-(3-2). Those are the lookahead depths
* past the rule ref needed for the local follow.
*
* <p>
* This is null unless an epsilon is created.
*
* @see antlr.Lookahead#combineWith(Lookahead)
*/
public class
Lookahead implements
Cloneable {
/** actual bitset of the lookahead */
BitSet fset;
/** is this computation part of a computation cycle? */
String cycle;
/** What k values were being computed when end of rule hit? */
BitSet epsilonDepth;
/** Does this lookahead depth include Epsilon token type? This
* is used to avoid having a bit in the set for Epsilon as it
* conflicts with parsing binary files.
*/
boolean
hasEpsilon = false;
public
Lookahead() {
fset = new
BitSet();
}
/** create a new lookahead set with the LL(1) set to the parameter */
public
Lookahead(
BitSet p) {
fset =
p;
}
/** create an empty lookahead set, but with cycle */
public
Lookahead(
String c) {
this();
cycle =
c;
}
/** Make a deep copy of everything in this object */
public
Object clone() {
Lookahead p = null;
try {
p = (
Lookahead)super.clone();
p.
fset = (
BitSet)
fset.
clone();
p.
cycle =
cycle; // strings are immutable
if (
epsilonDepth != null) {
p.
epsilonDepth = (
BitSet)
epsilonDepth.
clone();
}
}
catch (
CloneNotSupportedException e) {
throw new
InternalError();
}
return
p;
}
public void
combineWith(
Lookahead q) {
if (
cycle == null) { // track at least one cycle
cycle =
q.
cycle;
}
if (
q.
containsEpsilon()) {
hasEpsilon = true;
}
// combine epsilon depths
if (
epsilonDepth != null) {
if (
q.
epsilonDepth != null) {
epsilonDepth.
orInPlace(
q.
epsilonDepth);
}
}
else if (
q.
epsilonDepth != null) {
epsilonDepth = (
BitSet)
q.
epsilonDepth.
clone();
}
fset.
orInPlace(
q.
fset);
}
public boolean
containsEpsilon() {
return
hasEpsilon;
}
/** What is the intersection of two lookahead depths?
* Only the Epsilon "bit" and bitset are considered.
*/
public
Lookahead intersection(
Lookahead q) {
Lookahead p = new
Lookahead(
fset.
and(
q.
fset));
if (this.
hasEpsilon &&
q.
hasEpsilon) {
p.
setEpsilon();
}
return
p;
}
public boolean
nil() {
return
fset.
nil() && !
hasEpsilon;
}
public static
Lookahead of(int
el) {
Lookahead look = new
Lookahead();
look.
fset.
add(
el);
return
look;
}
public void
resetEpsilon() {
hasEpsilon = false;
}
public void
setEpsilon() {
hasEpsilon = true;
}
public
String toString() {
String e = "",
b,
f = "",
d = "";
b =
fset.
toString(",");
if (
containsEpsilon()) {
e = "+<epsilon>";
}
if (
cycle != null) {
f = "; FOLLOW(" +
cycle + ")";
}
if (
epsilonDepth != null) {
d = "; depths=" +
epsilonDepth.
toString(",");
}
return
b +
e +
f +
d;
}
public
String toString(
String separator,
CharFormatter formatter) {
String e = "",
b,
f = "",
d = "";
b =
fset.
toString(
separator,
formatter);
if (
containsEpsilon()) {
e = "+<epsilon>";
}
if (
cycle != null) {
f = "; FOLLOW(" +
cycle + ")";
}
if (
epsilonDepth != null) {
d = "; depths=" +
epsilonDepth.
toString(",");
}
return
b +
e +
f +
d;
}
public
String toString(
String separator,
CharFormatter formatter,
Grammar g) {
if (
g instanceof
LexerGrammar) {
return
toString(
separator,
formatter);
}
else {
return
toString(
separator,
g.
tokenManager.
getVocabulary());
}
}
public
String toString(
String separator,
Vector vocab) {
String b,
f = "",
d = "";
b =
fset.
toString(
separator,
vocab);
if (
cycle != null) {
f = "; FOLLOW(" +
cycle + ")";
}
if (
epsilonDepth != null) {
d = "; depths=" +
epsilonDepth.
toString(",");
}
return
b +
f +
d;
}
}