Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Turn StateTableError to an enum, handle self-loop for #290 #294

Closed
wants to merge 1 commit into from

Conversation

ratmice
Copy link
Collaborator

@ratmice ratmice commented May 15, 2022

Here is at least an attempt to fix #290,
It appeared to me that bison ignores this case entirely (no additional errors or self recursion, besides the conflicts, and if you run the parser it won't loop forever), and I believe I see in the bison code where it ignores it.

It's worth pointing out the Accept/Reduce errors here with it's "Infinitely recursive rule let through",
I haven't yet gone and tried to fully understand what makes this case different from an Accept/Reduce.

I had to switch the error around here, because unless I am mistaken, at that point we don't appear to have any way to get a PIdx.

StateTableError previously required a PIdx.
At the point we discover this self loop we don't have one.

In order to convey this error change StateTableError into an enum,
combining the `pidx` field with its kind.
@ltratt
Copy link
Member

ltratt commented May 15, 2022

Interestingly if I take your example:

%%
Start: Bar;
Foo: "a" | ;
Bar: Foo | Foo Bar;

and run it on (traditional-ish) yacc I get:

yacc: 1 rule never reduced
tmp.y: yacc finds 2 shift/reduce conflicts
tmp.y: yacc finds 1 reduce/reduce conflict

but on Bison:

tmp.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
tmp.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
tmp.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
tmp.y:4.6-8: warning: rule useless in parser due to conflicts [-Wother]
    4 | Bar: Foo | Foo Bar;
      |    

In both cases we have a warning, not an error, but the yacc warning is IMHO clearer.

So we probably have two questions to think about:

  1. Should this be an error or a warning?
  2. What should we call it / pretty-print to the user etc?

@ratmice
Copy link
Collaborator Author

ratmice commented May 15, 2022

I think if we want to turn it into a warning we need to do something about the infinitely growing action vector when it hits that state.

(Although I guess my program should probably refuse to try and parse files, unless the number of conflicts to ignore is set appropriately).

I'm not exactly sure what the right way to go about I would assume replacing it with State 0?

@ltratt
Copy link
Member

ltratt commented May 15, 2022

We should probably do whatever yacc/bison does, at least if we're in YaccKind::Original mode. In YaccKind::Grmtools I think I'd be fine with throwing an error.

@ratmice
Copy link
Collaborator Author

ratmice commented May 16, 2022

I agree, in general with that (It seems like I overlooked the rule useless when I said bison produced no additional errors),
I think it at least is stretching my familiarity here with the existing code base to fix it in the way bison does.

I think at least the way this works in the bison way is by having states in the StateGraph which never get added to the StateTable. Where currently StateGraph and StateTable's StIdx if i understand are in 1:1 correspondence. But once we have states in the StateGraph which never enter into the StateTable I would think we'd need to shift indexes down whenever we skip a useless state.

For now though, I'm just going to work around it by not running generated parsers which have conflicts when the conflict limits are not specified (Should have probably been doing this already). So that i'm not in a rush to fix it, and can take the time to do it correctly.

@ltratt
Copy link
Member

ltratt commented May 16, 2022

Does that mean we should close this PR or ... ?

@ratmice
Copy link
Collaborator Author

ratmice commented May 16, 2022

Sorry, that's a weird cultural thing of not being terribly direct,

I'm fine with closing it if you want to, there is perhaps some useful information here, but that doesn't actually disappear if we do.

@ltratt
Copy link
Member

ltratt commented May 31, 2022

OK, agreed, we might as well close this -- it'll still be here.

@ltratt ltratt closed this May 31, 2022
ratmice added a commit to ratmice/grmtools that referenced this pull request Aug 17, 2022
This test case is not caught by the error that I proposed in pr softdevteam#294.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Apparently infinite recursive rule
2 participants