context_free_grammar.py

# Written by Eric Martin for COMP9021

'''
Checks whether a word can be generated from a starting symbol
by a context free grammar, represented by a dictionnary
whose keys are the nonterminals and for each nonterminal N,
the value associated with N is the set of productions of N,
one of which is possibly ε (the empty production).

A character is a nonterminal symbol iff it is an uppercase letter.

If ε is not one of the starting symbol's productions, then it is added
as such by eliminate_ε() in case the empty string can be generated.
Whether this is the case or not, eliminate_ε() removes all productions
of ε by nonterminals different to the starting symbol, possibly adding
other productions to generate the same language.
That allows one to guarantee that a nonempty word w belongs to the
generated language iff it can be generated thanks to a sequence
of productions consisting of words no longer than w.
'''

def eliminate_ε(rules, starting_symbol):
    '''
    >>> rules = {'S': {'SS', '(S)', '()'}}
    >>> eliminate_ε(rules, 'S') == rules
    True
    
    >>> rules = {'S': {'bSbb', 'A'}, 'A': {'aA', 'ε'}}
    >>> eliminate_ε(rules, 'S') == {'S': {'', 'A', 'bbb', 'bSbb'},
    ...                            'A': {'aA', 'a'}}
    True
    '''
    # We look for the set S1 of all symbols producing ε,
    # then for the set S2 of all symbols producing a sequence
    # of symbols in S1, then for the set S3 of all symbols
    # producing a sequence of symbols in the union of S1 with S2...
    # If starting_symbol eventually shows up, 
    # then ε is added to starting_symbol's productions
    # in case it is not already recorded as such.
    symbols_leading_to_ε = {'ε'}
    search_more = True
    while search_more:
        search_more = False
        for nonterminal in set(rules) - symbols_leading_to_ε:
            if any(set(production) <= symbols_leading_to_ε
                                        for production in rules[nonterminal]):
                if nonterminal == starting_symbol:
                    rules[starting_symbol].add('ε')
                    search_more = False
                    break
                symbols_leading_to_ε.add(nonterminal)
                search_more = True
    new_rules = {}
    for nonterminal in rules:
        new_productions = set()
        for production in rules[nonterminal] - {'ε'}:
            # In production, an occurrence of a nonterminal P
            # is either kept or eliminated (doubling the number of
            # derived productions) in case 'ε' can be produced from P.
            # For instance, if X can produce 'ε' but Y cannot, then
            # the production aaXbYaX will give rise to the productions:
            # - aaXbYaX
            # - aabYaX
            # - aaXbYa
            # - aabYa
            productions = {''}
            for symbol in production:
                if symbol in rules and 'ε' in rules[symbol]:
                    productions = productions.union(word + symbol
                                                    for word in productions)
                else:
                    productions = {word + symbol for word in productions}
            new_productions = new_productions.union(productions)
        new_rules[nonterminal] = new_productions
        # If the grammar can generate the empty string,
        # then '' is one of the productions of starting_symbol;
        # it is removed from all other productions, if any.
        if nonterminal != starting_symbol:
            new_rules[nonterminal] -= {''}
    return new_rules


def can_generate_with_no_ε(word, rules, starting_symbol):
    '''
    >>> rules = {'S': {'SS', '(S)', '()'}}
    >>> can_generate_with_no_ε('()', rules, 'S')
    True
    >>> can_generate_with_no_ε('(())', rules, 'S')
    True
    >>> can_generate_with_no_ε('()()', rules, 'S')
    True
    >>> can_generate_with_no_ε('(()())', rules, 'S')
    True
    >>> can_generate_with_no_ε('((())())(((())))', rules, 'S')
    True
    >>> can_generate_with_no_ε('(', rules, 'S')
    False
    >>> can_generate_with_no_ε('())', rules, 'S')
    False

    >>> rules = {'S': {'', 'A', 'bbb', 'bSbb'}, 'A': {'aA', 'a'}}
    >>> can_generate_with_no_ε('', rules, 'S')
    True
    >>> can_generate_with_no_ε('bbb', rules, 'S')
    True
    >>> can_generate_with_no_ε('aa', rules, 'S')
    True
    >>> can_generate_with_no_ε('babb', rules, 'S')
    True
    >>> can_generate_with_no_ε('bbbbbb', rules, 'S')
    True
    >>> can_generate_with_no_ε('bbaaabbbb', rules, 'S')
    True
    >>> can_generate_with_no_ε('bbbaaaaaabbbbbb', rules, 'S')
    True
    >>> can_generate_with_no_ε('bbbbb', rules, 'S')
    False
    >>> can_generate_with_no_ε('bbabbbbb', rules, 'S')
    False
    >>> can_generate_with_no_ε('bbabbbba', rules, 'S')
    False
    '''
    if word == '':
        if '' in rules[starting_symbol]:
            return True
        return False
    rules[starting_symbol] -= {''}
    generated_bigrams = {('', starting_symbol)}
    seen_bigrams = generated_bigrams
    while generated_bigrams:
        bigram = generated_bigrams.pop()
        # bigram is a pair of the form (w_1, w_2)
        # where all symbols in w_1 are terminals.
        # - If w_2 is of the form tw where t is a terminal symbol,
        #   then (w_1, w_2) is replaced by (w_1t, w).
        # - Otherwise, if w_1 is not an initial segment of word,
        #   then (w_1, w_2) is dumped.
        # - Otherwise, if w_2 is empty, then either w_1 is word
        #   and word is known to have been generated, or (w_1, w_2) is dumped.
        # - Otherwise, w_2 is of the form Nw where N is a nonterminal symbol,
        #   and (w_1, w_2) is replaced by all pairs of the form
        #   (w_1, w'w) where w' can be produced from N and w_1w'w is
        #   not longer than word.
        while bigram[1] and not bigram[1][0].isupper():
            bigram = bigram[0] + bigram[1][0], bigram[1][1:]
        if not word.startswith(bigram[0]):
            continue
        if not bigram[1]:
            if len(bigram[0]) == len(word):
                return True
            continue
        for pattern in rules[bigram[1][0]]:
            new_bigram = bigram[0], pattern + bigram[1][1:]
            if len(new_bigram[0]) + len(new_bigram[1]) <= len(word):
                if new_bigram not in seen_bigrams:
                   generated_bigrams.add(new_bigram)
                seen_bigrams.add(new_bigram)
    return False


def can_generate(word, rules, starting_symbol):
    '''
    >>> rules = {'S': {'SS', '(S)', '()'}}
    >>> can_generate('()', rules, 'S')
    True
    >>> can_generate('(())', rules, 'S')
    True
    >>> can_generate('()()', rules, 'S')
    True
    >>> can_generate('(()())', rules, 'S')
    True
    >>> can_generate('((())())(((())))', rules, 'S')
    True
    >>> can_generate('(', rules, 'S')
    False
    >>> can_generate('())', rules, 'S')
    False

    >>> rules = {'S': {'bSbb', 'A'}, 'A': {'aA', 'ε'}}
    >>> can_generate('', rules, 'S')
    True
    >>> can_generate('bbb', rules, 'S')
    True
    >>> can_generate('aa', rules, 'S')
    True
    >>> can_generate('babb', rules, 'S')
    True
    >>> can_generate('bbbbbb', rules, 'S')
    True
    >>> can_generate('bbaaabbbb', rules, 'S')
    True
    >>> can_generate('bbbaaaaaabbbbbb', rules, 'S')
    True
    >>> can_generate('bbbbb', rules, 'S')
    False
    >>> can_generate('bbabbbbb', rules, 'S')
    False
    >>> can_generate('bbabbbba', rules, 'S')
    False
    '''
    return can_generate_with_no_ε(word,
                                  eliminate_ε(rules, starting_symbol),
                                  starting_symbol)

if __name__ == '__main__':
    import doctest
    doctest.testmod()