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.