Grammar backtrace

[sunjay]

Currently, if you want to figure out what the parser was expecting when it failed, you call the parser's expected() method which tells you which rules could have been next and provides a position which can be referenced in the source.

Unfortunately, when debugging a grammar, it can be difficult to use that information alone to figure out what went wrong. Especially in large grammars, knowing the next expected token doesn't always give you enough of the picture to figure out what went wrong. The expected token may be used in many places.

You can make an educated guess from the given source position, but it is hard to know for sure if your assumptions can be trusted.

It would be convenient if, when returning an error, the parser could generate a "backtrace" through the grammar which would inform us of exactly which path through the rules failed.

This is not a cheap calculation, so it should be saved for error cases and even possibly only done behind a feature flag which doesn't even compile that code unless the user adds a features section in their Cargo.toml.

[hansihe]

I gave porting a grammar from rust-peg a go, and I really like a lot of the design decisions and features.

However, without any debugging or tracing support, I find this difficult to use for more advanced grammars. Even just a trace of what rules are matched and which are not would be really helpful for debugging.

Just writing this to express interest.

[dragostis]

@hansihe, you should give https://pest-parser.github.com a try. It has an editor that helps. But, yes, this is something needed.

By the way, if you're curious about writing an Erlang grammar in pest, I'd be more than willing to help out! ❤️

[dragostis]

I've tried writing a solution to this and it's a bit more involved to get a decent trace. Basically, all positive and negative rules in an Error have their own trace which leads to a lot of information.

Maybe something more pragmatic would be a way to debug parsing as it happens? But I don't know exactly how that's supposed to work.

[hansihe]

I have a mostly complete grammar written in pest, and I'll push it if you want to have a look at it. There are a couple of issues I am having trouble figuring out when I don't have any tracing available.

I gave the editor you linked a try, and it pointed out some issues in the grammar that I fixed, thanks!

I hacked together some simple debugging utilities for rust-peg that helped me out a lot. It involves a compile time option that, when enabled, writes a trace of events to a vector (rule started, rule failed to match/rule matched, some others). I then have some utilities for pretty-printing the trace with colors and indentation, and optional collapsing of successfully matched rules. I can imagine an interactive browser for the trace would be quite nice as well.

Maybe something similar would work well for pest, at least as a start?

[hansihe]

If you are interested, here is the WIP pest grammar for core erlang. There are some test files in the test_data directory (*.core).

I'm sure I have some left-recursion somewhere in the grammar, since it seems to go into an infinite loop on some inputs.