# IELR

[![License: MPL 2.0](https://img.shields.io/badge/License-MPL_2.0-brightgreen.svg)](https://gitlab.com/arnaudgolfouse/ielr/blob/main/LICENSE)
[![Latest Version](https://img.shields.io/crates/v/ielr.svg)](https://crates.io/crates/ielr)
[![Docs Status](https://docs.rs/ielr/badge.svg)](https://docs.rs/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](https://www.sciencedirect.com/science/article/pii/S0167642309001191).

## Usage

```rust
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](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.