Prevent backtracking in parser (cuts)

[Malte S.]

Dear Tony and others,

Does the Kiama parser provide a combinator that acts as a backtracking
barrier, similar to the cut operator in Prolog?

Assume that I have a parsing rule similar to the following:

lazy val foo =
"keywordA" ~> argA ^^ NodeA |
"keywordB" ~> argB ^^ NodeB

I'd like to force the parser to fail if argA failed after "keywordA".

FastParse [1] has a combinator for this (~/), but FastParse doesn't
support left recursion (and is, in my humble opinion, in general a less
attractive library).

Cheers,
Malte

[1] http://www.lihaoyi.com/fastparse/

[Tony Sloane]

Hi Malte,

Thanks for your positive comments.

We don’t currently have a non-backtracking sequence parser combinator but something simple is not too hard to do. I’ve got a partial implementation now and will aim to finish it up soon. 

The plan is to release a release candidate for the next Kiama release soonish, so hopefully you will find this in there and can try it out.

regards,

Tony

--
You received this message because you are subscribed to the Google Groups "kiama" group.
To unsubscribe from this group and stop receiving emails from it, send an email to kiama+un...@googlegroups.com.
To post to this group, send email to ki...@googlegroups.com.
Visit this group at https://groups.google.com/group/kiama.
For more options, visit https://groups.google.com/d/optout.

[Malte S.]

Hi Tony,

That sounds great, thank you! I'll keep an eye open for release
candidate announcements.

Best regards,
Malte

> to kiama+un...@googlegroups.com <mailto:kiama+un...@googlegroups.com>.

> To post to this group, send email to ki...@googlegroups.com

> <mailto:ki...@googlegroups.com>.

[Tony Sloane]

The cut-based parsing changes are in the following commit if you want to try them out:

https://bitbucket.org/inkytonik/kiama/commits/efa635b144b75200546550dac765f5bacd93472f

I’m aiming to publish an RC later this week.

regards,

Tony

[Malte S.]

Hi Tony,

Thanks a lot for implementing cuts so quickly! I briefly tried the new
combinator and it seems to work fine.

Two observations:

(1) It would be handy if there were non-backtracking versions of ~> and
<~ as well, e.g. ~/>. My assumption is that cuts are commonly useful
after keywords that uniquely determine what to parse next (and that
render any backtracking attempts futile), but keywords are of course
usually discarded during parsing. However, discarding them manually of
course also works (e.g. "myfancykeyword" ~ idnexp ^^ { case _ ~ id =>
... }).

(2) It seems that backtracking-preventing errors make it possible to
improve parser error messages, at least to some extent. E.g. a rule such as

"(" ~> argDeclList <~ ")" ^^ ...

where argDeclList parses a comma-separated list of formal argument
declarations, could be changed to

"(" ~> (argDeclList | error("Expected a comma-separated ...")) <~ ")"
^^ ...

in order to provide better error reporting.

Does that seem like a reasonable use of the new errors?


Many thanks and best regards,
Malte

[Tony Sloane]

Hi Malte,

I’ve created a ticket:

https://bitbucket.org/inkytonik/kiama/issues/81/add-control-of-back-tracking-when-defining

I wonder if I could prevail upon you to add your feature requests there so we can track them more easily? They seem sensible so I’ll see what I can do.

thanks,

Tony

[Tony Sloane]

I’ve just pushed implementations of ~/> and <~/ that seem to work as intended. They will be in the next version.

https://bitbucket.org/inkytonik/kiama/commits/a364954

Yes, I expect that these combinators will be useful with the “error” combinator to improve error message. I haven’t done much experimentation with that, though.

regards,

Tony

On 7 May 2017, 1:58 PM +1000, Anthony Sloane <anthony...@mq.edu.au>, wrote:

Hi Malte,

I’ve created a ticket:

https://bitbucket.org/inkytonik/kiama/issues/81/add-control-of-back-tracking-when-defining

I wonder if I could prevail upon you to add your feature requests there so we can track them more easily? They seem sensible so I’ll see what I can do.

thanks,

Tony

[Malte S.]

Sorry for not responding earlier, I've bin travelling for a bit. Thanks
for implementing the input-discarding versions so quickly!

I might have an opportunity soon to experiment with using the new
combinators in combination with error reporting. Should I observe
something interesting then I'll report back here.

Best regards,
Malte