public Class DFA

Walk all accept states and find the manually-specified synpreds. Gated preds are not always hoisted I used to do this in the code generator, but that is too late. This converter tries to avoid computing DFA for decisions in syntactic predicates that are not ever used such as those created by autobacktrack mode.

What GrammarAST node (derived from the grammar) is this DFA associated with? It will point to the start of a block or the loop back of a (...)+ block etc...

Return k if decision is LL(k) for some k else return max int

What is the max state number ever created? This may be beyond getNumberOfStates().

Compress the incoming data list so that runs of same number are encoded as number,value pair sequences. 3 -1 -1 -1 28 is encoded as 1 3 3 -1 1 28. I am pretty sure this is the lossless compression that GIF files use. Transition tables are heavily compressed by this technique. I got the idea from JFlex http://jflex.de/ Return List<String> where each string is either \xyz for 8bit char and ￿ for 16bit. Hideous and specific to Java, but it is the only target bad enough to need it.

Return a list of Integer alt numbers for which no lookahead could be computed or for which no single DFA accept state predicts those alts. Must call verify() first before this makes sense.

The user may specify a max, acyclic lookahead for any decision. No DFA cycles are created when this value, k, is greater than 0. If this decision has no k lookahead specified, then try the grammar.

Compute cyclic w/o relying on state computed during analysis. just check.

Count all disambiguating syn preds (ignore synpred tests for gated edges, which occur for nonambig input sequences). E.g., x : (X)=> (X|Y)\n" + | X\n" + ; gives .s0-X->.s1 .s0-Y&&{synpred1_t}?->:s2=>1 .s1-{synpred1_t}?->:s2=>1 .s1-{true}?->:s3=>2

Is this DFA cyclic? That is, are there any loops? If not, then the DFA is essentially an LL(k) predictor for some fixed, max k value. We can build a series of nested IF statements to match this. In the presence of cycles, we need to build a general DFA and interpret it to distinguish between alternatives.

Is the DFA reduced? I.e., does every state have a path to an accept state? If not, don't delete as we need to generate an error indicating which paths are "dead ends". Also tracks list of alts with no accept state in the DFA. Must call verify() first before this makes sense.

Is this DFA derived from the NFA for the Tokens rule?

If this DFA failed to finish during construction, we might be able to retry with k=1 but we need to know whether it will potentially succeed. Can only succeed if there is a predicate to resolve the issue. Don't try if k=1 already as it would cycle forever. Timeout can retry with k=1 even if no predicate if k!=1.

Walk all states and reset their numbers to be a contiguous sequence of integers starting from 0. Only cyclic DFA can have unused positions in states list. State i might be identical to a previous state j and will result in states[i] == states[j]. We don't want to waste a state number on this. Useful mostly for code generation in tables. At the start of this routine, states[i].stateNumber <= i by definition. If states[50].stateNumber is 50 then a cycle during conversion may try to add state 103, but we find that an identical DFA state, named 50, already exists, hence, states[103]==states[50] and both have stateNumber 50 as they point at same object. Afterwards, the set of state numbers from all states should represent a contiguous range from 0..n-1 where n is the number of unique states.

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object

Annotations

@Override

Once this DFA has been built, need to verify that: 1. it's reduced 2. all alts have an accept state Elsewhere, in the NFA converter, we need to verify that: 3. alts i and j have disjoint lookahead if no sem preds 4. if sem preds, nondeterministic alts must be sufficiently covered This is avoided if analysis bails out for any reason.