Rustemo

LR/GLR parser generator for Rust (currently only LR).

Status: In early phase. Fairly complete feature set for the initial release. Not yet optimized for speed so don't expect blazing performance.

Feedback is welcome!

Be sure to check the docs!

Aspirations

• Both LR and GLR parsing from the same grammar

  E.g. start with GLR for easier development and refactor to LR for performance, or start from LR and move to GLR if your language needs more than 1 token of lookahead or is inherently ambiguous.

• Usability and error reporting

  Rustemo should be easy to use with sane defaults. Each error should be caught and explained with sufficient details. The docs should always be up-to-date and all docs examples should be tested by CI.

• Clean separation of CFG grammar and semantic actions written in Rust

  So a regular editors can be used for editing Rust code to its full potential. At the same time the syntax of the language is kept clean and existing grammars can be easily ported to Rustemo.

• Syntax sugar for common patterns

  E.g. zero-or-more(*), one-or-more (+), optional(?), groups (()), multiple match with a separator etc.

• Clean separation between lexer, parser and builder

  A parser asks a lexer for next tokens during parsing while telling the lexer what is expected due to the current parsing context. This avoids certain classes of lexical ambiguities. The parser calls builder to produce the result on each parser operation.

• Flexibility

  Default lexers and builders are provided/generated out-of-the box but the user can choose to write custom lexer and/or builder.

  When a custom lexer/builder is provided Rustemo can be used to parse virtually any kind of sequence and also build any kind of output.

• Inference of AST node types from the grammar

  For the default built-in builder, AST node types and semantics actions should be inferred from the grammar and auto-generated, but the user can introduce manual changes.

• Zero-copy by default

  Built-in builders should by default produce outputs by borrowing from the input.

• High test coverage

  There are a reasonable number of tests. I usually write tests before implementing each new feature (TDD). Tests are a good source of info until the docs are improved.

Roadmap (tentative)

v0.1.0

• [x] LR parsing.
• [x] Bootstrapping. Rustemo is implemented in itself.
• [x] Built-in lexer for parsing strings. Support for custom lexers.
• [x] Built-in builders: AST, generic CST, slice builder. Support for custom builders. Passing context to actions. See the tests .
• [x] Actions providing AST build are auto-generated but can be manually modified. Manual modifications are preserved on code re-generation while new types/actions are added to the file. This allow for fast development while keeping full control over the AST.
• [x] Regex-like syntax sugar. See the tests.
• [x] Repetition modifiers (e.g. separator)
• [x] Disambiguation filters: priorities, associativities.
• [x] Rule/production meta-data. E.g. production kinds.
• [x] CLI and API. A rcomp compiler CLI is available that can be called on Rustemo grammars. Also an API enables integrating parser compiling into Rust build.rs scripts. See the calculator example or integration tests.
• [x] Tracking of position and reporting error with line/column works.
• [x] Support for a layout (comments, whitespaces given as CFG). It is implemented as a special grammar rule and parsed by the LR parser. Result is passed by context to actions which can do whatever they please. E.g. a generic tree builder keeps layout on the following tree leaf. See the tests.
• [x] Detailed error reporting during grammar analysis and state machine building.
• [x] Docs completed.
• [x] First release to crates.io!

v0.2.0

• [ ] GLR parsing based on Right-Nulled GLR algorithm (RNGLR).
• [ ] Greedy repetitions.
• [ ] Zero copy for built-in builders.
• [ ] Parenthesized groups. Still not sure if this is a good thing to have. Sometimes it can nicely reduce clutter but if used too much it lowers readability.

v1.0

• [ ] Grammars compositions. Grammars importing, rule inheritance etc.
• [ ] Better disambiguations (investigate dynamic).
• [ ] Visualizations/debugging of GLR parsing process.

Post v1.0

• [ ] Error recovery, e.g. an approach taken by tree-sitter.
• [ ] Incremental parsing (reparse just the changed part of the input).
• [ ] Elkhound style of LR/GLR switching.
• [ ] Tooling for working with Rustemo grammars (e.g. LSP server, plugins for popular editors).

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Credits

Bootstrapping approach and the idea of macro for loading the generated code are based on the approach taken in the LALRPOP project.

Similar projects

The architecture and the general idea of Rustemo is loosely based on a similar project for Python, called parglare, I've started several years ago.

I have found a lot of inspiration and ideas in the following projects:

• LALRPOP - LR(1) parser generator for Rust. This project is the most similar to Rustemo so I've found there a lot of nice ideas.
• Nom - Parser combinator library. Nice architecture and nicely designed traits.
• pest - PEG parser for Rust. Seems nice and well maintained.

Why this name?

Rustemo is pronounced the same as Serbian word "растемо" which means "we grow". The name is a tribute to the awesome and ever growing Rust community.