Detect non-disjoint alternatives
RunDevelopment opened this issue · 2 comments
RunDevelopment commented
To prevent exponential backtracking, the alternatives of a quantified group have to be disjoint (aside from the empty string and assertions).
For a RE /(A1|A2|...|An)*/, its alternatives have to disjoint such that:
∀ Aj: ( L(/(A1|...|Aj-1|Aj+1|An)*/) ∩ L(/Aj*/) ) \ {ε} = ∅ where L is a function which returns the language of the given RE and ε is the empty string.
This will be difficult to implement because we need to be able to construct an NFA from the RE and assertions don't make this any easier.
RunDevelopment commented
Test case: (?=[\t ]+[\S]{1,}|[\t ]+['"][\S]|[\t ]+$|$)
RunDevelopment commented
Resolved by #22.