Evaluates whether a given set of rewrite rules is ambiguous after X steps.

grammar_ambiguity_evaluator.py

from collections import Counter

from itertools import product, chain

rules = {"S": [("a", "S", "a"), ("a", "S", "b", "S", "a"), ()]}
rules_two = {"S": [("aa", "S", "b"), ("ab", "S", "b", "S"), ()]}

start = ("S",)


def expand_grammar(start, rules, max_rewrites=1):
    """Calculates the grammar of a given set of production rules.

    :param start: The start symbol.
    :param rules: The production rules.
    :param max_rewrites: The max number of rewrites to perform
    :returns: The expanded grammar after X rewrites.
    """
    expanded_parts = []
    for part in start:
        if part in rules:
            part_rules = rules[part]
            if max_rewrites == 1:
                expanded_parts.append(part_rules)
            else:
                expansion = []
                for rule in part_rules:
                    expansion += expand_grammar(rule, rules, max_rewrites - 1)
                expanded_parts.append(expansion)
        else:
            expanded_parts.append((part,))

    # get the product of all the possible options
    # and join each of the into a string
    words = ("".join(chain.from_iterable(word)) for word in product(*expanded_parts))

    # filter out any words with remaining production rules
    # if we are not rewriting any further
    return (word for word in words if not (max_rewrites == 1 and "S" in word))


def is_ambiguous(start, rules, max_rewrites):
    counter = Counter(expand_grammar(start, rules, max_rewrites))
    ambiguities = sum(x > 1 for x in counter.values())
    print(f"Magnitude of grammar after {max_rewrites} rewrites: {len(counter.keys())}")
    print(f"Unique derivations: {sum(counter.values())}")
    print(f"Total ambiguities: {ambiguities}")
    return ambiguities > 0


is_ambiguous(start, rules, 6)
is_ambiguous(start, rules_two, 6)