Open breml opened 6 years ago
Hello Lucas,
I ran into the same issue and created this repo with what I had as minimal reproducible grammar (yours is smaller, though): https://github.com/mna/pigeon-bug-optimize-grammar-2. I tested it with your fix in the pending PR and it does work, is there any side-effect preventing the fix from being merged?
Thanks, Martin
Hi @mna If I remember correctly, the reason why I did not yet merge this PR is, that it only solves part of the problem. I had cases where the optimize still failed. That being said, we can merge this one and at least improve the situation, even though there are still failing (edge) cases.
Ah, yeah indeed I tried it on my full grammar and it does fail elsewhere with this fix. Might be worth holding up, as it might break grammars that are otherwise working today (for those that didn't run into the issue that it solves). I'll try to find some time to investigate further next week.
Thanks, Martin
I found the old commit and my notes about the bigger problem I found when I wrote the PR #71.
The thing is, that the added search algorithm in ast_optimize.go
is not able to find unnecessary rules, if these rules do form a cycle, but the entire rules cycle is no longer reachable from one of the entry points.
Such cycles can be produced by the grammar optimizer. I found such a case in the go-thrift grammer when I tried to use the optimize
option. I reduced the grammar to the following minimal example, extracted out of the optimized grammar from go-thrift:
{
package issue70_cycle
}
TypeDef ← annotations:TypeAnnotations?
FieldType ← SubType
SubType <- typ:FieldType annotations:TypeAnnotations?
TypeAnnotations ← annotations:TypeAnnotation*
TypeAnnotation ← value:(value:'X' { return value, nil })?
So the bottom line is, that the search algorithm needs to be extended with something like this:
The following grammar results in build failure, if generated with
--optimize-grammar
. The same grammar builds with out problem, if the option is not set.Minimal example:
Build error: