I'm in the process of attempting to write a parser compiler. In this, sets play a major role. I'm in the 'lexical ambiguity' isolation phase, and to that, I need to yield a set of every possible permutation of a given set of items which represent an ambiguity.
An ambiguity is reached when there are at two or more items in the active context that are lexically identical, but differ by their defined identity (The contextual keyword 'from' versus an Identifier of 'from'.)
That being said, I first detect the ambiguities of the language, and generate a set of sets which represent the full extent of each ambiguity. Upon each set I then need to yield all permutations of two or greater. Below is the initial result that appears, upon testing, to do what I want, but I went overboard and have a method that operates on multiple sets, so if given: { 'a', 'b' }
and { 'c', 'd' }
it would yield { 'a', 'c' }
, { 'a', 'd' }
, { 'b', 'c' }
, and { 'b', 'd' }
, which I solved with the 'Splay' method.
public static IEnumerable<IEnumerable<T>> Splay<T>(this IEnumerable<T> series)
{
/* When you want to yield an enumerable over each element in the series. */
foreach (var element in series)
yield return new T[1] { element };
}
public static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(int minSetLength, params T[][] series)
{
return GetAllPermutations(minSetLength,
(IEnumerable<IEnumerable<T>>)series);
}
public static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(int minSetLength, IEnumerable<IEnumerable<T>> series)
{
var jaggedVariation =
series.Select(set => set.ToArray()).ToArray();
for (int minDepth = minSetLength; minDepth <= jaggedVariation.Length; minDepth++)
foreach (var set in GetPermutationsOfLength<T>(minDepth, jaggedVariation))
yield return set;
}
private static IEnumerable<IEnumerable<T>> GetPermutationsOfLength<T>(int elementsPerSet, T[][] series)
{
for (int subsetIndex = 0; subsetIndex < series.Length - (elementsPerSet - 1); subsetIndex++)
foreach (var subset in GetPermutationsOfLength<T>(elementsPerSet, subsetIndex, 0, series).Select(k=>k.ToArray()))
if (subset.Length == elementsPerSet) /* Keeps the logic below very simple. */
yield return subset;
}
private static IEnumerable<IEnumerable<T>> GetPermutationsOfLength<T>(int elementsPerSet, int startingAt, int currentLength, T[][] series)
{
if (startingAt >= series.Length || currentLength >= elementsPerSet)
yield break;
var currentFrontSet = series[startingAt];
foreach (var forefront in currentFrontSet)
{
var forefrontSet = new T[1] { forefront };
/* Continue expanding recursively until the above constraints cause it to short circuit. */
for (int i = startingAt + 1; i < series.Length; i++)
{
var subsets = GetPermutationsOfLength<T>(elementsPerSet, i, currentLength + 1, series);
foreach (var subset in subsets)
yield return forefrontSet.Concat(subset);
}
yield return forefrontSet;
}
}
I'll be calling this with a single array that I call Splay on due to my over eagerness, but the general idea is I need every possible combination with two or greater elements, with no repeats. So if an ambiguity represents 5 separate identities I would yield 26 different sets, two through five items long. Each permutation within these ambiguity sets would become unique identities themselves, and have a bit mask I could check against unambiguous transition tables to identify the specific ambiguity, unify that ambiguity to determine the proper follow set and how to differentiate which identity it once was.
Does anyone have any suggestions/insight on the approach? I tried to keep the approach simple: I used iterators due to the simplicity they provide. They will have a slight memory footprint due to the allocation of the iterator objects and the lifting of the locals; however, the environment this runs in is already utilizing 6+GB of memory to handle unbound look-ahead ambiguity resolution, so this is just another step.