Feature or enhancement
Proposal:
When pegen picks a leader for a left-recursive SCC, compute_left_recursives calls sccutils.find_cycles_in_scc from every node. That function walks every path through the SCC, so the work grows factorially with the SCC's size.
CPython's own grammar doesn't notice, because its biggest left-recursive SCC has two rules. But a third-party grammar with a handful of mutually left-recursive rules makes generation fall over:
| mutually left-recursive rules |
parser generation |
| 10 |
30 ms |
| 14 |
2.5 s |
| 9, with no valid leader (error path) |
0.48 s |
On a fully connected 8-rule SCC, that's about 1.07 million name comparisons before it reports "no leadership candidate".
A leader is a rule that sits on every cycle in the SCC. So you can test each candidate directly: remove it and check whether the rest is acyclic (a topological sort). That's O(V·(V+E)) per SCC, it picks the same leader (smallest name), and it raises the same error. The 14-rule case drops to about 8 ms, and the generated Parser/parser.c doesn't change.
I have a patch with tests ready.
Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Links to previous discussion of this feature:
No response
Linked PRs
Feature or enhancement
Proposal:
When pegen picks a leader for a left-recursive SCC,
compute_left_recursivescallssccutils.find_cycles_in_sccfrom every node. That function walks every path through the SCC, so the work grows factorially with the SCC's size.CPython's own grammar doesn't notice, because its biggest left-recursive SCC has two rules. But a third-party grammar with a handful of mutually left-recursive rules makes generation fall over:
On a fully connected 8-rule SCC, that's about 1.07 million name comparisons before it reports "no leadership candidate".
A leader is a rule that sits on every cycle in the SCC. So you can test each candidate directly: remove it and check whether the rest is acyclic (a topological sort). That's O(V·(V+E)) per SCC, it picks the same leader (smallest name), and it raises the same error. The 14-rule case drops to about 8 ms, and the generated
Parser/parser.cdoesn't change.I have a patch with tests ready.
Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Links to previous discussion of this feature:
No response
Linked PRs