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

Grammar fails unexpectedly and then succeeds when Grammar::Tracer is imported in Rakudo #3611

Closed
p6rt opened this issue Dec 17, 2014 · 5 comments
Labels

Comments

@p6rt
Copy link

p6rt commented Dec 17, 2014

Migrated from rt.perl.org#123452 (status was 'rejected')

Searchable as RT123452$

@p6rt
Copy link
Author

p6rt commented Dec 17, 2014

From @masak

<masak> star​: grammar G { regex TOP { [<x> [';' | $$] \s*]* }; token x
{ B | \s* <y> \s* '()'* }; regex y { A | B } }; my $s = "B\nA();"; say
?G.parse($s)
<camelia> star-{m,p} 2014.09​: OUTPUT«False␤»
<masak> star​: use Grammar​::Tracer; grammar G { regex TOP { [<x> [';' |
$$] \s*]* }; token x { B | \s* <y> \s* '()'* }; regex y { A | B } };
my $s = "B\nA();"; say ?G.parse($s)
<camelia> star-{m,p} 2014.09​: OUTPUT«TOP␤| x␤| * MATCH "B"␤| x␤| |
y␤| | * MATCH "A"␤| * MATCH "A()"␤| x␤| | y␤| | * FAIL␤| *
FA…»
<masak> aww, the output cuts off too early to show that the grammar succeeds :/
* masak makes a gist
<masak> https://gist.github.com/masak/d10db42d5c6fd6d8d906
<vendethiel> masak​: is it deterministicly undeterministic?
<masak> yes.
<masak> personally, I think it should succeed even without
Grammar​::Tracer. (and that that's the bug)
<masak> but the fact that it comes out different with and without is
*clearly* wrong.
* masak submits rakudobug
<masak> things that cause the problem to go away​: inlining y into x.
inlining x into TOP. removing any of the remaining \s*. removing the *
after '()'.

@p6rt
Copy link
Author

p6rt commented Dec 17, 2014

From @masak

<TimToady> masak​: no, it makes the grammar behave wrong, it turns out
<TimToady> in parsing B\n, it matches the right side of x under LTM, and eats the newline that TOP needs to progress, so the next match fails to progress because $$ doesn't match
<TimToady> put a {} before the second \s* and it matches, because then it ties under LTM and works left-to-right instead
<TimToady> or change the 2nd \s* to a \h* and it works
<TimToady> so this turns out to be a bug in the tracer, I think
<TimToady> unless TOP should be backtracking to the left side of x, hmm
<TimToady> maybe it's a not-backtracking-into-subrule bug as well
<TimToady> I guess the token declarator for x is committing the match of the LTM in the alternation
<TimToady> if you change it to 'regex', it parses
<TimToady> so arguably that's correct behavior in rejecting the parse under 'token'
<TimToady> anything that subverts LTM would tend to make it do || semantics, so I'm guessing the tracer is subverting LTM somehow; does it work by inserting {} nodes?
<TimToady> if so, we need to teach LTM to ignore those nodes
<TimToady> or insert 'em as <!{stuff; 0}> instead, which LTM already ignores
* TimToady delegates the problem to anyone who will delegate it to someone else who is not TimToady :)
<TimToady> masak​: another way to fix your proggie is to change your [';' | $$] to match [';' | $$ | ^^] instead
<TimToady> but anyway, the bug report is at least partly right... .oO("It is a comfort not to be mistaken on all points." --Gandalf)
<masak> TimToady​: I added your comments to https://rt-archive.perl.org/perl6/Ticket/Display.html?id=123452

@p6rt
Copy link
Author

p6rt commented Dec 17, 2014

From @masak

<masak> I need to digest those comments, though. I don't understand where the grammar "eats the newline that TOP needs to progress".
<masak> and, oh yes, I also noticed that changing 'token x' to 'regex x' made the bug go away. that's one thing I failed to include.
<masak> ...but anyway. even not following all the details, I know it's wrong that Grammar​::Tracer heisenbugs the parse. :)
<masak> if it turns out the problem is *all* in Grammar​::Tracer, I'll happily re-file this as a Github issue.
<TimToady> masak​: the x rule matches a token of "B\n" and commits to that, but it must match only 'B' to allow the newline to match in TOP
<TimToady> it commits to "B\n" because that's the longesst token
<masak> why would the x rule ever match a "\n" after the "B"?
<TimToady> and it matches that because everything at the end is optional, including the ()
<TimToady> \s*
<TimToady> that's why changing \s* to \h* makes it work
<masak> oh, it goes into the *right* alternation...
<masak> I see.
<TimToady> or changing '()'* to '()'+
<masak> right.
<TimToady> or putting {} before the \s*
<masak> the ungolfed grammar is 108 lines. but you just provided some clues for how to fix it. thanks. :)
<moritz> whitespace. Still not a solved problem.
<jnthn> masak​: I highly suspect Grammar​::Tracer is doing something wrong. Note that when it was written, LTM was...rathre less advanced...than it is now.
<masak> yes, I think it's been established now that the problem is purely in Grammar​::Tracer.
<jnthn> OK
<jnthn> Then feel free to file a tikkit.
* masak does

Rejecting this ticket, as the problem seems to be entirely in Grammar​::Tracer, not in Rakudo.

See jnthn/grammar-debugger#13 for the ticket opened in Grammar​::Tracer.

@p6rt
Copy link
Author

p6rt commented Dec 17, 2014

@masak - Status changed from 'new' to 'rejected'

@p6rt p6rt closed this as completed Dec 17, 2014
@p6rt
Copy link
Author

p6rt commented Jul 2, 2016

From @masak

<masak> TimToady_​: ooc, do you agree that tracing a grammar breaks LTM matching? jnthn/grammar-debugger#13 (comment)
<jnthn> The solution, for whoever fancies implementing it, is probably to mix a role into the tracing closure that we hand back.
<jnthn> Where said role has the methods like !NFA or whatever on it and forwards them to the underlying code-ref
<jnthn> (That of the original rule)
<jnthn> Since the reason for the problem is, afaict, that the closure we return instead of the method lacks the NFA
<jnthn> OTOH, we could switch the NFA resolution to use lookup instead of find_method since it's after the original declarator
<jnthn> Then Grammar​::Tracer will just work and everyone won't have to re-solve the same problem if doing similar things.
<jnthn> In fact that's probably the better way, and then Grammar​::Tracer will Just Work again.
<jnthn> So let's do it that way :)
<jnthn> Then it'll freely fix other modules like Grammar​::Debugger and Grammar​::Profiler too I suspect.
* masak adds this insight to the RT ticket
<masak> jnthn​: um, where would the solution reside? in Rakudo, or in Grammar​::Tracer?
<jnthn> masak​: NQP

@p6rt p6rt added the Bug label Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant