Parsing Expression Grammars in Rust
This is a simple parser generator based on Parsing Expression Grammars.
Please see the release notes for updates.
Grammar Definition Syntax
use name;
The grammar may begin with a series of use
declarations, just like in Rust, which are included in
the generated module. Since the grammar is in its own module, you must use super::StructName;
to
access a structure from the parent module.
The remainder of the grammar defines a series of grammar rules which match components of your language:
pub rule_name = expression
If a rule is marked with pub
, the generated module has a public function that begins parsing at that rule.
Expressions
"literal"
- match a literal string[a-zA-Z]
- match a single character from a set[^a-zA-Z]
- match a single character not in a set.
- match any single charactersome_rule
- match a rule defined elsewhere in the grammar and return its resultsome_template<arg1, arg2>
- Expand a template rule with parameterse1 e2 e3
- Match expressions in sequencee1 / e2 / e3
- Try to match e1. If the match succeeds, return its result, otherwise try e2, and so on.expression?
- Match one or zero repetitions ofexpression
. Returns anOption
expression*
- Match zero or more repetitions ofexpression
and return the results as aVec
expression+
- Match one or more repetitions ofexpression
and return the results as aVec
expression*<n>
- Matchn
repetitions ofexpression
and return the results as aVec
expression*<n,m>
- Match betweenn
andm
repetitions ofexpression
and return the results as aVec
.expression*<{foo}>
- Evaluate the Rust expressionfoo
returning usize and match that many repetitions ofexpression
expression ** delim
- Match zero or more repetitions ofexpression
delimited withdelim
and return the results as aVec
expression **<n,m> delim
- Match betweenn
andm
repetitions ofexpression
delimited withdelim
and return the results as aVec
expression ++ delim
- Match one or more repetitions ofexpression
delimited withdelim
and return the results as aVec
&expression
- Match only ifexpression
matches at this position, without consuming any characters!expression
- Match only ifexpression
does not match at this position, without consuming any charactersa:e1 b:e2 c:e3 { rust }
- Match e1, e2, e3 in sequence. If they match successfully, run the Rust code in the block and return its return value. The variable names before the colons in the preceding sequence are bound to the results of the corresponding expressions. The Rust code must contain matched curly braces, including those in strings and comments.a:e1 b:e2 c:e3 {? rust }
- Like above, but the Rust block returns aResult
instead of a value directly. OnOk(v)
, it matches successfully and returnsv
. OnErr(e)
, the match of the entire expression fails and it tries alternatives or reports a parse error with the&str
e
.$(e)
- matches the expressione
, and returns the&str
slice of the input string corresponding to the match#position
- returns ausize
representing the current offset into the input string, and consumes no characters#quiet<expression>
- match expression, but don't report literals within it as "expected" in error messages.#expected("str")
- fails to match, and report the specified string as an expected symbol at the current location.#infix<atom> { ... }
- Parse infix expressions by precedence climbing. Details below.
Comments
You can use line comments and block comments just as in Rust code, for example:
// comment
name = /* weirdly placed comment */ n:$ // comment
Error reporting
When a match fails, position information is automatically recorded to report a set of "expected" tokens that would have allowed the parser to advance further.
Some rules should never appear in error messages, and can be suppressed with #quiet<e>
:
whitespace = # n\t]+>.
If you want the "expected" set to contain a more helpful string instead of character sets, you
can use #quiet
and #expected
together:
identifier = # zA-Z]+> / #expected
Infix expressions
#infix<atom> { rules... }
provides a convenient way to parse binary infix operators using the precedence climbing algorithm.
pub arithmetic = #
The atom (in this example, number
), is the rule used to parse the "things between the operators". It must be a name of a rule defined elsewhere in the grammar, not an expression, because its return type is used in the generated code. Each operator's action code and the #infix
expression as a whole return the same type as this rule. When building an AST, this type is commonly an enum with a variant for the atom, and variant(s) for operators.
Each #L
or #R
introduces a new precedence level that binds more tightly than previous precedence levels, and contains left (#L
) or right (#R
) associative operators. Each operator rule consists of a left operand variable name, an operator expression, a right variable name, and a Rust action expression. The Rust code has access to the two named operands.
You can think of the above example as a PEG parser number (("+" / "-" / "*" / "/" / "^") number)*
,
followed by precedence climbing to associate the atoms and operators into a tree following associativity and precedence rules, and running the action code for each level of the tree. No intermediate vector is allocated.
Template rules
Rule templating can reduce duplicated code in your grammar:
Example:
= E !identifierChar whitespace*
STRUCT = struct">
ENUM = keyword<"enum">
Templates are inlined every place they are used, and cannot be marked pub
.
Context arguments
You can pass parameters throughout the parser by adding a declaration like
#![arguments(filename: &str, interner: &mut Interner)]
to the top of your grammar. All public parse functions will take these additional arguments after the input string parameter, and they are available by name in all action code blocks.
For an example see the test.
The arguments will be passed to each internal parse function, so they must be Copy
or be a &
or &mut
reference. Be careful with mutable arguments. Remember that rule actions can run on parse
paths that later fail and do not contribute to the final parse.
Usage
With a build script
A Cargo build script can compile your PEG grammar to Rust source automatically. This method works on stable Rust.
Example crate using rust-peg with a build script
Add to your Cargo.toml
:
[] # this section should already exist
= "build.rs"
[]
= { = "0.5" }
Create build.rs
with:
extern crate peg;
(If you already have a build.rs
, just add the extern crate peg;
and the peg::cargo_build(...)
call.)
And import the generated code:
You can then use the pub
rules in the grammar as functions in the module. They accept a &str
to parse, and return a Result
with the parse result or parse error.
match my_rule
As a syntax extension
rust-syntax-ext
only works on Nightly builds of Rust.
Examples using rust-peg as a syntax extension
Add to your Cargo.toml:
[]
= "0.5.0"
Add to your crate root:
Use peg_file! modname("mygrammarfile.rustpeg");
to include the grammar from an external file. The macro expands into a module called modname
with functions corresponding to the pub
rules in your grammar.
Or, use
peg! modname;`
to embed a short PEG grammar inline in your Rust source file. Example.
As a standalone code generator
Run rust-peg input_file.rustpeg
to compile a grammar and generate Rust code on stdout.
Tracing
If you pass the peg/trace
feature to Cargo when building your project, a trace of the parsing will be output to stdout when running the binary. For example,
$ cargo run --features peg/trace
...
[PEG_TRACE] Matched rule type at 8:5
[PEG_TRACE] Attempting to match rule ident at 8:12
[PEG_TRACE] Attempting to match rule letter at 8:12
[PEG_TRACE] Failed to match rule letter at 8:12
...
Editor highlighting plugins
Users have created text editor syntax highlighting plugins for the .rustpeg
syntax:
- vim plugin by Trey Cordova
- vim plugin by rhysd