Quantcast

"Permutation" expression

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

"Permutation" expression

jms_nh
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/tutorial-20011203.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"



Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Permutation" expression

mathias
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/tutorial-20011203.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/Permutation-expression-tp2763524p2763524.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, click here.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Permutation" expression

sulfinu
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...
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: "Permutation" expression

mathias
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/Permutation-expression-tp2763524p3178729.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, click here.

Loading...