org.antlr.analysis
Class LL1Analyzer

java.lang.Object
  org.antlr.analysis.LL1Analyzer

public class LL1Analyzer
extends java.lang.Object

Created by IntelliJ IDEA. User: parrt Date: Dec 31, 2007 Time: 1:31:16 PM To change this template use File | Settings | File Templates.

Field Summary

static int	DETECT_PRED_EOR 0 if we hit end of rule and invoker should keep going (epsilon)
static int	DETECT_PRED_FOUND 1 if we found a nonautobacktracking pred
static int	DETECT_PRED_NOT_FOUND 2 if we didn't find such a pred
java.util.Map<NFAState,LookaheadSet>	FIRSTCache
java.util.Map<Rule,LookaheadSet>	FOLLOWCache
Grammar	grammar
protected java.util.Set<NFAState>	lookBusy Used during LOOK to detect computation cycles

Constructor Summary

LL1Analyzer(Grammar grammar)

Method Summary

protected int	_detectConfoundingPredicates(NFAState s, Rule enclosingRule, boolean chaseFollowTransitions)
protected LookaheadSet	_FIRST(NFAState s, boolean chaseFollowTransitions)
protected SemanticContext	_getPredicates(NFAState s, NFAState altStartState)
boolean	detectConfoundingPredicates(NFAState s) Is there a non-syn-pred predicate visible from s that is not in the rule enclosing s? This accounts for most predicate situations and lets ANTLR do a simple LL(1)+pred computation.
LookaheadSet	FIRST(NFAState s) From an NFA state, s, find the set of all labels reachable from s.
LookaheadSet	FOLLOW(Rule r)
SemanticContext	getPredicates(NFAState altStartState) Return predicate expression found via epsilon edges from s.
LookaheadSet	LOOK(NFAState s)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DETECT_PRED_EOR

public static final int DETECT_PRED_EOR

0 if we hit end of rule and invoker should keep going (epsilon)

See Also:

Constant Field Values

DETECT_PRED_FOUND

public static final int DETECT_PRED_FOUND

1 if we found a nonautobacktracking pred

See Also:

Constant Field Values

DETECT_PRED_NOT_FOUND

public static final int DETECT_PRED_NOT_FOUND

2 if we didn't find such a pred

See Also:

Constant Field Values

grammar

public Grammar grammar

lookBusy

protected java.util.Set<NFAState> lookBusy

Used during LOOK to detect computation cycles

FIRSTCache

public java.util.Map<NFAState,LookaheadSet> FIRSTCache

FOLLOWCache

public java.util.Map<Rule,LookaheadSet> FOLLOWCache

Constructor Detail

LL1Analyzer

public LL1Analyzer(Grammar grammar)

Method Detail

FIRST

public LookaheadSet FIRST(NFAState s)

From an NFA state, s, find the set of all labels reachable from s. Used to compute follow sets for error recovery. Never computes a FOLLOW operation. FIRST stops at end of rules, returning EOR, unless invoked from another rule. I.e., routine properly handles a : b A ; where b is nullable. We record with EOR_TOKEN_TYPE if we hit the end of a rule so we can know at runtime (when these sets are used) to start walking up the follow chain to compute the real, correct follow set (as opposed to the FOLLOW, which is a superset). This routine will only be used on parser and tree parser grammars.

FOLLOW

public LookaheadSet FOLLOW(Rule r)

LOOK

public LookaheadSet LOOK(NFAState s)

_FIRST

protected LookaheadSet _FIRST(NFAState s,
                              boolean chaseFollowTransitions)

detectConfoundingPredicates

public boolean detectConfoundingPredicates(NFAState s)

Is there a non-syn-pred predicate visible from s that is not in the rule enclosing s? This accounts for most predicate situations and lets ANTLR do a simple LL(1)+pred computation. TODO: what about gated vs regular preds?

_detectConfoundingPredicates

protected int _detectConfoundingPredicates(NFAState s,
                                           Rule enclosingRule,
                                           boolean chaseFollowTransitions)

getPredicates

public SemanticContext getPredicates(NFAState altStartState)

Return predicate expression found via epsilon edges from s. Do not look into other rules for now. Do something simple. Include backtracking synpreds.

_getPredicates

protected SemanticContext _getPredicates(NFAState s,
                                         NFAState altStartState)