Loyc.LLParserGenerator.LLParserGenerator.ComputeNext Class Reference

Gathers a list of all one-token transitions starting from a single position. Also gathers any and-predicates that must be traversed before completing a transition. More...

---

Source file:

• /Main/LLLPG/CoreEngine/LLParserGenerator.cs

Inheritance diagram for Loyc.LLParserGenerator.LLParserGenerator.ComputeNext:

Remarks

Gathers a list of all one-token transitions starting from a single position. Also gathers any and-predicates that must be traversed before completing a transition.

For example, given

rule X @[ 'x' Y '0'..'9' 'x' ];
rule Y @[.('y' | Z)? ];
rule Z @[ ('z' | '0'..'9' '0'..'9'*) ];

If the dot (.) represents the current position, then this class computes the possible Transitions, which are as follows:

Transition.Set   Transition.Position
'y'              rule Y @[ ('y' | Z)?.];                 (EndOfRule)
'0'..'9'         rule X @[ 'x' Y '0'..'9'.'x' ];         (TerminalPred)
'z'              rule Z @[ ('z' | '0'..'9' '0'..'9'*).]; (EndOfRule)
'0'..'9'         rule Z @[ ('z' | '0'..'9'.'0'..'9'*) ]; (Alts)

Notice that there can be duplicate sets–different destinations for the same input character. This means that there is an LL(1) ambiguity. The ambiguity may (or may not, depending on the situation) be resolved by looking ahead further (it is the responsibility of PredictionAnalysisVisitor.ComputePredictionTree to do so).

This class is derived from GetCanonical just to inherit some code from it.

What to do with and-predicates? It's a tricky question. And-predicates are not used nearly as often as normal terminals and nonterminals, yet they can produce the most complicated prediction code. Consider Alts such as:

( ( &{a} {f();} | &{b} {g();} ) &{c}
  ( &{a} 'a' | &{x} 'b' | &{x} 'c')
| &{x} ( 'a' | &{y} 'b' 'c' )
)

It's enough to make your head explode. IIRC, PredictionAnalysisVisitor deals with such complications–all ComputeNext does is gather a list of AndPreds.

Public Member Functions
void	Do (KthSet result, GrammarPos position)
void	Visit (Pred pred, GrammarPos newPos=null)
override void	Visit (Seq seq)
override void	Visit (Gate gate)
override void	Visit (TerminalPred term)
override void	Visit (RuleRef rref)
override void	Visit (Alts alts)
override void	Visit (AndPred and)
override void	Visit (EndOfRule end)
Public Member Functions inherited from Loyc.LLParserGenerator.PredVisitor
void	Visit (Pred pred)
virtual void	VisitOther (Pred pred)
void	VisitChildrenOf (Seq pred)
void	VisitChildrenOf (AndPred pred)
void	VisitChildrenOf (Gate pred)
void	VisitChildrenOf (Alts pred, bool includeError)