consider making Grammar a hashmap

[Carlyle-Foster]

Having Grammar be a simple list of productions is elegant enough, but it doesn't really model the structure of a BNF grammar properly since there's nothing in it's structure explicitly connecting the nonterminals on the right to the nonterminals on the left, making Grammar a hashmap<Term, Vec<Expression>> would allow users to traverse grammars out of the box and be a good middle-ground between the current flat grammars and a fully connected approach.
i'm still uncertain about this idea and it's relatively low priority for now, in the meantime any feedback would be appreciated.

[CrockAgile]

I think this is a fair point about Grammar. It will have to be a bit more complex than that, because there can be multiple Term -> [Expression]. But the need for this arises in a few places, including the EarleyParser. To still provide convenient iteration, BTreeMap will probably be desirable, and should be a non breaking change for users.

[Carlyle-Foster]

can't multiple Term -> [Expression]'s just be combined into one? it seems semantically equivalent

[CrockAgile]

I think yes it is semantically equivalent, but then in order to track which was used for parsing input, it is easier to use:

ProdId = 0, <start> ::= <a> <b>
ProdId = 1, <start> ::= <c> <d>

// record during parsing that ProdId(1) was used to match input text

compared to:

ProdId = 0, <start> ::= <a> <b> | <c> <d>

// record during parsing that ProdId(0) and Index(1) was used to match input text

maybe silly reason but it certainly helps me when reasoning about the parser.

also another maybe silly reason, but someday I hope to have an API that supports user provided constructors for parse nodes, which having only one Expression per Prod helps:

let my_parser = Grammer::new([
   ("<start> ::= 'a' 'b'", UserDefinedStart::from_a_and_b),
   ("<start> ::= 'c' 'd'", UserDefinedStart::from_c_and_d),
]);

// then use that parser
let parsed : UserDefinedStart = my_parser.parse("cd").next().unwrap();

[Carlyle-Foster]

couldn't we just do what we're doing now, using the normalized version for parsing but not exposing it to the user? if they give us s = a / b and s = c we combine it into s = a / b / c but normalize it to s = a, s = b and s = c before parsing

[Carlyle-Foster]

though know that i say that i realize it makes decomposing productions the same way u might compose them impossible

[Carlyle-Foster]

not sure if that's a compelling enough use case though, u can still decompose productions easily enough so long as they're normalized in the first place

[CrockAgile]

I locally migrated Grammar to use a HashMap and nearly all benchmarks saw performance worse.

I then tried BTreeMap, and saw results like:

Benchmark	Vec (mean)	BTreeMap (mean)	% diff
examples
generate_dna	771 ns	791 ns	+2.5%
parse_infinite_nullable_grammar	94.4 µs	93.0 µs	−1.5%
parse_polish_calculator	65.5 ms	67.4 ms	+2.8%
parse_postal	15.6 µs	20.8 µs	+33.9%
parse_postal_input	437 µs	420 µs	−4.0%
generation_strategies
generate_coverage_guided	6.37 µs	6.91 µs	+8.5%
generate_depth_bounded	3.24 µs	3.64 µs	+12.4%
generate_random_walk	3.02 µs	3.40 µs	+12.5%
generate_weighted	4.95 ms	5.24 ms	+6.0%
parser_api
build_polish_parser	762 ns	712 ns	−6.5%
build_postal_parser	4.85 µs	4.93 µs	+1.6%
parse_infinite_nullable_with_parser	93.2 µs	92.0 µs	−1.3%
parse_polish_with_parser	65.1 ms	65.2 ms	+0.2%
parse_postal_with_parser	448 µs	413 µs	−7.8%
per_input_100	4.17 s	3.88 s	−6.9%
reuse_parser_100	4.08 s	3.82 s	−6.5%

So with this mixed performance change, I think this migration would require some more pressing reasons. Such as:

• is there a use case the current API doesn't support that it should, and migrating to Map would help?
• what is "a fully connected approach" ?
• is the goal to eventually promote the same internal grammar used for parsing to the public Grammar so parsing doesn't require the middle step?

please comment and let me know what I am missing! but for now, I am going to remove this from the 0.6 release milestone