Permutation phrases with LR parsing

Question

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.

Answer 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 2

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.