<p>Have you considered converting this into a semantic problem?  Instead of grammar rules for all permutations of nonterminals { A, B, C }, simply have one rule to recognize (A | B | C)^3 together with special internal code that makes sure only one of each is recognized, otherwise it declares an error.  I would insert an empty production before the above clause, whose reduction triggers initialization of whatever you are using to count A's, B's, and C's, and one after, whose reduction triggers the counter check and (if necessary) asserts the error.  (of course this could get a bit tricky if the grammar is recursive through A, B, and/or C)</p>

CC BY-SA 3.0
2016-08-02T16:54:29.837Z
2016-08-02T16:54:29.837Z
PMar
<p>I do not think one needs a counter. Essentially you just check all the permutations but break </p>

<p>pseudo-code:</p>

<pre><code>perm-match(input, pattern)
     if pattern = nil return true

     foreach(rule in pattern)
         if (match(input, rule))
             perm-match(input - matchedpart, pattern - rule)
             break
         end
     end
     return false
end
</code></pre>

<p>Here is a more concrete example</p>

<p>Suppose we are trying to match any permutation of abcd and our string is bcda</p>

<ul>
<li>Step 1: Find the first matched symbol. In this case it is b</li>
<li>Step 2: Remove that symbol from our pattern and reduce the string: e.g., acd and cda  are left</li>
<li>Step 3: Repeat step 1 on the new strings
<ul>
<li>c matches in cda which leaves us with ad and da</li>
<li>a matches in da which leaves us with d and d</li>
<li>d matches in d which leaves us with nil in both strings</li>
</ul></li>
</ul>

<p>So you see this simple algorithm can check for a permutation quite easily by simply comparing "strings" out of order. Note that the complexity of the function is O(n!) worse case and O(1) best case. In a sense the we are keeping count by storing the symbols to match in an array. I would think this would be 
"fast" in general since one wouldn't deal with very large n in most cases.</p>

CC BY-SA 3.0
2012-03-23T16:55:57.963Z
My problem is: my $n$ does get very large - $n=50$ is quite common. Also, your method doesn't mesh well with standard LR parsing techniques - these phrases are sprinkled on a grammar that mostly contains non-permutation phrases.
Alex ten Brink
CC BY-SA 3.0
2012-03-23T07:51:37.137Z
2012-03-23T07:51:37.137Z
Uiy
<p>A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) $A_1$ through $A_n$. At the position of the permutation phrase, we'd like to see every one of these productions exactly once, but we are not interested in the ordering of these nonterminals.</p>

<p>For example:</p>

<pre><code>S &lt;- X { A, B, C } Y
</code></pre>

<p>is equivalent to:</p>

<pre><code>S &lt;- X  A B C  Y
S &lt;- X  A C B  Y
S &lt;- X  B A C  Y
S &lt;- X  B C A  Y
S &lt;- X  C A B  Y
S &lt;- X  C B A  Y
</code></pre>

<p>The concept seems to be introduced in <a href="http://dl.acm.org/citation.cfm?id=176454.176490">"Extending context-free grammars with permutation phrases"</a>. Therein it is also described how to parse these phrases in linear time using an LL(1) parser.</p>

<p>The paper <a href="http://dl.acm.org/citation.cfm?id=1030338">"Parsing permutation phrases"</a> describes a method for parsing permutation phrases using parser combinators. These are the only two papers I've found that talk about permutation phrases and how to parse them.</p>

<p>Seeing that we can easily parse these kinds of permutation phrases with LL(1) based parsers, my guess would be that we can do the same with LR(1) style parsers. My question is therefore:</p>

<blockquote>
  <p>Can a grammar containing permutation phrases be parsed in time linear in the input string size using LR(1) machinery while maintaining a reasonably sized table?</p>
</blockquote>

<p>Permutation phrases do not extend the power of context-free languages: as in my example above one can simply enumerate all possible permutations. However, the grammar then explodes as the resulting grammar can be of size $O(|G|!)$. This allows linear time parsing, but the size of the grammar becomes way too large.</p>

<p>The above approach works for any parsing algorithm (although it is not useful), so maybe we can do better for specific algorithms. We can reduce the blowup to 'merely' exponential ($O(2^{|G|})$) by encoding the phrases into the LR table: we can have LR items encode which productions have yet to be seen, and therefore reduce the blowup to all subsets of the permutation phrases.</p>

<p>Although this is better, it is of course not good enough - having a permutation phrase of 30 items would make the grammar unusable. There is still one part of LR parsing we haven't touched yet, and that is the actual stack-based procedure used for parsing. I imagine storing counters on the stack may be able to solve the problem, but I'm not sure how to do that.</p>

<p>I'm currently implementing a parser generator, and in the problem domain permutation phrases would be a gift from heaven. As I'm using LR(1) machinery, the above question followed.</p>

CC BY-SA 3.0
2012-01-27T16:09:41.153Z
The complexity of LR(1) parsing is already exponential in the size of the grammar without permutation phrases---except if you implement an "on the fly" computation of the parser, but then it feels more like an Earley parser than like a genuine LR(1) one.
Sylvain
CC BY-SA 3.0
2012-01-27T16:16:55.447Z
About the rest of your question: http://cstheory.stackexchange.com/questions/4962/do-there-exists-polynomial-size-cfg-that-describe-this-finite-language/4969#4969 shows an exponential lower bound on the size of a CFG for permutations, and by the usual polynomial construction of CFGs from PDAs, this entails an exponential lower bound on the size of the PDA as well.
Sylvain
CC BY-SA 3.0
2012-01-27T16:28:14.903Z
@Sylvain: I didn't know about the exponential worst case of LR(1) parsers - it's nearly always skimmed over in analyses. Luckily, the worst case seems to be quite rare, contrary to my method that always gives the full size blowup. About that other question: I saw it before, and it does indeed mean that modifying just the grammar or automaton won't be enough. I was however hoping that one could store extra information on the LR-stack, just like the LL method in the paper I linked, so the normal LR(1) table sizes are maintained.
Alex ten Brink
CC BY-SA 3.0
2012-01-27T17:07:16.257Z
I hadn't looked at the paper on LL(1).  Indeed, the implemented parser is no longer a PDA.  I still do not believe in the existence of a "reasonably-sized table", since membership for commutative context-free grammars is NP-complete (see e.g. http://dx.doi.org/10.3233/FI-1997-3112), but it's true that the hard instances might not be LR(1).
Sylvain
CC BY-SA 3.0
2012-01-27T19:35:12.517Z
@Sylvain: Can you elaborate on how question 4962 relates to this one?  In question 4962, permutation is fixed for each input length, and the strings to be permuted changes.  In the current question, we do not fix the permutation.  So I fail to see any real connection between them.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-27T20:13:16.337Z
@Tsuyoshito Ito: In LR(1) parsing a DPDA equivalent to the input grammar is first constructed and then run against the string to recognize.  As there exists a linear-sized CFG with permutation phrases for every permutation language, Yuval Filmus' paper (which is more comprehensive than his answer on cstheory: see http://www.cs.toronto.edu/~yuvalf/CFG-LB.pdf) shows that no such DPDA can be of polynomial size in the size of the input grammar.
Sylvain
CC BY-SA 3.0
2012-09-21T00:30:29.687Z
@Sylvain: Now I see (after eight months).  Thanks for the explanation!
Tsuyoshi Ito
CC BY-SA 3.0
2013-09-05T00:48:04.857Z
@D.W. In the original question, the permutations allowed by a _grammar with permutation phrases_ are not fixed in advance.  The same holds of the _permutation languages_ of Yuval Filmus in the linked paper: all the permutations of a fixed length are allowed.
Sylvain
CC BY-SA 3.0
2014-01-14T15:34:35.633Z
I am wondering what happens to the size of the tables if we would generate the permutations in Chomsky normal form. Would that not shrink the problem back to something manageable, i.e. polynomial? Especially with parsing algorithms that do this normalization implicitly (BRNGLR and GLL), this seems a relevant question.
Jurgen Vinju
<ds.algorithms><fl.formal-languages><parsing><context-free>
Permutation phrases with LR parsing
Alex ten Brink
# Permutation phrases with LR parsing

(Asked by: username_0 on 2012-01-27)

A permutation phrase is an extension to the standard (E)BNF context free grammar definitions: a permutation phrase $\{ A_1, \dots, A_n \}$ contains $n$ productions (or equivalently, nonterminals) $A_1$ through $A_n$. At the position of the permutation phrase, we'd like to see every one of these productions exactly once, but we are not interested in the ordering of these nonterminals.
For example:
S <- X { A, B, C } Y

is equivalent to:
S <- X  A B C  Y
S <- X  A C B  Y
S <- X  B A C  Y
S <- X  B C A  Y
S <- X  C A B  Y
S <- X  C B A  Y

The concept seems to be introduced in "Extending context-free grammars with permutation phrases". Therein it is also described how to parse these phrases in linear time using an LL(1) parser.
The paper "Parsing permutation phrases" describes a method for parsing permutation phrases using parser combinators. These are the only two papers I've found that talk about permutation phrases and how to parse them.
Seeing that we can easily parse these kinds of permutation phrases with LL(1) based parsers, my guess would be that we can do the same with LR(1) style parsers. My question is therefore:

Can a grammar containing permutation phrases be parsed in time linear in the input string size using LR(1) machinery while maintaining a reasonably sized table?

Permutation phrases do not extend the power of context-free languages: as in my example above one can simply enumerate all possible permutations. However, the grammar then explodes as the resulting grammar can be of size $O(|G|!)$. This allows linear time parsing, but the size of the grammar becomes way too large.
The above approach works for any parsing algorithm (although it is not useful), so maybe we can do better for specific algorithms. We can reduce the blowup to 'merely' exponential ($O(2^{|G|})$) by encoding the phrases into the LR table: we can have LR items encode which productions have yet to be seen, and therefore reduce the blowup to all subsets of the permutation phrases.
Although this is better, it is of course not good enough - having a permutation phrase of 30 items would make the grammar unusable. There is still one part of LR parsing we haven't touched yet, and that is the actual stack-based procedure used for parsing. I imagine storing counters on the stack may be able to solve the problem, but I'm not sure how to do that.
I'm currently implementing a parser generator, and in the problem domain permutation phrases would be a gift from heaven. As I'm using LR(1) machinery, the above question followed.

**Tags:** ds.algorithms, fl.formal-languages, parsing, context-free
> **Comments:**
> **username_1**: The complexity of LR(1) parsing is already exponential in the size of the grammar without permutation phrases---except if you implement an "on the fly" computation of the parser, but then it feels more like an Earley parser than like a genuine LR(1) one.  
> **username_1**: About the rest of your question: http://cstheory.stackexchange.com/questions/4962/do-there-exists-polynomial-size-cfg-that-describe-this-finite-language/4969#4969 shows an exponential lower bound on the size of a CFG for permutations, and by the usual polynomial construction of CFGs from PDAs, this entails an exponential lower bound on the size of the PDA as well.  
> **username_0**: @Sylvain: I didn't know about the exponential worst case of LR(1) parsers - it's nearly always skimmed over in analyses. Luckily, the worst case seems to be quite rare, contrary to my method that always gives the full size blowup. About that other question: I saw it before, and it does indeed mean that modifying just the grammar or automaton won't be enough. I was however hoping that one could store extra information on the LR-stack, just like the LL method in the paper I linked, so the normal LR(1) table sizes are maintained.  
> **username_1**: I hadn't looked at the paper on LL(1).  Indeed, the implemented parser is no longer a PDA.  I still do not believe in the existence of a "reasonably-sized table", since membership for commutative context-free grammars is NP-complete (see e.g. http://dx.doi.org/10.3233/FI-1997-3112), but it's true that the hard instances might not be LR(1).  
> **username_2**: @Sylvain: Can you elaborate on how question 4962 relates to this one?  In question 4962, permutation is fixed for each input length, and the strings to be permuted changes.  In the current question, we do not fix the permutation.  So I fail to see any real connection between them.  
> **username_1**: @Tsuyoshito Ito: In LR(1) parsing a DPDA equivalent to the input grammar is first constructed and then run against the string to recognize.  As there exists a linear-sized CFG with permutation phrases for every permutation language, Yuval Filmus' paper (which is more comprehensive than his answer on cstheory: see http://www.cs.toronto.edu/~yuvalf/CFG-LB.pdf) shows that no such DPDA can be of polynomial size in the size of the input grammar.  
> **username_2**: @Sylvain: Now I see (after eight months).  Thanks for the explanation!  
> **username_1**: @D.W. In the original question, the permutations allowed by a _grammar with permutation phrases_ are not fixed in advance.  The same holds of the _permutation languages_ of Yuval Filmus in the linked paper: all the permutations of a fixed length are allowed.  
> **username_3**: I am wondering what happens to the size of the tables if we would generate the permutations in Chomsky normal form. Would that not shrink the problem back to something manageable, i.e. polynomial? Especially with parsing algorithms that do this normalization implicitly (BRNGLR and GLL), this seems a relevant question.  

---

## 2 answers

### Answer by username_4 on 2016-08-02. Score: 1

Have you considered converting this into a semantic problem? Instead of grammar rules for all permutations of nonterminals { A, B, C }, simply have one rule to recognize (A | B | C)^3 together with special internal code that makes sure only one of each is recognized, otherwise it declares an error. I would insert an empty production before the above clause, whose reduction triggers initialization of whatever you are using to count A's, B's, and C's, and one after, whose reduction triggers the counter check and (if necessary) asserts the error. (of course this could get a bit tricky if the grammar is recursive through A, B, and/or C)


---

### Answer by username_5 on 2012-03-23. Score: 0

I do not think one needs a counter. Essentially you just check all the permutations but break 
pseudo-code:
perm-match(input, pattern)
     if pattern = nil return true

     foreach(rule in pattern)
         if (match(input, rule))
             perm-match(input - matchedpart, pattern - rule)
             break
         end
     end
     return false
end

Here is a more concrete example
Suppose we are trying to match any permutation of abcd and our string is bcda

Step 1: Find the first matched symbol. In this case it is b
Step 2: Remove that symbol from our pattern and reduce the string: e.g., acd and cda  are left
Step 3: Repeat step 1 on the new strings

c matches in cda which leaves us with ad and da
a matches in da which leaves us with d and d
d matches in d which leaves us with nil in both strings


So you see this simple algorithm can check for a permutation quite easily by simply comparing "strings" out of order. Note that the complexity of the function is O(n!) worse case and O(1) best case. In a sense the we are keeping count by storing the symbols to match in an array. I would think this would be 
"fast" in general since one wouldn't deal with very large n in most cases.

> **Comments:**
> **username_0**: My problem is: my $n$ does get very large - $n=50$ is quite common. Also, your method doesn't mesh well with standard LR parsing techniques - these phrases are sprinkled on a grammar that mostly contains non-permutation phrases.  

---

