Left factoring using Python
Question: Is there any predefined function in Python to identify the common prefixes on
the right side of a production rule?

For example, I need to turn this sort of data structure:

    
    
    ['abc', 'ab', 'd', 'dc']
    

into a dictionary of prefix-to-corresponding suffixes pairs. So my output for
this example should look something like this:

    
    
    {'ab': set(['c', '']), 'd': set(['c', ''])}  # ab is a common prefix and d is a common prefix
    

In more general terms, I need to convert this sort of input:

    
    
    S -> abc|ab|d|dc
    

into this sort of output:

    
    
    S -> abA|dA  # prefixes ab and d followed by A
    A -> c|NULL  # where A is either c or an equivalent of None
    

I want to use this output to perform left factoring of a grammar.


Answer: Another solution, let me know if that works:

    
    
    from itertools import takewhile,izip
    
    def groupby(ls):
        d = {}
        ls = [ y[0] for y in x ]
        initial = list(set(ls))
        for y in initial:
            for i in x:
                if i.startswith(y):
                    if y not in d:
                        d[y] = []
                    d[y].append(i)
        return d
    
    def prefix(x):
        return len(set(x)) == 1
    
    x=['abc','ab','d','dc']
    
    for k, l in groupby(x).iteritems():
        r = [l[0] for l in takewhile(prefix ,izip(*l))]
        print ''.join(r)
    

Output:

    
    
    ab
    d
    

