| java.lang.Object
 org.antlr.analysis.NFAContext
| NFAContext | | public class NFAContext (Code) | | A tree node for tracking the call chains for NFAs that invoke
other NFAs. These trees only have to point upwards to their parents
so we can walk back up the tree (i.e., pop stuff off the stack). We
never walk from stack down down through the children.
Each alt predicted in a decision has its own context tree,
representing all possible return nodes. The initial stack has
EOF ("$") in it. So, for m alternative productions, the lookahead
DFA will have m NFAContext trees.
To "push" a new context, just do "new NFAContext(context-parent, state)"
which will add itself to the parent. The root is NFAContext(null, null).
The complete context for an NFA configuration is the set of invoking states
on the path from this node thru the parent pointers to the root.
|
| Field Summary | |
| public static int | MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK
This is similar to Bermudez's m constant in his LAR(m) where
you bound the stack so your states don't explode. | | protected int | cachedHashCode
Computing the hashCode is very expensive and closureBusy()
uses it to track when it's seen a state|ctx before to avoid
infinite loops. | | public NFAState | invokingState
The NFA state that invoked another rule's start state is recorded
on the rule invocation context stack. | | public NFAContext | parent
|
| Method Summary | |
| public boolean | conflictsWith(NFAContext other)
Two contexts conflict() if they are equals() or one is a stack suffix
of the other. | | public boolean | equals(Object o)
Two contexts are equals() if both have
same call stack; walk upwards to the root.
Recall that the root sentinel node has no invokingStates and no parent.
Note that you may be comparing contexts in different alt trees.
The hashCode is now cheap as it's computed once upon each context
push on the stack. | | public int | hashCode()
| | public boolean | isEmpty()
A context is empty if there is no parent; meaning nobody pushed
anything on the call stack. | | public int | recursionDepthEmanatingFromState(int state)
Given an NFA state number, how many times has the NFA-to-DFA
conversion pushed that state on the stack? In other words,
the NFA state must be a rule invocation state and this method
tells you how many times you've been to this state. | | protected boolean | suffix(NFAContext other)
[$] suffix any context
[21 $] suffix [21 12 $]
[21 12 $] suffix [21 $]
[21 18 $] suffix [21 18 12 9 $]
[21 18 12 9 $] suffix [21 18 $]
[21 12 $] not suffix [21 9 $]
Example "[21 $] suffix [21 12 $]" means: rule r invoked current rule
from state 21. | | public String | toString()
|
| MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK | | public static int MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK(Code) | | This is similar to Bermudez's m constant in his LAR(m) where
you bound the stack so your states don't explode. The main difference
is that I bound only recursion on the stack, not the simple stack size.
This looser constraint will let the conversion roam further to find
lookahead to resolve a decision.
Bermudez's m operates differently as it is his LR stack depth
I'm pretty sure it therefore includes all stack symbols. Here I
restrict the size of an NFA configuration to be finite because a
stack component may mention the same NFA invocation state at
most m times. Hence, the number of DFA states will not grow forever.
With recursive rules like
e : '(' e ')' | INT ;
you could chase your tail forever if somebody said "s : e '.' | e ';' ;"
This constant prevents new states from being created after a stack gets
"too big".
Imagine doing a depth-first search on the DFA...as you chase an input
sequence you can recurse to same rule such as e above. You'd have a
chain of ((((. When you get do some point, you have to give up. The
states in the chain will have longer and longer NFA config stacks.
Must limit size.
TODO: i wonder if we can recognize recursive loops and use a simple cycle?
max=0 implies you cannot ever jump to another rule during closure.
max=1 implies you can make as many calls as you want--you just
can't ever visit a state that is on your rule invocation stack.
I.e., you cannot ever recurse.
max=2 implies you are able to recurse once (i.e., call a rule twice
from the same place).
This tracks recursion to a rule specific to an invocation site!
It does not detect multiple calls to a rule from different rule
invocation states. We are guaranteed to terminate because the
stack can only grow as big as the number of NFA states * max.
I noticed that the Java grammar didn't work with max=1, but did with
max=4. Let's set to 4. Recursion is sometimes needed to resolve some
fixed lookahead decisions.
|
| cachedHashCode | | protected int cachedHashCode(Code) | | Computing the hashCode is very expensive and closureBusy()
uses it to track when it's seen a state|ctx before to avoid
infinite loops. As we add new contexts, record the hash code
as this.invokingState + parent.cachedHashCode. Avoids walking
up the tree for every hashCode(). Note that this caching works
because a context is a monotonically growing tree of context nodes
and nothing on the stack is ever modified...ctx just grows
or shrinks.
|
| invokingState | | public NFAState invokingState(Code) | | The NFA state that invoked another rule's start state is recorded
on the rule invocation context stack.
|
| conflictsWith | | public boolean conflictsWith(NFAContext other)(Code) | | Two contexts conflict() if they are equals() or one is a stack suffix
of the other. For example, contexts [21 12 $] and [21 9 $] do not
conflict, but [21 $] and [21 12 $] do conflict. Note that I should
probably not show the $ in this case. There is a dummy node for each
stack that just means empty; $ is a marker that's all.
This is used in relation to checking conflicts associated with a
single NFA state's configurations within a single DFA state.
If there are configurations s and t within a DFA state such that
s.state=t.state && s.alt != t.alt && s.ctx conflicts t.ctx then
the DFA state predicts more than a single alt--it's nondeterministic.
Two contexts conflict if they are the same or if one is a suffix
of the other.
When comparing contexts, if one context has a stack and the other
does not then they should be considered the same context. The only
way for an NFA state p to have an empty context and a nonempty context
is the case when closure falls off end of rule without a call stack
and re-enters the rule with a context. This resolves the issue I
discussed with Sriram Srinivasan Feb 28, 2005 about not terminating
fast enough upon nondeterminism.
|
| equals | | public boolean equals(Object o)(Code) | | Two contexts are equals() if both have
same call stack; walk upwards to the root.
Recall that the root sentinel node has no invokingStates and no parent.
Note that you may be comparing contexts in different alt trees.
The hashCode is now cheap as it's computed once upon each context
push on the stack. Use it to make equals() more efficient.
|
| hashCode | | public int hashCode()(Code) | | |
| isEmpty | | public boolean isEmpty()(Code) | | A context is empty if there is no parent; meaning nobody pushed
anything on the call stack.
|
| recursionDepthEmanatingFromState | | public int recursionDepthEmanatingFromState(int state)(Code) | | Given an NFA state number, how many times has the NFA-to-DFA
conversion pushed that state on the stack? In other words,
the NFA state must be a rule invocation state and this method
tells you how many times you've been to this state. If none,
then you have not called the target rule from this state before
(though another NFA state could have called that target rule).
If n=1, then you've been to this state before during this
DFA construction and are going to invoke that rule again.
Note that many NFA states can invoke rule r, but we ignore recursion
unless you hit the same rule invocation state again.
|
| suffix | | protected boolean suffix(NFAContext other)(Code) | | [$] suffix any context
[21 $] suffix [21 12 $]
[21 12 $] suffix [21 $]
[21 18 $] suffix [21 18 12 9 $]
[21 18 12 9 $] suffix [21 18 $]
[21 12 $] not suffix [21 9 $]
Example "[21 $] suffix [21 12 $]" means: rule r invoked current rule
from state 21. Rule s invoked rule r from state 12 which then invoked
current rule also via state 21. While the context prior to state 21
is different, the fact that both contexts emanate from state 21 implies
that they are now going to track perfectly together. Once they
converged on state 21, there is no way they can separate. In other
words, the prior stack state is not consulted when computing where to
go in the closure operation. ?$ and ??$ are considered the same stack.
If ? is popped off then $ and ?$ remain; they are now an empty and
nonempty context comparison. So, if one stack is a suffix of
another, then it will still degenerate to the simple empty stack
comparison case.
|
|
|