Package org.antlr.v4.analysis

Class LeftRecursiveRuleAnalyzer

java.lang.Object

org.antlr.runtime.BaseRecognizer

org.antlr.runtime.tree.TreeParser

org.antlr.v4.parse.LeftRecursiveRuleWalker

org.antlr.v4.analysis.LeftRecursiveRuleAnalyzer

public class LeftRecursiveRuleAnalyzer
extends LeftRecursiveRuleWalker

Using a tree walker on the rules, determine if a rule is directly left-recursive and if it follows our pattern.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	LeftRecursiveRuleAnalyzer.ASSOC

Nested classes/interfaces inherited from class org.antlr.v4.parse.LeftRecursiveRuleWalker

LeftRecursiveRuleWalker.DFA11, LeftRecursiveRuleWalker.DFA14, LeftRecursiveRuleWalker.outerAlternative_return, LeftRecursiveRuleWalker.ruleBlock_return

Field Summary

Fields

Modifier and Type	Field	Description
Map<Integer,LeftRecursiveRuleAnalyzer.ASSOC>	altAssociativity
LinkedHashMap<Integer,LeftRecursiveRuleAltInfo>	binaryAlts
org.stringtemplate.v4.STGroup	codegenTemplates
String	language
List<Pair<GrammarAST,String>>	leftRecursiveRuleRefLabels	Pointer to ID node of ^(= ID element)
List<LeftRecursiveRuleAltInfo>	prefixAndOtherAlts
static org.stringtemplate.v4.STGroup	recRuleTemplates
GrammarAST	retvals
String	ruleName
LinkedHashMap<Integer,LeftRecursiveRuleAltInfo>	suffixAlts
LinkedHashMap<Integer,LeftRecursiveRuleAltInfo>	ternaryAlts
org.antlr.runtime.TokenStream	tokenStream	Tokens from which rule AST comes from
Tool	tool

Fields inherited from class org.antlr.v4.parse.LeftRecursiveRuleWalker

ACTION, ACTION_CHAR_LITERAL, ACTION_ESC, ACTION_STRING_LITERAL, ALT, ARG_ACTION, ARG_OR_CHARSET, ASSIGN, AT, BLOCK, CATCH, CHANNELS, CLOSURE, COLON, COLONCOLON, COMBINED, COMMA, COMMENT, dfa11, dfa14, DOC_COMMENT, DOLLAR, DOT, ELEMENT_OPTIONS, EOF, EPSILON, ERRCHAR, ESC_SEQ, FINALLY, FOLLOW_ACTION_in_block1179, FOLLOW_ACTION_in_elementOption921, FOLLOW_ACTION_in_epsilonElement1038, FOLLOW_ACTION_in_epsilonElement1054, FOLLOW_ACTION_in_exceptionHandler220, FOLLOW_ACTION_in_finallyClause235, FOLLOW_ACTION_in_rec_rule156, FOLLOW_ALT_in_alternative1199, FOLLOW_ALT_in_binary541, FOLLOW_ALT_in_nonLeftRecur671, FOLLOW_ALT_in_prefix579, FOLLOW_ALT_in_suffix630, FOLLOW_alternative_in_block1182, FOLLOW_ARG_ACTION_in_atom1223, FOLLOW_ARG_ACTION_in_exceptionHandler218, FOLLOW_ARG_ACTION_in_rec_rule117, FOLLOW_ARG_ACTION_in_rec_rule96, FOLLOW_ASSIGN_in_element978, FOLLOW_ASSIGN_in_elementOption885, FOLLOW_ASSIGN_in_elementOption901, FOLLOW_ASSIGN_in_elementOption917, FOLLOW_ASSIGN_in_elementOption933, FOLLOW_ASSIGN_in_recurse693, FOLLOW_ASSIGN_in_token740, FOLLOW_AT_in_rec_rule152, FOLLOW_atom_in_element952, FOLLOW_atom_in_element969, FOLLOW_atom_in_element971, FOLLOW_binary_in_outerAlternative362, FOLLOW_binary_in_synpred1_LeftRecursiveRuleWalker348, FOLLOW_BLOCK_in_block1177, FOLLOW_block_in_ebnf1111, FOLLOW_block_in_ebnf1125, FOLLOW_block_in_ebnf1141, FOLLOW_block_in_ebnf1157, FOLLOW_BLOCK_in_ruleBlock290, FOLLOW_CATCH_in_exceptionHandler216, FOLLOW_CLOSURE_in_ebnf1139, FOLLOW_DOT_in_atom1286, FOLLOW_ebnf_in_element1022, FOLLOW_element_in_alternative1204, FOLLOW_element_in_atom1290, FOLLOW_element_in_binary548, FOLLOW_element_in_element960, FOLLOW_element_in_element982, FOLLOW_element_in_element993, FOLLOW_element_in_nonLeftRecur676, FOLLOW_element_in_prefix587, FOLLOW_element_in_suffix637, FOLLOW_ELEMENT_OPTIONS_in_elementOptions853, FOLLOW_elementOption_in_elementOptions855, FOLLOW_elementOptions_in_alternative1201, FOLLOW_elementOptions_in_atom1226, FOLLOW_elementOptions_in_atom1240, FOLLOW_elementOptions_in_atom1257, FOLLOW_elementOptions_in_atom1274, FOLLOW_elementOptions_in_binary543, FOLLOW_elementOptions_in_epsilonElement1056, FOLLOW_elementOptions_in_epsilonElement1065, FOLLOW_elementOptions_in_nonLeftRecur673, FOLLOW_elementOptions_in_prefix581, FOLLOW_elementOptions_in_setElement1080, FOLLOW_elementOptions_in_setElement1089, FOLLOW_elementOptions_in_suffix632, FOLLOW_elementOptions_in_token794, FOLLOW_elementOptions_in_token811, FOLLOW_EPSILON_in_epsilonElement1048, FOLLOW_epsilonElement_in_binary553, FOLLOW_epsilonElement_in_element1027, FOLLOW_epsilonElement_in_prefix595, FOLLOW_exceptionGroup_in_rec_rule179, FOLLOW_exceptionHandler_in_exceptionGroup197, FOLLOW_FINALLY_in_finallyClause233, FOLLOW_finallyClause_in_exceptionGroup200, FOLLOW_ID_in_atom1288, FOLLOW_ID_in_element980, FOLLOW_ID_in_element991, FOLLOW_ID_in_elementOption874, FOLLOW_ID_in_elementOption887, FOLLOW_ID_in_elementOption889, FOLLOW_ID_in_elementOption903, FOLLOW_ID_in_elementOption919, FOLLOW_ID_in_elementOption935, FOLLOW_ID_in_rec_rule154, FOLLOW_ID_in_recurse695, FOLLOW_ID_in_recurse706, FOLLOW_ID_in_token742, FOLLOW_ID_in_token757, FOLLOW_INT_in_elementOption937, FOLLOW_LOCALS_in_rec_rule115, FOLLOW_nonLeftRecur_in_outerAlternative515, FOLLOW_NOT_in_element958, FOLLOW_OPTIONAL_in_ebnf1123, FOLLOW_OPTIONS_in_rec_rule135, FOLLOW_outerAlternative_in_ruleBlock303, FOLLOW_PLUS_ASSIGN_in_element989, FOLLOW_PLUS_ASSIGN_in_recurse704, FOLLOW_PLUS_ASSIGN_in_token755, FOLLOW_POSITIVE_CLOSURE_in_ebnf1155, FOLLOW_prefix_in_outerAlternative418, FOLLOW_prefix_in_synpred2_LeftRecursiveRuleWalker404, FOLLOW_RANGE_in_element967, FOLLOW_recurse_in_binary546, FOLLOW_recurse_in_binary551, FOLLOW_recurse_in_prefix593, FOLLOW_recurse_in_suffix635, FOLLOW_recurseNoLabel_in_recurse697, FOLLOW_recurseNoLabel_in_recurse708, FOLLOW_recurseNoLabel_in_recurse714, FOLLOW_RETURNS_in_rec_rule92, FOLLOW_RULE_in_rec_rule72, FOLLOW_RULE_REF_in_atom1221, FOLLOW_RULE_REF_in_element1017, FOLLOW_RULE_REF_in_rec_rule76, FOLLOW_RULE_REF_in_recurseNoLabel726, FOLLOW_ruleBlock_in_rec_rule172, FOLLOW_ruleModifier_in_rec_rule83, FOLLOW_SEMPRED_in_epsilonElement1043, FOLLOW_SEMPRED_in_epsilonElement1063, FOLLOW_SET_in_element1003, FOLLOW_setElement_in_element1005, FOLLOW_STRING_LITERAL_in_atom1238, FOLLOW_STRING_LITERAL_in_atom1246, FOLLOW_STRING_LITERAL_in_elementOption905, FOLLOW_STRING_LITERAL_in_setElement1078, FOLLOW_STRING_LITERAL_in_setElement1095, FOLLOW_STRING_LITERAL_in_token771, FOLLOW_STRING_LITERAL_in_token792, FOLLOW_suffix_in_outerAlternative474, FOLLOW_suffix_in_synpred3_LeftRecursiveRuleWalker460, FOLLOW_token_in_token746, FOLLOW_token_in_token761, FOLLOW_TOKEN_REF_in_atom1255, FOLLOW_TOKEN_REF_in_atom1263, FOLLOW_TOKEN_REF_in_setElement1087, FOLLOW_TOKEN_REF_in_setElement1100, FOLLOW_TOKEN_REF_in_token809, FOLLOW_TOKEN_REF_in_token823, FOLLOW_WILDCARD_in_atom1272, FOLLOW_WILDCARD_in_atom1280, FRAGMENT, GRAMMAR, GT, HEX_DIGIT, ID, IMPORT, INT, LEXER, LEXER_ACTION_CALL, LEXER_ALT_ACTION, LEXER_CHAR_SET, LOCALS, LPAREN, LT, MODE, NameChar, NameStartChar, NESTED_ACTION, NLCHARS, NOT, numAlts, OPTIONAL, OPTIONS, OR, PARSER, PLUS, PLUS_ASSIGN, POSITIVE_CLOSURE, POUND, PRIVATE, PROTECTED, PUBLIC, QUESTION, RANGE, RARROW, RBRACE, RETURNS, RPAREN, RULE, RULE_REF, RULEMODIFIERS, RULES, SEMI, SEMPRED, SET, SRC, STAR, STRING_LITERAL, THROWS, TOKEN_REF, tokenNames, TOKENS_SPEC, UNICODE_ESC, UNICODE_EXTENDED_ESC, UnicodeBOM, WILDCARD, WS, WSCHARS, WSNLCHARS

Fields inherited from class org.antlr.runtime.tree.TreeParser

DOWN, input, UP

Fields inherited from class org.antlr.runtime.BaseRecognizer

DEFAULT_TOKEN_CHANNEL, HIDDEN, INITIAL_FOLLOW_STACK_SIZE, MEMO_RULE_FAILED, MEMO_RULE_UNKNOWN, NEXT_TOKEN_RULE_NAME, state

Constructor Summary

Constructors

Constructor	Description
LeftRecursiveRuleAnalyzer(GrammarAST ruleAST, Tool tool, String ruleName, String language)

Method Summary

Modifier and Type	Method	Description
AltAST	addPrecedenceArgToRules(AltAST t, int prec)
void	binaryAlt(AltAST originalAltTree, int alt)
String	getArtificialOpPrecRule()
static boolean	hasImmediateRecursiveRuleRefs(GrammarAST t, String ruleName)	Match (RULE RULE_REF (BLOCK (ALT .*) (ALT RULE_REF[self] .*) (ALT .*))) Match (RULE RULE_REF (BLOCK (ALT .*) (ALT (ASSIGN ID RULE_REF[self]) .*) (ALT .*)))
int	nextPrecedence(int alt)
void	otherAlt(AltAST originalAltTree, int alt)
int	precedence(int alt)
void	prefixAlt(AltAST originalAltTree, int alt)
void	setAltAssoc(AltAST t, int alt)
void	setReturnValues(GrammarAST t)
void	stripAltLabel(GrammarAST altAST)	Strip last 2 tokens if → label; alter indexes in altAST
GrammarAST	stripLeftRecursion(GrammarAST altAST)
void	suffixAlt(AltAST originalAltTree, int alt)
String	text(GrammarAST t)
String	toString()

Methods inherited from class org.antlr.v4.parse.LeftRecursiveRuleWalker

alternative, atom, binary, block, ebnf, element, elementOption, elementOptions, epsilonElement, exceptionGroup, exceptionHandler, finallyClause, getDelegates, getGrammarFileName, getTokenNames, nonLeftRecur, outerAlternative, prefix, rec_rule, recurse, recurseNoLabel, ruleBlock, ruleModifier, setElement, suffix, synpred1_LeftRecursiveRuleWalker, synpred1_LeftRecursiveRuleWalker_fragment, synpred2_LeftRecursiveRuleWalker, synpred2_LeftRecursiveRuleWalker_fragment, synpred3_LeftRecursiveRuleWalker, synpred3_LeftRecursiveRuleWalker_fragment, token

Methods inherited from class org.antlr.runtime.tree.TreeParser

getAncestor, getCurrentInputSymbol, getErrorHeader, getErrorMessage, getMissingSymbol, getSourceName, getTreeNodeStream, inContext, inContext, matchAny, recoverFromMismatchedToken, reset, setTreeNodeStream, traceIn, traceOut

Methods inherited from class org.antlr.runtime.BaseRecognizer

alreadyParsedRule, beginResync, combineFollows, computeContextSensitiveRuleFOLLOW, computeErrorRecoverySet, consumeUntil, consumeUntil, displayRecognitionError, emitErrorMessage, endResync, failed, getBacktrackingLevel, getNumberOfSyntaxErrors, getRuleInvocationStack, getRuleInvocationStack, getRuleMemoization, getRuleMemoizationCacheSize, getTokenErrorDisplay, match, memoize, mismatchIsMissingToken, mismatchIsUnwantedToken, pushFollow, recover, recoverFromMismatchedSet, reportError, setBacktrackingLevel, toStrings, traceIn, traceOut

Methods inherited from class java.lang.Object

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

Field Detail

tool

public Tool tool

ruleName

public String ruleName

binaryAlts

public LinkedHashMap<Integer,LeftRecursiveRuleAltInfo> binaryAlts

ternaryAlts

public LinkedHashMap<Integer,LeftRecursiveRuleAltInfo> ternaryAlts

suffixAlts

public LinkedHashMap<Integer,LeftRecursiveRuleAltInfo> suffixAlts

prefixAndOtherAlts

public List<LeftRecursiveRuleAltInfo> prefixAndOtherAlts

leftRecursiveRuleRefLabels

public List<Pair<GrammarAST,String>> leftRecursiveRuleRefLabels

Pointer to ID node of ^(= ID element)

tokenStream

public final org.antlr.runtime.TokenStream tokenStream

Tokens from which rule AST comes from

retvals

public GrammarAST retvals

recRuleTemplates

public static final org.stringtemplate.v4.STGroup recRuleTemplates

codegenTemplates

public final org.stringtemplate.v4.STGroup codegenTemplates

language

public final String language

altAssociativity

public Map<Integer,LeftRecursiveRuleAnalyzer.ASSOC> altAssociativity

Constructor Detail

LeftRecursiveRuleAnalyzer

public LeftRecursiveRuleAnalyzer(GrammarAST ruleAST,
                                 Tool tool,
                                 String ruleName,
                                 String language)

Method Detail

setReturnValues

public void setReturnValues(GrammarAST t)

Overrides:

setReturnValues in class LeftRecursiveRuleWalker

setAltAssoc

public void setAltAssoc(AltAST t,
                        int alt)

Overrides:

setAltAssoc in class LeftRecursiveRuleWalker

binaryAlt

public void binaryAlt(AltAST originalAltTree,
                      int alt)

Overrides:

binaryAlt in class LeftRecursiveRuleWalker

prefixAlt

public void prefixAlt(AltAST originalAltTree,
                      int alt)

Overrides:

prefixAlt in class LeftRecursiveRuleWalker

suffixAlt

public void suffixAlt(AltAST originalAltTree,
                      int alt)

Overrides:

suffixAlt in class LeftRecursiveRuleWalker

otherAlt

public void otherAlt(AltAST originalAltTree,
                     int alt)

Overrides:

otherAlt in class LeftRecursiveRuleWalker

getArtificialOpPrecRule

public String getArtificialOpPrecRule()

addPrecedenceArgToRules

public AltAST addPrecedenceArgToRules(AltAST t,
                                      int prec)

hasImmediateRecursiveRuleRefs

public static boolean hasImmediateRecursiveRuleRefs(GrammarAST t,
                                                    String ruleName)

Match (RULE RULE_REF (BLOCK (ALT .*) (ALT RULE_REF[self] .*) (ALT .*))) Match (RULE RULE_REF (BLOCK (ALT .*) (ALT (ASSIGN ID RULE_REF[self]) .*) (ALT .*)))

stripLeftRecursion

public GrammarAST stripLeftRecursion(GrammarAST altAST)

stripAltLabel

public void stripAltLabel(GrammarAST altAST)

Strip last 2 tokens if → label; alter indexes in altAST

text

public String text(GrammarAST t)

precedence

public int precedence(int alt)

nextPrecedence

public int nextPrecedence(int alt)

toString

public String toString()

Overrides:

toString in class Object