Notes

# First and Follow functions implementation
def first(grammar, symbol):
first_set = set()
if symbol not in grammar:
first_set.add(symbol)
else:
for production in grammar[symbol]:
for char in production:
if char != symbol:
first_set |= first(grammar, char)
if char not in grammar or 'ε' not in grammar[char]:
break
else:
first_set.add('ε')
return first_set

def follow(grammar, start_symbol):
follow_set = {start_symbol}
for left, right in grammar.items():
for production in right:
for i, char in enumerate(production):
if char in grammar:
follow_set |= (first(grammar, production[i+1:]) - {'ε'})
if 'ε' in first(grammar, production[i+1:]):
follow_set |= follow(grammar, left)
return follow_set

# Parse Table creation
def create_parse_table(terminals, non_terminals, grammar):
parse_table = {nt: {t: [] for t in terminals} for nt in non_terminals}
for non_terminal, productions in grammar.items():
for production in productions:
first_of_production = first(grammar, production[0])
for terminal in first_of_production:
if terminal != 'ε':
parse_table[non_terminal][terminal].append(production)
if 'ε' in first_of_production or len(production) == 0:
for terminal in follow(grammar, non_terminal):
parse_table[non_terminal][terminal].append(production)
return parse_table

# User input for Grammar
grammar = {}
terminals = set()
non_terminals = set()

num_productions = int(input("Enter the number of productions: "))
for _ in range(num_productions):
production = input("Enter production (in the form A->alpha): ")
left, right = production.split('->')
if left not in grammar:
grammar[left] = []
grammar[left].append(right.strip())
non_terminals.add(left)
for char in right.strip():
if char.islower():
terminals.add(char)

parse_table = create_parse_table(terminals, non_terminals, grammar)
print(parse_table)


INPUT:Enter the number of productions: 4
Enter production (in the form A->alpha): S->aAB
Enter production (in the form A->alpha): A->a
Enter production (in the form A->alpha): A->bB
Enter production (in the form A->alpha): B->b

OUTPUT :
{
'S': {'a': ['aAB']},
'A': {'a': ['a'], 'b': ['bB'], '$': ['ε']},
'B': {'b': ['b'], '$': ['ε']}
}