1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
/*
* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
* Use of this file is governed by the BSD 3-clause license that
* can be found in the LICENSE.txt file in the project root.
*/
package org.antlr.v4.analysis;
import org.antlr.v4.runtime.atn.ATN;
import org.antlr.v4.runtime.atn.ATNState;
import org.antlr.v4.runtime.atn.RuleStartState;
import org.antlr.v4.runtime.atn.RuleStopState;
import org.antlr.v4.runtime.atn.RuleTransition;
import org.antlr.v4.runtime.atn.Transition;
import org.antlr.v4.runtime.misc.OrderedHashSet;
import org.antlr.v4.tool.Grammar;
import org.antlr.v4.tool.Rule;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class LeftRecursionDetector {
Grammar g;
public ATN atn;
/** Holds a list of cycles (sets of rule names). */
public List<Set<Rule>> listOfRecursiveCycles = new ArrayList<Set<Rule>>();
/** Which rule start states have we visited while looking for a single
* left-recursion check?
*/
Set<RuleStartState> rulesVisitedPerRuleCheck = new HashSet<RuleStartState>();
public LeftRecursionDetector(Grammar g, ATN atn) {
this.g = g;
this.atn = atn;
}
public void check() {
for (RuleStartState start : atn.ruleToStartState) {
//System.out.print("check "+start.rule.name);
rulesVisitedPerRuleCheck.clear();
rulesVisitedPerRuleCheck.add(start);
//FASerializer ser = new FASerializer(atn.g, start);
//System.out.print(":\n"+ser+"\n");
check(g.getRule(start.ruleIndex), start, new HashSet<ATNState>());
}
//System.out.println("cycles="+listOfRecursiveCycles);
if ( !listOfRecursiveCycles.isEmpty() ) {
g.tool.errMgr.leftRecursionCycles(g.fileName, listOfRecursiveCycles);
}
}
/** From state s, look for any transition to a rule that is currently
* being traced. When tracing r, visitedPerRuleCheck has r
* initially. If you reach a rule stop state, return but notify the
* invoking rule that the called rule is nullable. This implies that
* invoking rule must look at follow transition for that invoking state.
*
* The visitedStates tracks visited states within a single rule so
* we can avoid epsilon-loop-induced infinite recursion here. Keep
* filling the cycles in listOfRecursiveCycles and also, as a
* side-effect, set leftRecursiveRules.
*/
public boolean check(Rule enclosingRule, ATNState s, Set<ATNState> visitedStates) {
if ( s instanceof RuleStopState) return true;
if ( visitedStates.contains(s) ) return false;
visitedStates.add(s);
//System.out.println("visit "+s);
int n = s.getNumberOfTransitions();
boolean stateReachesStopState = false;
for (int i=0; i<n; i++) {
Transition t = s.transition(i);
if ( t instanceof RuleTransition ) {
RuleTransition rt = (RuleTransition) t;
Rule r = g.getRule(rt.ruleIndex);
if ( rulesVisitedPerRuleCheck.contains((RuleStartState)t.target) ) {
addRulesToCycle(enclosingRule, r);
}
else {
// must visit if not already visited; mark target, pop when done
rulesVisitedPerRuleCheck.add((RuleStartState)t.target);
// send new visitedStates set per rule invocation
boolean nullable = check(r, t.target, new HashSet<ATNState>());
// we're back from visiting that rule
rulesVisitedPerRuleCheck.remove((RuleStartState)t.target);
if ( nullable ) {
stateReachesStopState |= check(enclosingRule, rt.followState, visitedStates);
}
}
}
else if ( t.isEpsilon() ) {
stateReachesStopState |= check(enclosingRule, t.target, visitedStates);
}
// else ignore non-epsilon transitions
}
return stateReachesStopState;
}
/** enclosingRule calls targetRule. Find the cycle containing
* the target and add the caller. Find the cycle containing the caller
* and add the target. If no cycles contain either, then create a new
* cycle.
*/
protected void addRulesToCycle(Rule enclosingRule, Rule targetRule) {
//System.err.println("left-recursion to "+targetRule.name+" from "+enclosingRule.name);
boolean foundCycle = false;
for (Set<Rule> rulesInCycle : listOfRecursiveCycles) {
// ensure both rules are in same cycle
if (rulesInCycle.contains(targetRule)) {
rulesInCycle.add(enclosingRule);
foundCycle = true;
}
if (rulesInCycle.contains(enclosingRule)) {
rulesInCycle.add(targetRule);
foundCycle = true;
}
}
if ( !foundCycle ) {
Set<Rule> cycle = new OrderedHashSet<Rule>();
cycle.add(targetRule);
cycle.add(enclosingRule);
listOfRecursiveCycles.add(cycle);
}
}
}
|
