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

• 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 Jan 27 '12 at 16:09
• About the rest of your question: cstheory.stackexchange.com/questions/4962/… 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 Jan 27 '12 at 16:16
• 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. dx.doi.org/10.3233/FI-1997-3112), but it's true that the hard instances might not be LR(1). – Sylvain Jan 27 '12 at 17:07
• @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 Jan 27 '12 at 19:35
• @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 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 Jan 27 '12 at 20:13

2 Answers

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)

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.

• 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 Mar 23 '12 at 16:55