Parse grammar sentences via "Earley Parsing"

[CrockAgile]

What

Closes #67

This adds the ability for Grammar to parse an input sentence according to its Productions.

That parsing is implemented according to "Earley parsers" (which I learned about while doing this!)

I won't try to poorly explain the Earley parsing algorithm here, but some great resources are:

• https://loup-vaillant.fr/tutorials/earley-parsing/
• https://en.wikipedia.org/wiki/Earley_parser
• https://github.com/shnewto/earley

Example

use bnf::Grammar;

let input =
    "<dna> ::= <base> | <base> <dna>
    <base> ::= \"A\" | \"C\" | \"G\" | \"T\"";
let grammar: Grammar = input.parse().unwrap();

let sentence = "GATTACA";

let mut parse_trees = grammar.parse_input(sentence);
match parse_trees.next() {
    Some(parse_tree) => println!("{}", parse_tree),
    _ => println!("Grammar could not parse sentence"),
}

/* output:
<dna> ::= <base> <dna>
├── <base> ::= "G"
│   └── "G"
└── <dna> ::= <base> <dna>
    ├── <base> ::= "A"
    │   └── "A"
    └── <dna> ::= <base> <dna>
        ├── <base> ::= "T"
        │   └── "T"
        └── <dna> ::= <base> <dna>
            ├── <base> ::= "T"
            │   └── "T"
            └── <dna> ::= <base> <dna>
                ├── <base> ::= "A"
                │   └── "A"
                └── <dna> ::= <base> <dna>
                    ├── <base> ::= "C"
                    │   └── "C"
                    └── <dna> ::= <base>
                        └── <base> ::= "A"
                            └── "A"
*/

Misc

Also, it has been a while since this crate got an update. I bumped into quite a few new Clippy warnings while working, so I apologize that the PR touches other files randomly 😓

[codecov[bot]]

Codecov Report

Merging #92 (f811cf3) into main (37173d6) will increase coverage by 1.98%. The diff coverage is 90.65%.

@@            Coverage Diff             @@
##             main      #92      +/-   ##
==========================================
+ Coverage   91.94%   93.93%   +1.98%     
==========================================
  Files          10       11       +1     
  Lines         869     1187     +318     
==========================================
+ Hits          799     1115     +316     
- Misses         70       72       +2     

Impacted Files	Coverage Δ
src/term.rs	96.03% <ø> (+2.90%)	:arrow_up:
src/earley.rs	87.27% <87.27%> (ø)
src/expression.rs	96.42% <90.47%> (+0.94%)	:arrow_up:
src/production.rs	93.24% <92.85%> (+4.69%)	:arrow_up:
src/grammar.rs	97.11% <97.70%> (+7.01%)	:arrow_up:
src/error.rs	82.53% <100.00%> (+7.96%)	:arrow_up:
... and 1 more

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 37173d6...f811cf3. Read the comment docs.