Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Optimize pure string alternatives #115

Open
sirthias opened this issue Dec 2, 2014 · 1 comment
Open

Optimize pure string alternatives #115

sirthias opened this issue Dec 2, 2014 · 1 comment
Labels
Improvement

Comments

@sirthias
Copy link
Owner

sirthias commented Dec 2, 2014

Rather than matching

"foo" | "bar" | "baz"

with the usual "first match" strategy we can optimize the whole match at compile time and produce a simple DFA for it which only needs the minimal number of comparisons for determining a match (and no backtracking).
@alexander-myltsev
Copy link
Contributor

@sirthias , case match in FirstOf would become gigantic: it needs to match all combinations of FirstOf, StringMatch, CharMatch, and "otherwise".

Can we add a new rule as follows?:

def anyOfStrings(strings: String*): Rule0

barnardb added a commit to barnardb/parboiled2 that referenced this issue Mar 3, 2017
@barnardb
Select the longest matching key in matchMap
706eca2 
Fixes sirthias#136

By checking keys from longest to shortest, we ensure that we always
select the longest matching key.

This fix requires sorting the keys each time the rule is invoked. If
sirthias#115 gets implemented, this could be improved to make use of it instead.
@barnardb barnardb mentioned this issue Mar 3, 2017
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Improvement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@sirthias @alexander-myltsev