Permutation phrases with LR parsing 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 &lt;- X { A, B, C } Y


is equivalent to:

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


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.
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)