Notes

def compute_first(grammar, symbol, computed=None):
if computed is None:
computed = set()
first_set = set()
if symbol in grammar['terminals']:
first_set.add(symbol)
elif symbol not in computed:
computed.add(symbol)
for production in grammar['productions'][symbol]:
first_set |= compute_first(grammar, production[0], computed)
if grammar['epsilon'] not in first_set:
break
else:
first_set.add(grammar['epsilon'])
return first_set

def compute_follow(grammar, symbol, computed=None):
if computed is None:
computed = set()
follow_set = set()
if symbol == grammar['start_symbol']:
follow_set.add('$')
if symbol not in computed:
computed.add(symbol)
for nonterminal, productions in grammar['productions'].items():
for production in productions:
if symbol in production:
index = production.index(symbol)
if index == len(production) - 1:
if nonterminal != symbol:
follow_set |= compute_follow(grammar, nonterminal, computed)
else:
follow_set |= compute_first(grammar, production[index + 1], computed)
if grammar['epsilon'] in follow_set:
follow_set.remove(grammar['epsilon'])
follow_set |= compute_follow(grammar, nonterminal, computed)
return follow_set

# Take user input to specify the grammar productions
grammar = {
'terminals': set(),
'nonterminals': set(),
'start_symbol': None,
'productions': {},
'epsilon': 'epsilon'
}
num_productions = int(input("Enter the number of productions: "))
for i in range(num_productions):
production = input(f"Enter production {i + 1}: ").strip()
nonterminal, rhs = production.split(':')
grammar['nonterminals'].add(nonterminal)
if i == 0:
grammar['start_symbol'] = nonterminal
grammar['productions'][nonterminal] = [tuple(production.strip().split()) for production in rhs.split('|')]

# Compute the first and follow sets of the grammar
first_sets = {}
follow_sets = {}
for symbol in grammar['nonterminals']:
first_sets[symbol] = compute_first(grammar, symbol)
follow_sets[symbol] = compute_follow(grammar, symbol)

# Print the first and follow sets
print('First sets:')
for symbol, first_set in first_sets.items():
print(f' {symbol}: {first_set}')
print('Follow sets:')
for symbol, follow_set in follow_sets.items():
print(f' {symbol}: {follow_set}')