Could you please consider adding a pair of Permutation methods to the BaseParser class?
Use case: where a sequence of items is expected, but the order is unimportant as long as they each occur once. As far as I can tell, this is not possible with the existing Parboiled framework, unless you use OneOrMore(FirstOf(A,B,C,...)) and check afterwards for uniqueness of terms. Existing implementations in other parsers:  RELAX NG's "interleave" (http://relaxng.org/tutorial20011203.html#IDAN1YR)  Boost Spirit.Qi Parser's permutation operator (http://www.boost.org/doc/libs/1_46_1/libs/spirit/doc/html/spirit/qi/reference/operator/permutation.html) Example: public Rule expression() { return Permutation("A","E","I","O","U",Optional("Y")); } // this matches AEIOU, AEIOUY, OUIAE, UIAOYE, etc. but not AEIO or AAEIOU Behavior specification / implementation suggestion: Treat as a hybrid of Sequence and FirstOf, namely that each of the terms in the Permutation should be tried, in order, until one matches, and a Permutation of the remaining terms matches, in which case the entire permutation matches. Otherwise it fails. More specifically: // pseudocode boolean match_permutation(List<Rule> rule_list, Input input) { for Rule r : rule_list { if (r.match(input) && match_permutation(get_remaining_items(rule_list, r), input) return true; } return false; } Other examples: Permutation("AB", Optional("B"), "A") this matches "ABA", "AAB", "AABB", "ABBA", "BAAB", "BABA", and "ABAB" (this last one matches the sequence "AB", "A", "B", but never "A","B","AB") Permutation(Optional("ABC"), Optional("AB"), "C") this matches "ABCABC", "ABCCAB", "CABABC", "ABABCC", "CABCAB", "ABC", "CAB", "ABCC", "CABC", and "C" 
Administrator

Damn,
just now found your message by accident, in the spam. Sorry, for taking so long to reply. I think your request sounds like a good idea. I have already needed similar functionality a few times already... I just added a GH issue to track the feature. Cheers and thanks for the suggestions! Mathias  [hidden email] http://www.parboiled.org On 01.04.2011, at 16:35, jms_nh [via parboiled users] wrote: > Could you please consider adding a pair of Permutation methods to the BaseParser class? > > Use case: where a sequence of items is expected, but the order is unimportant as long as they each occur once. > > As far as I can tell, this is not possible with the existing Parboiled framework, unless you use OneOrMore(FirstOf(A,B,C,...)) and check afterwards for uniqueness of terms. > > Existing implementations in other parsers: > >  RELAX NG's "interleave" (http://relaxng.org/tutorial20011203.html#IDAN1YR) >  Boost Spirit.Qi Parser's permutation operator (http://www.boost.org/doc/libs/1_46_1/libs/spirit/doc/html/spirit/qi/reference/operator/permutation.html) > > Example: > > public Rule expression() { return Permutation("A","E","I","O","U",Optional("Y")); } > // this matches AEIOU, AEIOUY, OUIAE, UIAOYE, etc. but not AEIO or AAEIOU > > Behavior specification / implementation suggestion: > > Treat as a hybrid of Sequence and FirstOf, namely that each of the terms in the Permutation should be tried, in order, until one matches, and a Permutation of the remaining terms matches, in which case the entire permutation matches. Otherwise it fails. More specifically: > > // pseudocode > boolean match_permutation(List<Rule> rule_list, Input input) > { > for Rule r : rule_list > { > if (r.match(input) && match_permutation(get_remaining_items(rule_list, r), input) > return true; > } > return false; > } > > Other examples: > > Permutation("AB", Optional("B"), "A") > this matches "ABA", "AAB", "AABB", "ABBA", "BAAB", "BABA", and "ABAB" (this last one matches the sequence "AB", "A", "B", but never "A","B","AB") > > Permutation(Optional("ABC"), Optional("AB"), "C") > this matches "ABCABC", "ABCCAB", "CABABC", "ABABCC", "CABCAB", "ABC", "CAB", "ABCC", "CABC", and "C" > > > > > > If you reply to this email, your message will be added to the discussion below: > http://users.parboiled.org/Permutationexpressiontp2763524p2763524.html > To start a new topic under parboiled users, email [hidden email] > To unsubscribe from parboiled users, click here. 
I believe this shouldn't be achieved by generating all n! permutations, where n is the number of arguments of Permutations().
Right now, I simulate this with something like OneOrMore( FirstOf( Sequence(ACTION(noXAlready()), X()), Sequence(ACTION(noYAlready()), Y()), ... )) Parboiled could similarly keep track of already encountered items, instead of generating permutations via recursion. Take it as an option... 
Administrator

Yes, generating all n! permutations is certainly not a good idea.
Currently I'm thinking about implementing something similar to your logic that uses a bitfield for efficiently keeping the "already encountered" state ... Cheers, Mathias  [hidden email] http://www.parboiled.org On 18.07.2011, at 12:23, sulfinu [via parboiled users] wrote: > I believe this shouldn't be achieved by generating all n! permutations, where n is the number of arguments of Permutations(). > Right now, I simulate this with something like > OneOrMore( > FirstOf( > Sequence(ACTION(noXAlready()), X()), > Sequence(ACTION(noYAlready()), Y()), > ... > )) > Parboiled could similarly keep track of already encountered items, instead of generating permutations via recursion. Take it as an option... > > If you reply to this email, your message will be added to the discussion below: > http://users.parboiled.org/Permutationexpressiontp2763524p3178729.html > To start a new topic under parboiled users, email [hidden email] > To unsubscribe from parboiled users, click here. 
Free forum by Nabble  Scala forum  Edit this page 