public Class NFAContext

The NFA state that invoked another rule's start state is recorded on the rule invocation context stack.

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". Actually (12/14/2007) I realize that this example is trapped by the non-LL(*) detector for recursion in > 1 alt. Here is an example that trips stack overflow: s : a Y | A A A A A X ; // force recursion past m=4 a : A a | Q; If that were: s : a Y | A+ X ; it could loop forever. Imagine doing a depth-first search on the e 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. 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.

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.

Overrides java.lang.Object.equals.

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.

Parameters

o:Object

Doc from java.lang.Object.equals.

the reference object with which to compare.

Returns:boolean

Doc from java.lang.Object.equals.

true if this object is the same as the obj argument; false otherwise.

Annotations

@Override

Overrides java.lang.Object.hashCode.

Doc from java.lang.Object.hashCode.

Returns a hash code value for this object. This method is supported for the benefit of hash tables such as those provided by java.util.HashMap.

The general contract of hashCode is:

• Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
• If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
• It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

Returns:int

a hash code value for this object

Annotations

@Override

A context is empty if there is no parent; meaning nobody pushed anything on the call stack.

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.

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