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 and 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 and 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
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, ALTLIST, ARG, ARG_ACTION, ARG_OR_CHARSET, ARGLIST, ASSIGN, AT, BLOCK, CATCH, CHANNELS, CHAR_RANGE, 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, INITACTION, INT, LABEL, LEXER, LEXER_ACTION_CALL, LEXER_ALT_ACTION, LEXER_CHAR_SET, LIST, LOCALS, LPAREN, LT, MODE, NameChar, NameStartChar, NESTED_ACTION, NLCHARS, NOT, numAlts, OPTIONAL, OPTIONS, OR, PARSER, PLUS, PLUS_ASSIGN, POSITIVE_CLOSURE, POUND, PREC_RULE, PRIVATE, PROTECTED, PUBLIC, QUESTION, RANGE, RARROW, RBRACE, RESULT, RET, RETURNS, RPAREN, RULE, RULE_REF, RULEACTIONS, RULEMODIFIERS, RULES, SEMI, SEMPRED, SET, SRC, STAR, STRING_LITERAL, SYNPRED, TEMPLATE, THROWS, TOKEN_REF, tokenNames, TOKENS_SPEC, TREE_GRAMMAR, 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 and Description
LeftRecursiveRuleAnalyzer(GrammarAST ruleAST, Tool tool, String ruleName, String language)

Method Summary

Methods

Modifier and Type	Method and 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 .*)))
void	loadPrecRuleTemplates()
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_fragment, synpred1_LeftRecursiveRuleWalker, synpred2_LeftRecursiveRuleWalker_fragment, synpred2_LeftRecursiveRuleWalker, synpred3_LeftRecursiveRuleWalker_fragment, synpred3_LeftRecursiveRuleWalker, 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 org.stringtemplate.v4.STGroup recRuleTemplates

codegenTemplates

public org.stringtemplate.v4.STGroup codegenTemplates

language

public String language

altAssociativity

public Map<Integer,LeftRecursiveRuleAnalyzer.ASSOC> altAssociativity

Constructor Detail

LeftRecursiveRuleAnalyzer

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

Method Detail

loadPrecRuleTemplates

public void loadPrecRuleTemplates()

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