Inheritance diagram for antlr.LLkAnalyzer:

Public Member Functions
	LLkAnalyzer (Tool tool_)
boolean	deterministic (AlternativeBlock blk)
boolean	deterministic (OneOrMoreBlock blk)
boolean	deterministic (ZeroOrMoreBlock blk)
boolean	deterministicImpliedPath (BlockWithImpliedExitPath blk)
Lookahead	FOLLOW (int k, RuleEndElement end)
Lookahead	look (int k, ActionElement action)
Lookahead	look (int k, AlternativeBlock blk)
Lookahead	look (int k, BlockEndElement end)
Lookahead	look (int k, CharLiteralElement atom)
Lookahead	look (int k, CharRangeElement r)
Lookahead	look (int k, GrammarAtom atom)
Lookahead	look (int k, OneOrMoreBlock blk)
Lookahead	look (int k, RuleBlock blk)
Lookahead	look (int k, RuleEndElement end)
Lookahead	look (int k, RuleRefElement rr)
Lookahead	look (int k, StringLiteralElement atom)
Lookahead	look (int k, SynPredBlock blk)
Lookahead	look (int k, TokenRangeElement r)
Lookahead	look (int k, TreeElement t)
Lookahead	look (int k, WildcardElement wc)
Lookahead	look (int k, ZeroOrMoreBlock blk)
Lookahead	look (int k, String rule)
void	setGrammar (Grammar g)
boolean	subruleCanBeInverted (AlternativeBlock blk, boolean forLexer)
Static Public Member Functions
static boolean	lookaheadEquivForApproxAndFullAnalysis (Lookahead[] bset, int k)
Public Attributes
boolean	DEBUG_ANALYZER = false
Protected Member Functions
boolean	altUsesWildcardDefault (Alternative alt)
Protected Attributes
Tool	tool = null
Grammar	grammar = null
boolean	lexicalAnalysis = false
Package Attributes
CharFormatter	charFormatter = new JavaCharFormatter()

Detailed Description

A linear-approximate LL(k) grammar analzyer.

All lookahead elements are sets of token types.

Author:: Terence Parr, John Lilley

See also:: antlr.Grammar; antlr.Lookahead

Constructor & Destructor Documentation

antlr.LLkAnalyzer.LLkAnalyzer ( Tool tool_ )

Create an LLk analyzer

References antlr.LLkAnalyzer.tool.

Member Function Documentation

boolean antlr.LLkAnalyzer.altUsesWildcardDefault ( Alternative alt ) [protected]

Return true if someone used the '.' wildcard default idiom. Either #(. children) or '.' as an alt by itself.

References antlr.Alternative.head, and antlr.AlternativeElement.next.

Referenced by antlr.LLkAnalyzer.deterministic().

boolean antlr.LLkAnalyzer.deterministic ( AlternativeBlock blk )

Is this block of alternatives LL(k)? Fill in alternative cache for this block.

Returns:: true if the block is deterministic

The lookahead depth for this decision

Implements antlr.LLkGrammarAnalyzer.

Referenced by antlr.LLkAnalyzer.deterministic().

boolean antlr.LLkAnalyzer.deterministic ( ZeroOrMoreBlock blk )

Is (...)* block LL(1)? Fill in alternative cache for this block.

Returns:: true if the block is deterministic

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.LLkAnalyzer.deterministic(), and antlr.LLkAnalyzer.deterministicImpliedPath().

boolean antlr.LLkAnalyzer.deterministic ( OneOrMoreBlock blk )

Is (...)+ block LL(1)? Fill in alternative cache for this block.

Returns:: true if the block is deterministic

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.LLkAnalyzer.deterministic(), and antlr.LLkAnalyzer.deterministicImpliedPath().

boolean antlr.LLkAnalyzer.deterministicImpliedPath ( BlockWithImpliedExitPath blk )

Is this (...)* or (...)+ block LL(k)?

Returns:: true if the block is deterministic

The lookahead depth for this decision considering implied exit path

Referenced by antlr.LLkAnalyzer.deterministic().

Lookahead antlr.LLkAnalyzer.FOLLOW	(	int	k,
		RuleEndElement	end
	)

Compute the lookahead set of whatever follows references to the rule associated witht the FOLLOW block.

Implements antlr.LLkGrammarAnalyzer.

References antlr.collections.impl.BitSet.add(), antlr.BlockEndElement.block, antlr.RuleEndElement.cache, antlr.LLkAnalyzer.charFormatter, antlr.Lookahead.clone(), antlr.Lookahead.combineWith(), antlr.Lookahead.cycle, antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.RuleBlock.endNode, antlr.Lookahead.fset, antlr.RuleSymbol.getBlock(), antlr.RuleSymbol.getReference(), antlr.RuleBlock.getRuleName(), antlr.Grammar.getSymbol(), antlr.LLkAnalyzer.grammar, antlr.LLkAnalyzer.lexicalAnalysis, antlr.BlockEndElement.lock, antlr.GrammarElement.look(), antlr.AlternativeElement.next, antlr.collections.impl.BitSet.nil(), antlr.RuleSymbol.numReferences(), antlr.Lookahead.setEpsilon(), antlr.GrammarElement.toString(), and antlr.Lookahead.toString().

Referenced by antlr.LLkAnalyzer.look().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		WildcardElement	wc
	)

Implements antlr.LLkGrammarAnalyzer.

References antlr.collections.impl.BitSet.clone(), antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.LLkAnalyzer.grammar, antlr.LLkAnalyzer.lexicalAnalysis, antlr.GrammarElement.look(), antlr.TokenManager.maxTokenType(), antlr.AlternativeElement.next, antlr.collections.impl.BitSet.notInPlace(), and antlr.Grammar.tokenManager.

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		String	rule
	)

Compute the combined lookahead for all productions of a rule. If the lookahead returns with epsilon, at least one epsilon path exists (one that consumes no tokens). The noFOLLOW flag being set for this endruleblk, indicates that the a rule ref invoked this rule.

Currently only look(RuleRef) calls this. There is no need for the code generator to call this.

Implements antlr.LLkGrammarAnalyzer.

References antlr.RuleBlock.cache, antlr.LLkAnalyzer.charFormatter, antlr.Lookahead.clone(), antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.RuleSymbol.getBlock(), antlr.RuleBlock.getRuleName(), antlr.Grammar.getSymbol(), antlr.LLkAnalyzer.grammar, antlr.RuleBlock.lock, antlr.LLkAnalyzer.look(), and antlr.Lookahead.toString().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		TokenRangeElement	r
	)

Implements antlr.LLkGrammarAnalyzer.

References antlr.collections.impl.BitSet.add(), antlr.TokenRangeElement.begin, antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.TokenRangeElement.end, antlr.GrammarElement.look(), antlr.AlternativeElement.next, and antlr.Lookahead.of().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		SynPredBlock	blk
	)

The lookahead of a (...)=> block is the lookahead of what follows the block. By definition, the syntactic predicate block defies static analysis (you want to try it out at run-time). The LOOK of (a)=>A B is A for LL(1) ### is this even called?

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.GrammarElement.look(), and antlr.AlternativeElement.next.

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		AlternativeBlock	blk
	)

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		RuleRefElement	rr
	)

Compute the lookahead contributed by a rule reference.

When computing ruleref lookahead, we don't want the FOLLOW computation done if an empty path exists for the rule. The FOLLOW is too loose of a set...we want only to include the "local" FOLLOW or what can follow this particular ref to the node. In other words, we use context information to reduce the complexity of the analysis and strengthen the parser.

The noFOLLOW flag is used as a means of restricting the FOLLOW to a "local" FOLLOW. This variable is orthogonal to the lock variable that prevents infinite recursion. noFOLLOW does not care about what k is.

Implements antlr.LLkGrammarAnalyzer.

References antlr.Lookahead.combineWith(), antlr.Lookahead.containsEpsilon(), antlr.Lookahead.cycle, antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.RuleSymbol.defined, antlr.AlternativeElement.enclosingRuleName, antlr.RuleBlock.endNode, antlr.Lookahead.epsilonDepth, antlr.Tool.error(), antlr.RuleSymbol.getBlock(), antlr.GrammarElement.getColumn(), antlr.Grammar.getFilename(), antlr.GrammarElement.getLine(), antlr.Grammar.getSymbol(), antlr.LLkAnalyzer.grammar, antlr.GrammarElement.look(), antlr.LLkAnalyzer.look(), antlr.AlternativeElement.next, antlr.RuleEndElement.noFOLLOW, antlr.Lookahead.resetEpsilon(), antlr.RuleRefElement.targetRule, antlr.collections.impl.BitSet.toArray(), and antlr.LLkAnalyzer.tool.

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		RuleEndElement	end
	)

If not locked or noFOLLOW set, compute FOLLOW of a rule.

TJP says 8/12/99: not true anymore: Lexical rules never compute follow. They set epsilon and the code generator gens code to check for any character. The code generator must remove the tokens used to predict any previous alts in the same block.

When the last node of a rule is reached and noFOLLOW, it implies that a "local" FOLLOW will be computed after this call. I.e.,

		a : b A;
		b : B | ;
		c : b C;

Here, when computing the look of rule b from rule a, we want only {B,EPSILON_TYPE} so that look(b A) will be {B,A} not {B,A,C}.

if the end block is not locked and the FOLLOW is wanted, the algorithm must compute the lookahead of what follows references to this rule. If end block is locked, FOLLOW will return an empty set with a cycle to the rule associated with this end block.

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.Lookahead.epsilonDepth, antlr.LLkAnalyzer.FOLLOW(), antlr.BlockEndElement.lock, antlr.RuleEndElement.noFOLLOW, antlr.collections.impl.BitSet.of(), and antlr.Lookahead.setEpsilon().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		RuleBlock	blk
	)

Combine the lookahead computed for each alternative. Lock the node so that no other computation may come back on itself--infinite loop. This also implies infinite left-recursion in the grammar (or an error in this algorithm ;)).

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, and antlr.LLkAnalyzer.look().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		OneOrMoreBlock	blk
	)

The lookahead of a (...)+ block is the combined lookahead of all alternatives and, if an empty path is found, the lookahead of what follows the block.

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, and antlr.LLkAnalyzer.look().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		StringLiteralElement	atom
	)

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.Lookahead.fset, antlr.GrammarAtom.getType(), antlr.LLkAnalyzer.grammar, antlr.LLkAnalyzer.lexicalAnalysis, antlr.GrammarElement.look(), antlr.TokenManager.maxTokenType(), antlr.AlternativeElement.next, antlr.GrammarAtom.not, antlr.collections.impl.BitSet.notInPlace(), antlr.Lookahead.of(), antlr.StringLiteralElement.processedAtomText, and antlr.Grammar.tokenManager.

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		CharRangeElement	r
	)

Implements antlr.LLkGrammarAnalyzer.

References antlr.collections.impl.BitSet.add(), antlr.CharRangeElement.begin, antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.CharRangeElement.end, antlr.GrammarElement.look(), antlr.AlternativeElement.next, and antlr.Lookahead.of().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		TreeElement	t
	)

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.Lookahead.fset, antlr.GrammarAtom.getType(), antlr.LLkAnalyzer.grammar, antlr.GrammarElement.look(), antlr.TokenManager.maxTokenType(), antlr.AlternativeElement.next, antlr.GrammarAtom.not, antlr.collections.impl.BitSet.notInPlace(), antlr.Lookahead.of(), antlr.TreeElement.root, and antlr.Grammar.tokenManager.

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		BlockEndElement	end
	)

Compute what follows this place-holder node and possibly what begins the associated loop unless the node is locked.

if we hit the end of a loop, we have to include what tokens can begin the loop as well. If the start node is locked, then we simply found an empty path through this subrule while analyzing it. If the start node is not locked, then this node was hit during a FOLLOW operation and the FIRST of this block must be included in that lookahead computation.

Implements antlr.LLkGrammarAnalyzer.

References antlr.BlockEndElement.block, antlr.Lookahead.combineWith(), antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.BlockEndElement.lock, antlr.GrammarElement.look(), antlr.LLkAnalyzer.look(), antlr.AlternativeElement.next, and antlr.Lookahead.setEpsilon().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		CharLiteralElement	atom
	)

Return this char as the lookahead if k=1.

### Doesn't work for ( 'a' 'b' | 'a' ~'b' ) yet!!!

If the atom has the not flag on, then create the set complement of the tokenType which is the set of all characters referenced in the grammar with this char turned off. Also remove characters from the set that are currently allocated for predicting previous alternatives. This avoids ambiguity messages and is more properly what is meant. ( 'a' | ~'a' ) implies that the ~'a' is the "else" clause.

NOTE: we do NOT include exit path in the exclusion set. E.g., ( 'a' | ~'a' )* 'b' should exit upon seeing a 'b' during the loop.

Implements antlr.LLkGrammarAnalyzer.

References antlr.collections.impl.BitSet.clear(), antlr.Lookahead.clone(), antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.GrammarAtom.getType(), antlr.LLkAnalyzer.grammar, antlr.LLkAnalyzer.lexicalAnalysis, antlr.GrammarElement.look(), antlr.AlternativeElement.next, antlr.GrammarAtom.not, antlr.Tool.panic(), antlr.LLkAnalyzer.tool, and antlr.collections.impl.BitSet.toString().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		ActionElement	action
	)

Actions are ignored

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.GrammarElement.look(), and antlr.AlternativeElement.next.

Referenced by antlr.LLkAnalyzer.look(), and antlr.LLkAnalyzer.lookaheadEquivForApproxAndFullAnalysis().

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		GrammarAtom	atom
	)

Implements antlr.LLkGrammarAnalyzer.

References antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.Lookahead.fset, antlr.GrammarAtom.getType(), antlr.LLkAnalyzer.grammar, antlr.LLkAnalyzer.lexicalAnalysis, antlr.GrammarElement.look(), antlr.TokenManager.maxTokenType(), antlr.AlternativeElement.next, antlr.GrammarAtom.not, antlr.collections.impl.BitSet.notInPlace(), antlr.Lookahead.of(), antlr.Tool.panic(), antlr.Grammar.tokenManager, and antlr.LLkAnalyzer.tool.

Lookahead antlr.LLkAnalyzer.look	(	int	k,
		ZeroOrMoreBlock	blk
	)

The (...)* element is the combined lookahead of the alternatives and what can follow the loop.

Implements antlr.LLkGrammarAnalyzer.

References antlr.Lookahead.combineWith(), antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.GrammarElement.look(), antlr.LLkAnalyzer.look(), and antlr.AlternativeElement.next.

static boolean antlr.LLkAnalyzer.lookaheadEquivForApproxAndFullAnalysis	(	Lookahead[]	bset,
		int	k
	)			`[static]`

If the first k-1 sets are singleton sets, the appoximate lookahead analysis is equivalent to full lookahead analysis.

References antlr.collections.impl.BitSet.degree(), antlr.Lookahead.fset, and antlr.LLkAnalyzer.look().

Referenced by antlr.LLkAnalyzer.deterministicImpliedPath().

void antlr.LLkAnalyzer.setGrammar ( Grammar g )

Set the grammar for the analyzer

Implements antlr.LLkGrammarAnalyzer.

References antlr.Grammar.analyzerDebug, antlr.LLkAnalyzer.DEBUG_ANALYZER, antlr.LLkAnalyzer.grammar, and antlr.LLkAnalyzer.lexicalAnalysis.

boolean antlr.LLkAnalyzer.subruleCanBeInverted	(	AlternativeBlock	blk,
		boolean	forLexer
	)

Implements antlr.LLkGrammarAnalyzer.

References antlr.AlternativeBlock.alternatives, antlr.Alternative.exceptionSpec, antlr.AlternativeBlock.getAlternativeAt(), antlr.AlternativeElement.getAutoGenType(), antlr.Alternative.head, antlr.AlternativeElement.next, antlr.Alternative.semPred, antlr.collections.impl.Vector.size(), and antlr.Alternative.synPred.

Referenced by antlr.MakeGrammar.endSubRule(), and antlr.LLkAnalyzer.look().

Member Data Documentation

CharFormatter antlr.LLkAnalyzer.charFormatter = new JavaCharFormatter() [package]

Referenced by antlr.LLkAnalyzer.deterministic(), antlr.LLkAnalyzer.deterministicImpliedPath(), antlr.LLkAnalyzer.FOLLOW(), and antlr.LLkAnalyzer.look().

boolean antlr.LLkAnalyzer.DEBUG_ANALYZER = false

Referenced by antlr.LLkAnalyzer.deterministic(), antlr.LLkAnalyzer.deterministicImpliedPath(), antlr.LLkAnalyzer.FOLLOW(), antlr.LLkAnalyzer.look(), and antlr.LLkAnalyzer.setGrammar().

Grammar antlr.LLkAnalyzer.grammar = null [protected]

Referenced by antlr.LLkAnalyzer.deterministic(), antlr.LLkAnalyzer.deterministicImpliedPath(), antlr.LLkAnalyzer.FOLLOW(), antlr.LLkAnalyzer.look(), and antlr.LLkAnalyzer.setGrammar().

boolean antlr.LLkAnalyzer.lexicalAnalysis = false [protected]

Referenced by antlr.LLkAnalyzer.deterministic(), antlr.LLkAnalyzer.deterministicImpliedPath(), antlr.LLkAnalyzer.FOLLOW(), antlr.LLkAnalyzer.look(), and antlr.LLkAnalyzer.setGrammar().

Tool antlr.LLkAnalyzer.tool = null [protected]

Referenced by antlr.LLkAnalyzer.deterministic(), antlr.LLkAnalyzer.deterministicImpliedPath(), antlr.LLkAnalyzer.LLkAnalyzer(), and antlr.LLkAnalyzer.look().

The documentation for this class was generated from the following file:

LLkAnalyzer.java

All Classes Namespaces Files Functions Variables Enumerations Properties

antlr.LLkAnalyzer Class Reference

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Package Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation