RFC: Implement grammar with macros 1.1.

[dragostis]

There are currently two important issues that hinder the development experience when using pest. The first is the fact that macro expansions (especially the recursive definitions within the grammar! macro) do not give descriptive errors. This is a limitation of the macro system and cannot be amended with the current system.

The second issue is the non-linear growth in compile time with respect to the size of the grammar. This is in part because of the slow expansion of the recursive macros but also the bloated code that it generated which takes quite some time to compile. A ~700 line grammar compiles in ~30s on a newish system while generating over 20K lines of Rust code. (mileage may vary a lot)

The proposed solution would be to take advantage of the current implementation of macros 1.1 which permits an extra line to be added before the struct. This solution was documented by @tomaka and looks something like this:

#[derive(Parser)]
#[grammar("ruby.pest")]
struct MyParser;

The procedural macro would then open the grammar file, parse it and generate the code for the parser. The parsing would be done with a very simple manually-written recursive descent parser and a lexer.

This approach has several important advantages:

• eliminates the large compile times by parsing linearly and generating a smaller amount of code
• prints precise, detailed errors from the manual parser
• does not add any big dependency (like syntex)
• permits cleaner grammar (e.g. "def" instead of the current ["def"])
• allows grammar to be optimized statically (reordering rules, phasing out common parts etc.)
• allows the parser to consider caching an intermediate result (combination between a recursive descent and a Packrat; most of the times caching is expensive and not worth it)

The major disadvantage of this approach is the fact that the process! macro would have nowhere to be added to. One idea would be to add it to the .pest grammar file and then pass it to pest to compile. Another approach would be to have it outside:

#[derive(Parser)]
#[grammar("ruby.pest")]
struct MyParser;

impl MyParser {
    process! {
        ...
    }
}

As far as I know, this also means that the grammar! macro would have to form a separate crate which is but a minor disadvantage.

Alternatives to this would be to wait for macros 2.0, but that may be a long wait. Another alternative was to have a separate crate that analyzes the grammar and provides errors and which can also test your grammar dynamically for fast prototyping.

[Keats]

Feel free to ping me if you need a guinea pig!

[dragostis]

@Keats Awesome. I'm working on the procedural branch. I'm currently trying to figure out a data structure that permits efficient parallelization.

[dragostis]

Further discussion lead to the following design choices:

• [x] implement derive macro that reads from a grammar file
• [ ] improve pest grammar parsing errors (maybe use the same errors?)
• [x] implement TokenStream
  • [x] expand
  • [ ] repeat
• [ ] Parser trait should be simplified to only a few methods (new and parse(&mut self, rule: Rule) -> TokenStream come to mind); all required methods should be implemented as _pest_{name}
  • [ ] generate atomic sub-rules
  • [ ] generate non-atomic sub-rules
• [x] Error should should probably have 3 implementations:
  • [x] ParsingError which has some public expected and unexpectedRules
  • [x] CustomErrorPos with message and pos
  • [x] CustomErrorSpan with message, start, and end
• [ ] implement an Error type that knows its line and column and with a &Input it should know how to format itself in a rustc way
• [x] remove process!
• [ ] implement grammar assertion macros.
• [x] try to optimize the grammar
  • [x] find common parts
  • [x] concatenate string sequences
  • [ ] force atomicity of rules that are always called in atomic rules

[sunjay]

I'm also happy to be a tester once this is ready!

[sunjay]

I think we should keep the process macro and adopt the approach you suggested above:

#[derive(Parser)]
#[grammar("ruby.pest")]
struct MyParser;

impl MyParser {
    process! {
        ...
    }
}

It's good enough for now and it allows the user to implement further non-matcher methods on the parser as needed. Since process! is mostly Rust code (baring the patterns in the matchers), it makes sense to keep that stuff in Rust source files so the compiler can check them.

[dragostis]

Right now, I'm pretty confident about a Stream implementation that would replace process!.