87 releases (4 stable)
1.0.3 | Nov 19, 2024 |
---|---|
1.0.1 | Oct 8, 2024 |
0.31.0 | Jun 21, 2024 |
0.26.1 | Feb 13, 2024 |
0.2.3 | Nov 30, 2021 |
#13 in Parser tooling
648 downloads per month
Used in 15 crates
(5 directly)
1MB
23K
SLoC
About parol
parol is a LL(k) and a LALR(1) parser generator for Rust.
It's an installable command line tool that can generate complete parsers from a single grammar
description file including all AST data types you would otherwise had to design by yourself. parol
does this solely by analyzing your language's grammar. parol
is also a library that you can use in
your own crates.
You can control the process of AST type generation. First you can mark elements for omission in your AST. Also you can specify your own types for language elements.
Language description and language implementation is strictly separated in parol
. Thus you can
design your language's grammar without any need to process anything because generated parsers
function by default as acceptors. This empowers you to do a real rapid prototyping of your grammar.
parol
generates a trait as interface between your language processing and the generated parser.
The trait contains functions for each non-terminal of your grammar which you can implement for
non-terminals you need to process. In the simplest case you only implement the trait function for
the start symbol of your grammar which is called after the whole input string is parsed. This
function then is called with a parameter that comprises the complete structure of the parsed
document.
The parser calls the interface trait's functions via a separately generated adapter automatically during the process of parsing.
With such a generated interface trait you theoretically never have to let parol
generate new code
for you anymore and you can concentrate on the development of your language processing. Although,
often a more iterative approach is taken.
Generated parsers
- are true LL(k) parsers implemented by push down automata (PDAs).
- are predictive, i.e. they implement a non-backtracking parsing technique. This often results in much faster parsers.
- are clean and easy to read.
- use only as much lookahead as needed for a certain non-terminal (from 0 to k)
- are generated from a single grammar description file.
- can generate types that resemble the AST of your grammar automatically. Semantic actions are then called with these types. This greatly improves the development process and makes it less error-prone.
- As of version 0.24.0 generated parsers can recover from syntax errors automatically
- As of version 0.28.0
parol
starts to support LR style grammars as well, in detail LALR(1) grammars. Please have a look at the CHANGELOG
Other properties of parol
- Selection of production is done by a deterministic finite lookahead automaton for each non-terminal.
- Semantic actions with empty default implementations are generated as a trait. You can implement this trait for your grammar processing item and implement only needed actions. This provides a loose coupling between your language definition and the language processing.
- As a result semantic actions are strictly separated from the grammar definition in contrast to Bison. No parser generation step is needed when you merely change the implementation of a semantic action.
- The grammar description is provided in a Yacc/Bison-like style with additional features known from EBNF such as grouping, optional elements and repetitions.
- You can define multiple scanner states (aka start conditions) and define switches between them directly in the productions of your grammar.
- You can opt out the default handling of whitespace and newlines for each scanner state separately.
- The grammar description supports definition of language comments via %line_comment and %block_comment declarations for each scanner state.
- The crate provides several tools for grammar analysis, transformation and parse tree visualization to support your grammar implementation.
- The parser generator detects direct and indirect left recursions in your grammar description.
parol
's parser is generated byparol
itself.- Use
parol new
to create your own crate that usesparol
.
Why should you use LL(k) parsers in your language implementation?
LL parsing technique is a top-down parsing strategy that always starts from the start symbol of your grammar. This symbol becomes the root node of the parse tree. Then it tries to derive the left-most symbol first. All such symbols are then processed in a pre-order traversal. During this process the parse tree is created from the root downwards.
Both, processing the input and producing the parse tree in 'natural' direction ensures that at every
point during parsing you can see where you came from and what you want to derive next. parol
's
parse stack contains 'End of Production' markers which reflect the 'call hierarchy' of productions.
This tremendously helps to put your language processing into operation. In contrast, anyone who has ever debugged a LR parser will remember the effect of 'coming out of nowhere'.
Although LL grammars are known to be less powerful than LR grammars many use cases exist where LL grammars are sufficient. By supporting more than one lookahead token the abilities of traditional LR(1) grammars and LL(k) grammars become more and more indistinct.
Why should you use parol
?
parol
is simple. You can actually understand all parts of it without broader knowledge in parsing
theory.
parol
is fast. The use of deterministic automata ensures a minimal overhead during parsing, no
backtracking needed.
parol
is a true LL(k) parser. You won't find much working LL(k) parsers out there.
parol
generates beautiful code that is easy to read which fosters debugging.
parol
is young. Although this might be a problem some times, especially regarding the stability of
the API, the best is yet to come.
parol
is actively developed. Thus new features are likely to be added as the need arises.
Documentation
Examples
This project contains some introductory grammar examples from entry level up to a more complex C-like expression language and an acceptor for Oberon-0 grammar.
A complete Oberon-2 acceptor generated by parol
can be found in the examples of this
repository.
A rudimentary Basic interpreter strives to mimic a small part of C64 Basic.
A TOML parser can be found here.
I also provide a JSON Parser.
parol
's input language processing is an additional and very practical example.
The book
A book explains some internals and the practical use of parol
in detail. It is still a work in
progress but should be considered as the central documentation.
The video
This video explains the installation of parol
and the language server to setup your working
environment. Then it shows the process of designing grammars with parol
with the help of an
example project.
State of the project
parol
has proved its ability in many examples and tests during its development. Early adopters can
quite safely use it.
But parol
is not ready for production yet. Features are still in development and the crate's
interface can change at any time. There is still a lot of work to be done and any help is
appreciated.
Dependencies
Please note that any necessary dependencies are automatically added to your new parol
project if
you use the parol new
subcommand to create your new crate. The following sections are therefore
for information only.
Runtime library
Parsers generated by parol
have to add a dependency to the
parol_runtime crate. It provides the scanner and parser
implementations needed. The parol_runtime crate is very lightweight.
Macros
As of version 0.13.0 you have to add the parol-macros
crate to your dependencies if you use parol
's auto-generation mode.
License
parol
and its accompanied tools included in this workspace are free, open source and permissively
licensed! Except where noted (below and/or in individual files), all code in this repository is
dual-licensed under either:
- MIT License (LICENSE-MIT or http://opensource.org/licenses/MIT)
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
at your option. This means you can select the license you prefer!
Your contributions
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.
Further readings
Contributors
Thanks to all the contributors for improving this project!
Dependencies
~13–24MB
~346K SLoC