Python function to calculate the FIRST sets from a context-free grammar given in BNF

first_sets.py

"""
MIT License

Copyright (c) 2024 Jesse Farmer <[email protected]>

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
"""

EPSILON = 'ε'

def is_epsilon(symbol):
    return symbol == EPSILON

def is_terminal(symbol):
    return not is_epsilon(symbol) and symbol.islower()

def is_nonterminal(symbol):
    return not is_epsilon(symbol) and symbol.isupper()

def get_first_sets(grammar):
    """
    Given a contect-free grammar, calculate the first sets for all
    nonterminal symbols.

    For a given nonterminal, its first set is the set of all terminals
    which can appear as the first character in any production. Since the
    empty string can "begin" any string whatsoever, it's only counted if
    the nonterminal can produce only the empty string.
    """
    first_sets = {key:set() for key in grammar.keys()}

    changed = True
    while changed:
        changed = False

        for nonterminal in grammar:
            for production in grammar[nonterminal]:
                prev_len = len(first_sets[nonterminal])

                first_sets[nonterminal] |= get_first_set_pass(production, first_sets)

                new_len = len(first_sets[nonterminal])

                if (new_len > prev_len):
                    changed = True

    return first_sets

def get_first_set_pass(production, first_sets):
    """
    Given a production and dict containing information about what
    terminal symbols we've seen so far, apply the production rule
    and add any new terminal symbols which appear at the beginning
    of the output.
    """
    first_set = set()

    for symbol in production:
        if is_nonterminal(symbol):
            first_set |= (first_sets[symbol] - {EPSILON})
            if EPSILON not in first_sets[symbol]:
                break
        elif is_terminal(symbol):
            first_set |= {symbol}
            break
        elif is_epsilon(symbol):
            first_set |= {EPSILON}
            break
    else:
        if EPSILON not in first_set:
            first_set |= {EPSILON}

    return first_set


import re
def parse_grammar(text):
    """
    Given text representing a grammar, turn it into a dictionary as follows:

      S -> ABC | x
      A -> y | z
      B -> y | #

      {
          'S': [list('ABC'), list('x')],
          'A': [list('y'), list('z')],
          'B': [list('y'), list('#')],
      }
    """
    grammar = dict()

    for line in text.strip().splitlines():
        lvalue, rvalue = re.split(r'\s*->\s*', line.strip())
        productions = [production.split(' ') for production in re.split(r'\s*\|\s*', rvalue)]

        grammar[lvalue] = grammar.get(lvalue, []) + productions

    return grammar

def key_sort_first(key):
    """
    Given a key like "foo", returns a lambda that ensures that "foo"
    appears FIRST in any sorting
    """
    return lambda value: (value != key, value)

def key_sort_last(key):
    """
    Given a key like "foo", returns a lambda that ensures that "foo"
    appears LAST in any sorting
    """
    return lambda value: (value == key, value)

def print_first_sets(first_set):
    """
    Prints out the collection of first sets.
    """
    for nonterminal in sorted(first_set, key=key_sort_first('S')):
        productions = sorted(first_set[nonterminal], key=key_sort_last(EPSILON))
        first_set_str = ', '.join(productions)

        print(f'FIRST({nonterminal}) = {{{first_set_str}}}')

if __name__ == "__main__":
    from textwrap import dedent

    # EPSILON is defined above as '#'
    grammar = dedent(f"""
    S -> A C E | B D D | E E C
    A -> a | S D a | {EPSILON}
    B -> b | a A c
    C -> c | b E | {EPSILON}
    D -> d | B c C e
    E -> e | C | {EPSILON}
    """)

    parsed_grammar = parse_grammar(grammar)
    first_sets = get_first_sets(parsed_grammar)

    print_first_sets(first_sets)

LICENSE

MIT License

Copyright (c) 2024 Jesse Farmer <https://github.com/jfarmer>

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.