help wantedoptimization
Repository metrics
- Stars
- (3,456 stars)
- PR merge metrics
- (30d に merged PR はありません)
説明
For example, s -> "a" | s s goes into an infinite loop a good fraction of the time.
There's a couple of solutions to this. The one I implemented in my library for working with CFGs is based on this paper, though if you actually want to go this route I recommend looking at or asking me about this other thing I made instead, which is a simplification and generalization of this algorithm which I haven't gotten around to applying to CFGs yet (but it should be almost trivial to do so).
The other classic solution is to bound depth of the tree and backtrack when you've exceeded the bound without getting rid of all nonterminals.