2 releases
0.1.1 | May 6, 2023 |
---|---|
0.1.0 | Apr 14, 2023 |
#167 in Parser tooling
320KB
6.5K
SLoC
IELR
This is an implementation of the IELR algorithm, described in a paper by Joel E.Denny and Brian A.Malloy: The IELR(1) algorithm for generating minimal LR(1) parser tables for non-LR(1) grammars with conflict resolution.
Usage
use ielr::{input, compute_table, Algorithm};
const START_NODE: input::Node = input::Node(0);
let grammar = input::Grammar::new();
// ...
// add grammar productions
// ...
let table = match compute_table(
Algorithm::Lalr(std::num::NonZeroU8::new(1).unwrap()),
&grammar,
[START_NODE],
) {
Ok((table, _statistics)) => table,
Err(_) => unimplemented!("handle error"),
};
For more complete examples, see the examples directory.
Purpose and scope
This crate is meant to be used by a parser generator. It builds the LR(1) table for a grammar, using an efficient and minimal algorithm.
Note that this crate does not include:
- A lexer.
- An actual parser generator: once you have the tables, you still need to use them to build the parser.
- A way to parse a grammar in a textual format: the grammar must be specified via code (e.g.
grammar.add_rule(left, right);
)
Future goals
At the moment, two algorithms are provided: LALR(1) and LR(1).
In the future, I would like to implement the following features:
- Extend the IELR algorithm to LR(k).
- Improve performance, especially when using precedence annotations.