rust-lang / gll

GLL parsing framework.
Apache License 2.0
138 stars 25 forks source link

Redundant `X | X` rules are allowed and mismanaged. #126

Open eddyb opened 5 years ago

eddyb commented 5 years ago

This is a testcase that demonstrates the problem (in tests/basic.rs):

    multiple {
        A = X:"x" | Y:"x";
    }:
    A("x") => "\
1:1-1:2 => A::X(
    1:1-1:2,
)";

The output is the current one and is incorrect: both sides are "x" and should match or the situation should be statically denied. But only the first one is observed.

eddyb commented 5 years ago

I think a reasonable thing to do might be to use IndexSet instead of Vec in Or and make it an error to have duplicate rules (unless they have identical fields?).

CAD97 commented 5 years ago

I also think it would be reasonable to prohibit identically matching rules in a single Or disjunction.

eternaleye commented 3 years ago

One problem with prohibiting identically matching rules is that it reduces to grammar equality, which is undecidable for basically anything with the complexity of CFG or higher.